快速排序简介
快速排序正如其名，是一种极为快速的排序，通常情况下的时间复杂度仅为 O(nlogn) ，在极端条件下才会退化为 O(n^2) 。
快速算法采用分治和递归的思想，其核心操作如下：
- 选出基准值，将数组划分为两个部分，左边的数值都小于基准值，右边的数值都小于基准值。
- 把两个部分看作独立的数组，重复上述操作。
- 当划分出的数组只有一个元素时，表示排序完成，即递归出口。
事实上这一过程十分直观，以数组
1
|
[3, 5, 1, 6, 12, 2, 4, 8, 9, 7, 10, 11]
|
为例，对其进行的操作如下：
- 选出第一个元素
3
- 将其移动到正确的位置，使得其左边的元素都小于它，右边的元素都大于它。
那么为了达到这一点，我们可以使用两个指针，分别从前往后和从后往前查找。每次从后面找一个比基准值小的，从前面找一个比基准值大的，然后将其交换，就可以将这两个元素从不应该呆在的位置上移动到正确的位置上。这样一来，就可以把大的元素放在后面，把小的元素放在前面了。
很显然，最终这两个指针会相遇，相遇的位置就是基准值应当存在的位置了。但是这里有一个问题，就是相遇位置的这个元素，我们需要确保它是比基准值小的元素，因为它会被放到数组的开头位置。
为了保证这一点，我们需要做的一个细节是：永远让右边的指针先向前走。
举一个简单的例子，如果我们不让右边的指针先走会发生什么？
1
2
|
0 1 2 3 4 5 6 7
↑(i) ↑(j)
|
假设先从左边查找，找一个比基准值 0 大的，那么自然会找到第一个元素 1 ：
1
2
|
0 1 2 3 4 5 6 7
↑(i) ↑(j)
|
那么再从右边查找，由于找不到一个比基准值小的，因此两个指针会直接相遇，那么按照规定，需要交换指针指向的元素和基准元素，0 和 1 就会发生交换，这显然是不合理的。我们希望实现：如果基准值已经是数组中的最小元素了，最终指针应当指向其自身。那么只能让右边的指针先走，才能保证这一点：很显然，如果右指针始终无法找到一个小于基准值的元素，则会直接走到开始位置，即基准值自身
1
2
|
0 1 2 3 4 5 6 7
↑(i,j)
|
这样一来基准值的位置就不会被意外改变了。
最终这一轮的结果是：
1
|
[1 2] {3} [6 12 5 4 8 9 7 10 11]
|
层层递归，最终完成排序。
代码实现
交换式
这里有两种实现方式，首先是交换式：
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
|
int partition(int arr[], int start, int end) {
// 取第一个元素作为基准元素
int pivot = arr[start], i = start, j = end;
while (i < j) {
// 从右向左找到小于基准值的 arr[j]
while (i < j && arr[j] >= pivot)
j--;
// 从左向右找到大于基准值的 arr[i]
while (i < j && arr[i] <= pivot)
i++;
// 如果没相遇，则交换元素
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 指针相遇，将基准元素与指针指向元素交换
arr[start] = arr[i];
arr[i] = pivot;
return i;
}
void quickSort(int arr[], int start, int end) {
if (start < end) {
// 将数组通过基准值分成两部分分别排序
int pivot = partition(arr, start, end);
quickSort(arr, start, pivot - 1);
quickSort(arr, pivot + 1, end);
}
}
|
填坑式
还有一种“填坑式”，区别就在于把第一个元素（基准值）的位置空出来，从右边找到一个比基准值小的元素就直接把它放到这个空出的位置，然后从左边找一个比基准值大的元素放到右边空出的位置。这样一来，指针相遇时一定是处于一个“空白”位置，直接把基准值放进去即可。每次元素只是单纯的移动，省去了交换的环节。代码实现如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
int partition(int arr[], int start, int end) {
// 取第一个元素作为基准元素
int pivot = arr[start];
while (start < end) {
// 从右向左找第一个比基准小的元素
while (start < end && arr[end] >= pivot)
end--;
// 没有相遇，则将这个大的元素放到 start 的位置
if (start < end)
arr[start++] = arr[end];
// 从左向右找第一个比基准大的元素
while (start < end && arr[start] <= pivot)
start++;
// 没有相遇，则将这个小的元素放到 end 的位置
if (start < end)
arr[end--] = arr[start];
}
// 把基准值放到最终空出来的 start 位置上
arr[start] = pivot;
return start;
}
|
主函数调用则与交换式保持一致。
随机快速排序
上文提到，快速排序在极端条件下才会退化为 Ο(n^2) 的时间复杂度，这是由于快速排序在面对近乎有序的数组时，每次 partition 分区产生的子数组切片长度会极其不平衡，例如之前的例子：
1
2
|
0 1 2 3 4 5 6 7
↑(i) ↑(j)
|
这一轮最终产生的切片会是这样的
然后下一轮的切片则是：
每次划分的时候总有一个切片中的元素个数为 0，而另一个切片中的元素个数为 n-1 。此时，算法需要对每一个数据（最后一个数据除外）都进行一次分区，即 n-1次分区操作，每次都只能确定一个元素的位置。而我们知道，一个长度为 2 的切片就可以同时确定两个元素的位置了，快速排序分治法的思想就是把整个数组全部分块成长度为 2 的最小单位，整个操作如下：
1
2
3
|
[8]
[4] [4]
[2] [2] [2] [2] // 可以返回了
|
那么自然就是一个 O(nlogn) 的复杂度。而在上述的最差情况下，自然就是 O(n^2) 的复杂度了。
为了避免这种情况的出现，我们就不能每次都只取第一个元素作为基准值了，需要随机取一个值，这也就是随机快速排序的唯一变动。这样一来，我们就可以保证在遇到近乎有序的数组时，不会产生长度差距悬殊的切片了。使得在任何情况下，排序都趋近于 O(nlogn) 的复杂度。
使用 JavaScript 实现较为简单：
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
|
function randomPartition(arr, start, end) {
// 随机取一个元素
const pivotIndex = parseInt(Math.random() * (end - start) + start);
// 将这个元素和切片起始元素交换
[arr[start], arr[pivotIndex]] = [arr[pivotIndex], arr[start]];
// 后续操作全部相同
const pivot = arr[start];
while (start < end) {
// 从右向左找第一个比基准小的元素
while (start < end && arr[end] >= pivot) end--;
if (start < end) arr[start++] = arr[end];
// 从左向右找第一个比基准大的元素
while (start < end && arr[start] <= pivot) start++;
if (start < end) arr[end--] = arr[start];
}
arr[start] = pivot;
return start;
}
function randomQuickSort(arr, start, end) {
if (start < end) {
const pivot = randomPartition(arr, start, end);
randomQuickSort(arr, start, pivot - 1);
randomQuickSort(arr, pivot + 1, end);
}
return;
}
|
是不是很简单呢:D
