这篇文章主要介绍的是快速排序的一些公认有效的优化方法，它们中间有很多都来自于实践经验(empirical)。

在进行优化之前，我觉得必要先找到优化的起点，这里直接使用上篇文章的实现版本作为最原始的版本，如果这段代码你无法理解，请先阅读上一篇文章。看过上篇文章则可以直接跳过这部分。

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
public static void quickSort(int[] arr){
    quickSort(arr,0,arr.length - 1);
}

private static void quickSort(int[] arr,int lo,int hi){
    if(lo>=hi) return;
    int pivot=partition(arr,lo,hi);
    quickSort(arr,lo,pivot - 1);
    quickSort(arr,pivot + 1,hi);
}

/**
*直接选取第一个元素lo作为pivot，使用两个指针(i,j)扫描数组，i,j朝数组中间移动
*遇到arr[i]>=pivot则i停止，遇到arr[j]<=pivot则j停止，交换i,j对应的元素，重复该过程直到i,j相遇
*当整个过程停下来时将pivot与a[j]交换位置，从而完成分区
*
*       left part              center part           right part
* +--------------------------------------------------------------+
* lo |   <= pivot   |              ?              |   >= pivot   |
* +--------------------------------------------------------------+
* ^                 ^                             ^
* |                 |                             |
* pivot             i->                         <-j
*
*/
private static int partition(int[] arr,int lo,int hi){
    int i=lo+1,j=hi;

    while(true){
        while(arr[++i]<arr[lo] && i < hi);
        while(arr[--j]>arr[lo]); //这里不需要判断j>lo，因为当j=lo时，arr[j]>arr[lo]不可能成立
        if(i>=j) break; 		 //i,j相遇时停止
        exchange(arr,i,j);
    }

    exchange(arr,lo,j);
    return j;
}

一.在内循环中加入插入排序(cut off to insertion sort)

这其实没什么好说的，插入排序章节中已经给出了明确的解释。在快速排序，归并排序等基于递归的排序算法中都可以加入插入排序来处理小规模数组，而对“小”的定义则需要考虑具体的系统环境，编程语言等因素，算法书上给出了5-20的建议。下面是改进后的代码片段：

1
2
3
4
5
6
7
8
9
10
private static final int CUTOFF=8;
private static void quickSort(int[] arr,int lo,int hi){
    if(hi - lo + 1 <= CUTTOFF ) {
    	insertionSort(arr,lo,hi);
        return;
    }
    int pivot=partition(arr,lo,hi);
    quickSort(arr,lo,pivot - 1);
    quickSort(arr,pivot + 1,hi);
}

二.三数中值切分(median of three partitioning)

在原始版本中我们直接使用数组的第一个元素作为pivot(枢纽元)，成功的在数组已经预排序的情况下将复杂度提升到了平方级，这意味着消耗大量时间却什么也没干。针对这个问题大家尝试了一些解决方案：

  • 数组中间随机挑一个元素作为pivot，不得不说这在实践中比直接选取第一个元素要好，但如果输入数组是随机的，数组已经预排序的概率与其它分布情况一致，则该方法起不到任何效果，反而还要消耗生成随机数的时间。
  • 寻找数组的中位素(median)，每次都使用中位数作为pivot是快速排序的最好情况，但实践中发现在内循环中寻找中位数的开销远远大于其省下来的时间。
  • 既然寻找整个数组的中位数不靠谱，那要不试试在数组中随机取三个数，再取它们的中位数作为pivot?oh!It works!I'm such a genius!...实践证明这种方法非常不错，然而在查到的资料中都没有明确的说明为什么，它们给出的解释大多都是“实验证明(empirical)”。
  • 没有三取样解决不了的问题，如果有，那就取九个，在我的算法书上称其为"Tukey's ninther"，又称"median of medians"。即先选出三组元素，每组三个，分别取三组元素的中位数，再从这三个中位数中取其中位数作为pivot，这在输入数组比较大时，进一步降低了切分不均匀的概率。

也许关于这个问题我的描述带有过多的调侃成分，这完全出于我没有办法量化三数中值切分所带来的好处，而我又不想给出一个模棱两可的回答，《数据结构与算法分析》这本书说采取三数中值切分减少了快速排序大约5%的时间，请你也尝试说服自己接受这个答案。无论如何它总归可以避免快速排序沦为平方级算法，下面是改进后的代码片段：

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
private static void quickSort(int[] arr,int lo,int hi){
    int length=hi-lo+1;

    if(length <= CUTTOFF ) {
    	//use insertionSort
    	insertionSort(arr,lo,hi);
        return;
    }else if(length <= 40){
    	//use median of three
    	int m = median3(arr, lo, lo + N>>1, hi);
        exchange(arr, lo, m);
    }else {
    	//use median of medians
    	int eps = N/8;
        int mid = lo + N>>1;
        int m1 = median3(arr, lo, lo + eps, lo + eps + eps);
        int m2 = median3(arr, mid - eps, mid, mid + eps);
        int m3 = median3(arr, hi - eps - eps, hi - eps, hi);
        int ninther = median3(arr, m1, m2, m3);
        exchange(arr,lo,ninther);
    }

    int pivot=partition(arr,lo,hi);
    quickSort(arr,lo,pivot - 1);
    quickSort(arr,pivot + 1,hi);
}

