学C语言的时候经常用库函数qsort，学数据结构的时候知道qsort是怎么一回事儿了，数据结构期末考试有一道题就是写快排的算法，当时很熟悉，但很久不用就忘了，再写一遍加深印象。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| public class Main {
public static void main(String[] args) {
int[] nums = randomArray(100);
System.out.println("排序前：" + Arrays.toString(nums));
qSort(nums);
System.out.println("排序后：" + Arrays.toString(nums));
}
private static void qSort(int[] nums) {
qSort(nums, 0, nums.length - 1);
}
private static void qSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int std = order(nums, left, right);
qSort(nums, left, std - 1);
qSort(nums, std + 1, right);
}
private static void swap(int[] nums, int index1, int index2) {
int tmp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = tmp;
}
private static int order(int[] nums, int left, int right) {
int std = left;
int l = left + 1, r = right;
boolean flag = false;
while (l <= r) {
if (flag) {
if (nums[std] < nums[l]) {
swap(nums, std, l);
flag = false;
std = l;
}
l++;
} else {
if (nums[std] > nums[r]) {
swap(nums, std, r);
flag = true;
std = r;
}
r--;
}
}
return std;
}
private static int[] randomArray(int length) {
int[] nums = new int[length];
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (Math.random() * 100);
}
return nums;
}
}
|
核心是一趟快速排序的算法，如果选择第一个元素作为参考，就必需先从后往前对比交换位置，举个栗子：
如果序列是：【5， 6， 4， 2】，先从左往右对比交换：
- 第一次：5和6对比，不做变化。
- 第二次：5和4对比，交换位置。【4，6， 5，2】
- 第三次：换方向，5和2对比，交换位置。【4，6，2，5】
出问题了，最大的数6没能移动到最后，这是因为5和6对比的时候5还在6的前面，而当5移动到6之后时，6已经失去了移动的机会。
反过来，如果先从右往左，一开局5就处于一个尽可能靠后的位置，上面的情况则可以避免。