快速排序-笔记

算法描述

Hoare 在 1960 年发明了这个算法,该算法的思路是选择一个元素作为切分元素,并排定它在数组中的位置,使得它左边的元素都小于等于它,右边的都大于等于它;然后分别递归地对左右两部分重复前面的过程。如果每个元素左边的小于等于它,右边的元素大于等于它,整个数组就有序了。

算法实现

先看基于二向切分的基本实现。切分数组的过程如下图:

二向切分的示意图

具体实现:

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

public void sort(Comparable[] a) {
StdRandom.shuffle(a); // 消除对输入的依赖
sort(a, 0, a.length-1);
}

private void sort(Comparable[] a, int low, int high) {
if (high <= low) return;
int k = partition(a, low, high); // 切分
sort(a, low, k-1); // 将左半部分a[low..k-1]排序
sort(a, k+1, high); // 将右半部分a[k+1..high]排序
}

/**
* 为子数组选定切分元素, 并排定它在数组中的位置。
* 排定位置后, 它左边的所有元素都小于等于它, 右边的都大于等于它。
* @param a 输入数组
* @param low 子数组起始位置
* @param high 子数组结束位置
* @return 排定位置之后切分元素的索引
*/
private int partition(Comparable[] a, int low, int high) {
Comparable v = a[low]; // 选定切分元素
int i = low, j = high + 1; // 左右扫描指针

while (true) {
// 等价的写法, 但可读性没有下面的写法好
//while (less(a[++i], v) && i < high) {}
//while (less(v, a[--j]) && j > low) {}

while (less(a[++i], v)) if (i == high) break;
while (less(v, a[--j])) if (j == low) break;
if (i >= j) {
break;
}
// 能走到这里表明 i < j。在 i < j 这个前提下, 前面两个循环
// 退出的原因只能是找到了我们希望的元素, 因此执行交换操作
exch(a, i, j);
}
exch(a, low, j); // 将切分元素 v 放入正确的位置
// 此时 a[low..j-1] <= a[j] <= a[j+1..high] 已达成
return j;
}

/**
* 展现很容易犯的错误
*/
private int wrongPartition(Comparable[] a, int low, int high) {
Comparable v = a[low]; // 选定切分元素
int i = low, j = high + 1; // 左右扫描指针

while (true) {
// TODO 错误写法一: 循环很可能在 因数组下标越界而抛出异常 时才退出。
// 之所以会犯这个错是因为正确的代码在循环体中有检查是否达到上下界,
// 达到则直接 break。想把循环体精简掉时就想当然地把上下界包含到了循环条件中了
while (less(a[++i], v) && i <= high) {}
while (less(v, a[--j]) && j >= low) {}

// TODO 错误写法二: 数组下标会越界
// j 初始值为 high+1, i 等于 high+1 时,
// 如果 high 是输入数组最后一个元素的索引, 那么第一次执行该循环时下标就会越界;
// 如果 high 之后还有元素, 那么就会操作到其他子数组的元素了, 导致最终的结果并不是有序的
while (less(a[++i], v) && i <= j) {}
while (less(v, a[--j]) && i <= j) {}

// TODO 错误写法三: 数组下标还是会越界
// 很可能会觉得把错误写法二这样修改哈就正确了, 但实际上仍然会下标越界。
// 因为 j 初始值为 high+1, 第一次执行该循环时, 在将 i 更新为 high 后,
// 还要再检查一次循环条件以退出循环, 这时就会出现跟错误二同样的情形
while (less(a[++i], v) && i < j) {}
while (less(v, a[--j]) && i < j) {}

// TODO 错误写法四: i, j 永远碰不了头, 进而导致外层循环死循环
// 很可能会觉得把错误写法三这样改改就好了, 可问题是之前的错误解决了, 却引入了新的错误。
// 因为循环条件包含 i < j-1, 所以 i == j-1 时两个循环就退出了, 那 i 和 j 就永远碰不了头,
// 进而 i >= j 的条件永远无法满足, 外层循环就成死循环了。
while (less(a[++i], v) && i < j-1) {}
while (less(v, a[--j]) && i < j-1) {}

if (i >= j) {
break;
}
exch(a, i, j);
}
exch(a, low, j);
return j;
}

