算法4 快速排序

快速排序被认为是20世纪中最重要的算法之一,在1960年由Tony Hoare(东尼·霍尔,1980年的图灵奖得主)提出,快速排序流行的原因是它实现起来简单,适用于各种不同的输入数据,并且在一般应用中比其他排序算法都要快。

快速排序的实现方式和归并排序都是使用分治法的排序算法,排序时间都和cNlogN成正比。但实际上快速排序要快不少,因为它的常数c要小很多,主要原因是它的元素交换次数较少。它很接近排序算法的终极目标,唯一的缺点就是快速排序并不是稳定的排序算法。

快速排序是一种偏爱随机性的排序算法,也就是序列的随机程度越高,快速排序的性能就越稳定。所以实现快速排序的第一步就是需要保证输入的随机性,通常情况下我们会花费线性的时间打乱数组的顺序,以保证快速排序的性能。

打乱数组(Knuth洗牌算法)

不要以为打乱一个数组很简单,你以为打乱了,实际上并不够均匀。

我之前在Coursera上有个作业的做法是将数组分成两半,随机交换左半边和右半边的元素 N/2次,然而作业提交后Coursera检测出数组随机度不够导致扣了1分,这个作业就是栈和队列那篇文章中RandomizedQueue。

Fisher–Yates shuffle 也称为 Knuth shuffle,是一种随机洗牌算法。算法将数组看成两部分:未打乱的部分和已打乱的部分,从未打乱的部分中随机选择一个元素放入已打乱的部分中。

1
2
3
4
5
6
7
8
public static void shuffle(Object[] a, int lo, int hi) {
for (int i = lo; i < hi; i++) {
int r = i + uniform(hi-i); // between i and hi-1
Object temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}

实现思路

实现快速排序的基本思路如下:

  • 随机打乱数组
  • 切分数组,对于某个索引j
    • a[j]已排定;
    • a[j]左边没有比它自身大的元素;
    • a[j]右边没有比它自身小的元素
  • 递归的切分更小的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void sort(Comparable[] a) {
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
}

private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int j = partition(a, lo, hi); // 切分
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}

private static int partition(Comparable[] a, int lo, int hi) {
// 看下面代码
}

切分方式

实现切分时,一般是随意的选取a[lo]作为切分元素:

  • 从左到右的扫描a[i] < a[lo],找到不符合条件的i
  • 从右到左的扫描a[j] > a[lo],找到不符合条件的j
  • 交换a[i]a[j]

