快速排序实现及优化 | DualPivotQuicksort

快速排序的基本实现

快速排序算法是一种基于交换的高效的排序算法,它采用了 分治法 的思想:

  1. 从数列中取出一个数作为基准数(枢轴,pivot)。
  2. 将数组进行划分(partition),将比基准数大的元素都移至枢轴右边,将小于等于基准数的元素都移至枢轴左边。
  3. 再对左右的子区间重复第二步的划分操作,直至每个子区间只有一个元素。

快排最重要的一步就是划分了。划分的过程用通俗的语言讲就是“挖坑”和“填坑”。

举个例子,首先给一组数组:

0 1 2 3 4 5 6 pivot
36 9 -7 45 23 61 15

为了方便起见,我们选择第一个元素36作为基准数,这样就腾出了第一个位置(挖坑),下面首先自右向左寻找比基准数小的元素填至第一个位置(填坑):

0 1 2 3 4 5 6 pivot
15 9 -7 45 23 61 36

第七个位置被腾出,然后再自左向右寻找比基准元素大的元素填在空位处:

0 1 2 3 4 5 6 pivot
15 9 -7 23 61 45 36

再重复上面的动作,直到第一趟划分完毕。此时[a0,a3]都是小于基准值a4的,[a5,a6]都是大于基准值a4的:

0 1 2 3 4 5 6 pivot
15 9 -7 23 36 61 45 36

然后再对两个子序列递归地进行上述的过程,最终可得到有序序列。

总结一下这个划分的过程:

  1. 设两个指示 i=left,j=right;设 arr[left] 为基准数
  2. 从后向前寻找比基准元素大的元素,填至空位处
  3. 从前向后寻找比基准元素小的元素,填至空位处
  4. 重复执行 2、3 步,直到两指示相等,将基准元素填至指示的位置,本次划分结束

用代码表示为:

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
int partition(int arr[], int left, int right) {
int i = left, j = right;
int tmp = arr[left];
while (i < j) {
while (i < j && arr[j] > tmp)
j--;
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < tmp)
i++;
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = tmp;
return i;
}
void quick_sort(int arr[], int left, int right) {
if(left > right)
return;
int j = partition(arr, left, right);
quick_sort(arr, left, j - 1);
quick_sort(arr, j + 1, right);
}

当然用Haskell写是最简单的了:)

1
2
3
4
5
6
qs :: (Ord a) => [a] -> [a]
qs [] = []
qs (x:xs) =
let s = qs $ filter (<= x) xs
l = qs $ filter (> x) xs
in s ++ [x] ++ l

另一种实现划分的思路是先从左到右扫描一个比基准数大的元素,再从右到左扫描一个比基准数小的元素(左右两个指针 i、j 滑动),然后交换这两个元素,重复操作直到两指针相遇,然后将基准元素 arr[left] 与左子序列最后的元素 arr[j] 进行交换即可,用代码描述为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int partition(int arr[], int left, int right) {
int i = left, j = right + 1;
int temp = arr[left];
while (true) {
while (arr[i] < temp && i < right) {
i++;
}
while (arr[j] > temp && j < left) {
j++
}
if (i >= j)
break;
swap(arr[i], arr[j]);
}
swap(arr[left], arr[j]);
return j;
}

快速排序算法的平均时间复杂度为 $O(NlogN)$。快排的最差情况为序列完全有序,此时快排退化为冒泡排序,时间复杂度为 $O(n^2)$ 。

快速排序的改进和优化

快速排序也有不足之处,比如对于元素较少或接近有序的数组来说,快速排序平均性能比插入排序差。这是因为小数组信息熵相对来说比较小(特别是经过一系列的快速排序调用以后),而插入排序在数据接近有序的情况下时间复杂度接近 $O(N)$,再加上快速排序递归调用也会有一些性能损耗。因此,针对小数组,我们可以加个判断,对小数组使用插入排序。Java标准库自带的排序DualPivotQuicksort就是这么干的,INSERTION_SORT_THRESHOLD = 47。

另外一个改进快速排序性能的方法就是使用 双枢轴,即将数组三切分(大于枢轴,等于枢轴,小于枢轴),可以证明这样是熵最优的并且更高效。为什么这样划分呢?因为统计表明对大规模数组进行排序时,数据重复的情况比较多,因此使用双枢轴可以有效避免相等元素之间的比较。以 Java 标准库为例,JDK 1.8 中的 DualPivotQuicksort 实现了一种 快速三向切分 的快速排序,它通过将相等元素聚集起来的方式使熵最优(原理:将相等元素聚集起来,不必再切分这些元素)。

快速三向切分

还有一个优化的杀手锏就是 改进划分的策略,这里 DualPivotQuicksort 使用了一种称为 五取样划分 的策略对数组进行划分,类似于 BFPRT 算法

总结一下,快排的改进主要有三种方法:小数组使用插入排序、双枢轴(快速三向切分)、划分策略优化(五取样划分)。经过优化后的快速排序算法时间复杂度可以介于 $O(N)$ 到 $O(NlogN)$ 之间,性能更优。具体实现可以看 DualPivotQuicksort 的源码,实现的很复杂,非常奇妙。

文章目录
  1. 1. 快速排序的基本实现
  2. 2. 快速排序的改进和优化