private static int median3(int[] arr,i,j,k){
    return  (arr[i] < arr[j] ?
            (arr[j] < arr[k] ? j : arr[i] < arr[k] ? k : i):
            (arr[j] < arr[k] ? k : arr[i] < arr[k] ? i : k));
}

三.三向切分快速排序(three way quick sort)

实际应用中，数组常常包含一些重复元素，到目前为止我们的排序算法在应对这种数组时显然是不够优化的，即便是处理一个全是重复元素的数组，我们的算法还是把它视为普通输入一样切分，递归。而三向切分快速排序正是用于处理这个问题，它将数组切分成三部分，分别是小于pivot，等于pivot，大于pivot。在之前的实现中，每次递归至少能保证将pivot元素放在正确的位置，而应用此项改进后，每次都能将所有等于pivot的元素放到正确位置。在研究它的思路之前，可以先来看看由Dijkstra提出的Dutch National Flag Problem(荷兰国旗问题)，下面是简单描述版本。
假设一个数组分别由A,B,C三个元素组成，三个元素随机排列，且每个元素的个数不确定，应该如何重新排列该数组使其恢复有序?
Example:
Input=[A,B,B,C,A,C,B];
Output=[A,A,B,B,B,C,C];
这样看起来问题非常简单，使用一个指针按顺序扫描数组，遇到A则将其换到左边，遇到C则将其换到右边。这跟最原始的三向切分思路一模一样，下面是其实现代码，你也可以在JDK1.7以上版本双枢纽快速排序(Dual-Pivot-Quick-Sort)源码中看到它(不过只有在特定情形下才会调用它)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 *   left part    center part              right part
 * +--------------------------------------------------+
 * lo|  < pivot  |   == pivot   |     ?    |  > pivot |
 * +--------------------------------------------------+
 *               ^              ^          ^
 *               |              |          |
 *              less            k        great
 */
int pivot=lo,less=lo,great=hi;

for (int k = lo+1; k <= great; k++) {
    if(arr[k]==pivot) continue;

    if(arr[k]<pivot){
        exchange(arr,k,less++);
    } else{
        while (arr[great]>pivot) great--;
        exchange(arr,k,great--);
    }
}
sort(arr,lo,less - 1);
sort(arr,great + 1,hi);

如果你急不可耐的在我们的快排版本中加入以上代码，并使用随机生成的数组进行测试，你会发现它几乎没什么卵用，因为它的内循环中明显增加了元素间的交换次数，只要k指针遇到的元素不等于pivot，都会被交换。除非你的快速排序仅用于解决上面的荷兰旗帜问题，否则应用这段代码不会对效率有什么帮助，因为实际应用中大部分元素都不会等于pivot。
正因为上面的问题，该项策略一直不太流行，直到90年代，Jon Bentley与Douglas McIlroy使用了一个非常聪明的办法解决了这个问题，既然交换不相等的元素开销过大，为什么不改成交换相等的元素？下面是应用了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
37
38
39
40
/*
 * Three Way Partitioning
 * By Bently and McIlroy
 *
 *   left part            center part          right part
 * +-------------------------------------------------------+
 * lo|  = pivot  |  < pivot  |  ?  |  > pivot  |  = pivot  |
 * +-------------------------------------------------------+
 *               ^           ^     ^           ^
 *               |           |     |           |
 *             less->        i->  <-j        <-great
 *
 */
int less=lo,great=hi+1;

while(arr[++less]=arr[lo] && less<hi);
while(arr[--great]=arr[lo] && great>less);

int i=less-1,j=great+1;

while (true) {
    while(arr[++i]<arr[lo] && i<hi);
    while(arr[--j]>arr[lo]);

    if(i==j) exchange(arr,i,less++);
    if(i>=j) break;
    exchange(arr,i,j);

    //这里暂时将与pivot相等的元素换到数组的两端
    if(arr[i]=arr[lo]) exchange(arr,i,less++);
    if(arr[j]=arr[lo]) exchange(arr,j,great--);
}

//这里将与pivot相等的元素换到正确位置
i=j+1;
for (int k = lo; k < less; k++) exchange(arr,k,j--);
for (int k = hi; k > great; k++) exchange(arr,k,i++);

sort(arr,lo,j);
sort(arr,i,hi);

到这里快速排序的主要优化就已经结束了。

本文参考链接：