注意,一定要保持 输入数组 元素顺序的随机性。此外,左侧扫描最好是在遇到 大于等于切分元素值的元素 时停下,右侧扫描最好是在遇到 小于等于切分元素值的元素 时停下。虽然这样可能会不必要地交换一些等值的元素,但在某些典型的应用中(处理只有若干种元素值的数组时),它能够避免算法的运行时间变为平方级别。

上面的实现有下面几点可以该改进:

  1. 切分操作中防止左端越界的测试条件 (j == low) 是冗余的,因为 j 为 low 时,前面的循环测试条件肯定通不过(a[low] 就是 v)。防止右端越界的测试条件 (i == high) 通过引入哨兵元素也可以去掉。

  2. 和大多数递归排序算法一样,快速排序的的性能改进基于以下两点:

    • 对于小数组,快速排序比插入排序慢;
    • 快速排序的 sort() 方法对于小数组也会递归地调用自己。

      对于小规模数组使用插入排序,就可以同时改进这两点。可是具体操作起来,对于多大的数组才合适用插入排序呢?这个参数的最佳值是和系统相关的,但是 5 ~ 15 之间的任意值在大多数情况下都能令人满意。

  3. 切分元素的选取。对于中等规模的数组,使用三取样选取切分元素;对于大规模数组,使用Tukey’s ninther 方法。三取样就是选 3 个元素作为样本元素,计算找到样本元素的中位数作为切分元素。Tukey’s ninther 方法就是选三组,每组三个元素,分别取三组元素的中位数,然后取三个中位数的中位数作为切分元素。

    注意,可以将切分元素放在数组末尾作为“哨兵”来去掉 partition() 方法中的数组右端边界测试 (i == high),算是对改进 1 的补充吧。

  4. 实际应用中经常会出现含有大量重复元素的数组,对于这些情况,上面的快速排序实现性能尚可,但还有巨大的改进空间。在有大量重复元素的情况下,快速排序的递归性会使 元素全部重复的子数组 经常出现,这儿就有很大的改进空间,我们可以将上面的实现的性能由线性代数级别提高到线性级别。

    一个简单的方法就是三向切分,把数组分成三部分,分别对应于小于、等于和大于切分元素的数组元素。但是在数组元素重复不多的普通情况下,它比标准的二分法多使用了很多次交换。Bentley-McIlroy 三向切分聪明地解决了这个问题,使得三向切分的快速排序 在包括有很多重复元素的实际应用中 比归并排序和其他排序方法更快。

简单三向切分的过程:

简单三向切分的示意图

简单三向切分的实现:

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

private void sort(Comparable[] a, int low, int high) {
if (high <= low) return;
// 将 a[low] 选定为切分元素
Comparable v = a[low];
// lt 是与切分元素相等的那部分的左边界,
// 因此其初始值就是 low
int lt = low;
// i 是还未确定所在区域的那部分的左边界。
// 因为已将 a[low] 选定为切分元素, 所以初始时
// 从下一个元素开始一直到子数组末尾都是未确定的区域
int i = low + 1;
// gt 是还未确定所在区域的那部分的右边界,
// 其初始值自然是 high
int gt = high;

// i..gt 还未确定所属区域的
// gt+1..high 比 v 大的
// lt..i-1 等于 v 小的
// low..lt-1 比 v 小的

while (i <= gt) {
int cmp = a[i].compareTo(v);
// 参与交换的两个元素的大小状况都很明确,
// 一个等于, 一个小于, 所以两个指针都要向前移动
if (cmp < 0) exch(a, lt++, i++);
// 参与交换的两个元素中, 交换到 i 位置的元素大小
// 不明确, 所以交换后 i 不能向前移动,
// 以便下一次处理刚交换到 i 位置的元素
else if (cmp > 0) exch(a, gt--, i);
else i++;
} // 现在 a[low..lt-1] < v=a[lt..gt] < a[gt+1..high] 成立

sort(a, low, lt-1);
sort(a, gt+1, high);
}

Bentley-McIlroy 三向切分的过程:

Bentley-McIlroy 三向切分的示意图

改进 2、3、4 的具体实现:

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

// cutoff to insertion sort, must be >= 1
private static final int INSERTION_SORT_CUTOFF = 8;

// cutoff to median of 3 partitioning
private static final int MEDIAN_OF_3_CUTOFF = 40;