重复以上步骤直到指针ij相遇,交换a[j]a[lo],具体如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
Comparable v = a[lo];
while (true) {
while (less(a[++i], v)) if (i == hi) break;
while (less(v, a[--j])) if (j == lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
}

递归跟踪图:

演示动画:

可以看出对于重复元素较多的输入,快速排序性能较差,这是后续需要优化的点。

实现快速排序的几个要点:

原地切分:如果使用一个辅助,可以更加容易的实现切分,但将切分后的数组赋值回去的开销也许会使我们得不偿失,为何不直接使用归并排序呢?

保持随机:数组元素的顺序是被打乱过的,它的所有子数组也是随机排序的,保持随机性的另一种方式是在切分时随机的选择一个切分元素。

重复元素:需要注意的是处理切分元素值有重复的情况,左侧的扫描最好是遇到大于等于切分元素时停下,右侧扫描则是遇到小于等于切分元素时停下。否则对于处理重复元素非常多的情况下,可能导致算法的运行时间变为平方级(下面的“改进3”分析此原因)。

性能分析

最好的情况是每次切分都正好等平分左右两边的子数组,和归并排序的递归跟踪图相似,比较次数为 ~ NlogN​

最差的情况是每次切分时左边或右边的子数组其中之一为空,比较次数为 ~ :

这也是为什么我们必须打乱数组的原因,能够防止出现最坏的情况并使得运行时间可以预计,霍尔在1960年提出这个算法时就推荐了这种方式,它是一种(也是第一批)偏爱随机性的算法。

而平均情况下将长度为N的无重复元素的数组排序,快速排序平均需要2NlnN次比较以及1/3(NlnN)次交换,其中 2NlnN约等于1.39NlgN。(这其中存在较为复杂的数学证明,由于能力优先就不嫌丑了)

和归并排序对比

对于长度为N的无重复数组,快速排序平均需要1.39NlgN次比较,这比归并排序要多不少。但实际情况是快速排序要比归并排序更快,因为它使用了更少的交换次数,从下图可以看出大约快了30%.

另外,快速排序是不稳定的,因为在切分时会打乱稳定性,如下所示:

改进1: 不切分小数组

和归并排序一样,对于小数组直接使用插入排序:

1
2
3
4
5
6
7
8
9
10
private static void sort(Comparable[] a, int lo, int hi) {
// if (hi <= lo) return;
if (hi <= lo + M) {
Insertion.sort(a, lo, hi);
return;
}
int j = partition(a, lo, hi); // 切分
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}

M值取5-15之间的任意值在大多数情况下都是不错的。

改进2:取样中位数作为切分元素

使用子数组的一小部分元素的中位数来切分数组,这样的切分更好,但代价是需要计算中位数。

人们发现将取样大小设为3并使用其中位数来切分的效果最好。

1
2
3
4
5
6
private static int partition(Comparable[] a, int lo, int hi) {
int n = hi - lo + 1;
int m = median3(a, lo, lo + n/2, hi);
exch(a, m, lo);
// ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static int median3(Comparable[] a, int i, int j, int k) {
if(less(a[i], a[j])) {
if(less(a[j], a[k])) return j;
else if(less(a[i], a[k])) return k;
else return i;
} else {
if (less(a[k], a[j])) return j;
else if (less(a[k], a[i])) return k;
else return i;
}

// 三元运算符的方式
//return (less(a[i], a[j]) ?
// (less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) :
// (less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i));
}

改进3:三向切分

前面说过,对于大量重复元素的输入,如果切分时没有在正确的位置停止扫描,将使得算法的性能变为平方级。

例如下面两组数据,遇到和切分元素相同的元素不停止扫描时:

对于所有元素均重复的情况,切分不均匀,另一半数组永远被认为是空的,所以需要~ 次比较,。


假设遇到和切分元素相同的元素时停止扫描:

对于所有元素均重复的情况,切分刚好是平分的,所以需要~ NlgN次比较。但即使正确的停下扫描,这种切分方式依然存在非常大的改进空间,因为上面的例子中所有元素相同时,存在无意义的元素交换(A和A交换了5次)。


理想的情况应该是相同的元素放在一起:

对于三向切分,很容易想起一个算法题——荷兰国旗。

  • ltgt间的元素和切分元素相同
  • 左边没有比lt更大的元素
  • 右边没有比gt更小的元素

荷兰国旗解法如下:我们需要三个指针,lt指向首位,gt指向末尾,c则是遍历用的游标。

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
// 初始状态,lt指针指向首位,gt指向末位
c
l         g
3 2 1 1 2 3

// 游标指向的元素大于2,和gt交换元素,并且gt左移一位。表示gt指针右边的元素是已排序的
c
l       g
3 2 1 1 2 3

// 游标指向的元素大于2,和gt交换元素,并且gt左移一位。表示gt指针右边的元素是已排序的
c
l     g
2 2 1 1 3 3

// 游标指向的元素等于2,移动游标。
l c   g
2 2 1 1 3 3

// 游标指向的元素等于2,移动游标。
l   c g
2 2 1 1 3 3

// 游标指向的元素小于2,和lt交换元素,并且lt右移一位,表示指针右边的元素是已排序的
// 此时c也要跟着右移,因为和lt交换元素后,c必然小于等于2。
    c
l   g
1 2 2 1 3 3

// 游标指向的元素小于2,和lt交换元素,并且lt和游标右移一位。游标大于gt指针,跳出循环。
      c
  h t
1 1 2 2 3 3

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, gt = hi;
Comparable v = a[lo];
int i = lo;
while (i <= gt) {
if (a[i].compareTo(v) < 0) exch(a, lt++, i++);
else if (a[i].compareTo(v) > 0) exch(a, i, gt--);
else i++;
}
// lt和gt之间的元素相同,三向切分
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}

三向切分的快速排序的可视轨迹:

动画演示:

可以看出对于重复元素较多的输入,三向切分的快速排序效率非常高。

对于包含大量重复元素的随机数组,三向切分快速排序的时间能从线性对数级降低到线性级的。