@Override
public void sort(Comparable[] a) {
StdRandom.shuffle(a);
sort(a, 0, a.length-1);
}

private void sort(Comparable[] a, int low, int high) {
//if (high <= low) return; // unnecessary

int n = high - low + 1;

// 改进一: 对于小规模数组使用插入排序
if (n <= INSERTION_SORT_CUTOFF) {
insertionSort(a, low, high);
return;
}

// 改进二: 切分元素的选取
partition(a, low, high);

// 改进三: 使用 Bentley-McIlroy 3-way partitioning
// --------------------------
Comparable v = a[low];
int p = low, q = high+1;
int i = low, j = high+1;

while (true) {
while (less(a[++i], v)) if (i == high) break;
while (less(v, a[--j])) if (j == low) break;

// 如果 i 和 j 相遇, 且指向的元素等于 v,
// 就将其和最左边的那个小于 v 的元素交换位置。
// ++p 执行后 p 就指向最左边的那个小于 v 的元素,
// 交换位置后, p 就指向刚找到的这个等于 v 的元素。
if (i == j && eq(a[i], v)) {
exch(a, ++p, i);
}

if (i >= j) {
break;
}

exch(a, i, j);
if (eq(a[i], v)) {
exch(a, ++p, i);
}
if (eq(a[j], v)) {
exch(a, --q, j);
}
}

i = j+1;
for (int k = low; k <= p; k++) {
exch(a, k, j--);
}
for (int k = high; k >= q; k--) {
exch(a, k, i++);
}

sort(a, low, j);
sort(a, i, high);
// --------------------------
}

private void partition(Comparable[] a, int low, int high) {
int n = high - low + 1;

// use median of 3 as partitioning element
if (n <= MEDIAN_OF_3_CUTOFF) {
int m = median3(a, low, low + n / 2, high);
exch(a, low, m);
} else { // use Tukey ninther as partitioning element
int eps = n/8;
int mid = low + n/2;
int m1 = median3(a, low, low+eps, low+eps+eps);
int m2 = median3(a, mid-eps, mid, mid+eps);
int m3 = median3(a, high-eps-eps, high-eps, high);
int ninther = median3(a, m1, m2, m3);
exch(a, low, ninther);
}
}

private void insertionSort(Comparable[] a, int low, int high) {
for (int i = low+1; i <= high; i++) {
Comparable v = a[i];
int j = i;
for (; j > low && less(v, a[j-1]); j--) {
a[j] = a[j-1];
}
a[j] = v;
}
}

private int median3(Comparable[] a, int i, int j, int k) {
return less(i, j)
? (less(j, k) ? j : (less(i, k) ? k : i))
: (less(k, j) ? j : (less(k, i) ? k : i));
}

算法性能评估

快速排序可能是应用最广泛的排序算法了。原因是它实现简单、适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。

最引人注目的特点就是它是原地排序(只需要一个很小的辅助栈),且将长度为 N 的数组排序所需的时间和 $NlgN$ 成正比。另外,快速排序的内循环比大多数排序算法都要短小。

主要的缺点就是非常脆弱,在实现时要非常小心才能避免低劣的性能。

将长度为 N 的无重复数组排序,快速排序平均需要 ~ $2NlnN$ 次比较,以及 1/6 的交换。$2NlnN \approx 1.39NlgN$,也就是说平均比较次数只比最好情况多 39%。

快速排序最多需要约 $N^2/2$ 次比较,但随即打乱数组能够预防这种情况。

与其他算法相比较

总的来说,可以肯定的是对于大小为 N 的数组,快速排序的基本实现(二向切分)的运行时间在 $1.39NlgN$ 的某个常数因子的范围内。归并排序也能做到这一点,但是快速排序一般会更快。虽然它的比较次数多了 39%,但是它移动数据的次数更少。

答疑

问:随机地将数组打乱似乎占了排序用时的一大部分,这么做值得吗?
答:值得。这能够防止出现最坏情况,并且使得运行时间可以预计。它是一种(也是第一批)偏爱随机性的算法。Hoare 在 1960 年提出这个算法的时候就推荐了这种方法。

参考资源

《算法(第四版)》Robert Sedgewick 等著,第 2 章-排序

0%