8 快速排序

8.1 对快速排序的描述

快速排序是基于“分治算法”的。在《1.3.1 分治算法》里面已经介绍过的，就不重复讲了。只要记住基于“分治”的算法，一般都是主函数是个“分治”语句（if…else…）,分治块里面一般是调用本身的递归。

伪代码：
QUICKSORT(A, p, r)if p < rthen q ← PARTITION(A, p, r)QUICKSORT(A, p, q - 1)QUICKSORT(A, q + 1, r) PARTITION(A, p, r)x ← A[r]i ← p - 1for j ← p to r - 1do if A[j] ≤ xthen i ← i + 1exchange A[i] ←→ A[j]exchange A[i + 1] ←→ A[r]return i + 1


Java代码：

import java.util.Comparator; public class QuickSort {public static <T> void quickSort(T[] a, Comparator<? super T> c) {quickSort(a, c, 0, a.length);}public static <T> void quickSort(T[] a, Comparator<? super T> c, int p,int r) {if (p < r) {int q = partition(a, c, p, r);quickSort(a, c, p, q);quickSort(a, c, q + 1, r);}}public static <T> int partition(T[] a, Comparator<? super T> c, int p, int r) {T t = a[r - 1];int i = p - 1;for (int j = p; j < r - 1; j++) {if (c.compare(a[j], t) <= 0) {i++;T tmp = a[i];a[i] = a[j];a[j] = tmp;}}T tmp = a[i + 1];a[i + 1] = a[r - 1];a[r - 1] = tmp;return i + 1;}public static void main(String[] args) {Integer[] temp = new Integer[] { 2, 8, 7, 1, 3, 5, 6, 4 };quickSort(temp, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}});for (int i : temp) {System.out.print(i + " ");}System.out.println();} }


输出：
1 2 3 4 5 6 7 8


code后感
快速排序已经被讨论得太多。所以，反而没有什么可写的了。PARTITION函数如何对子数组进行划分，在《算法导论》里面说得也很清楚。
值得玩味的是，《算法导论》第一版里面的伪代码用while来做循环，第二版是for来循环。伪代码我是照英文版第二版来的，所以，包括Java代码都用for来循环了。我没看出效率上两者有什么区别。
但是可读性上，while做循环的程序，就像一直以来的教科书上的样子,i和j像2个指针不断往中间靠，直到重叠在一起。似乎，可以使快速排序更容易理解一点。

细心的人，还会注意到下面的不同：
伪代码：QUICKSORT(A, p, q - 1)
我的Java代码：quickSort(a, c, p, q);
也就是，分治时，边界不同。为什么会这样？说起来有点搞。
事实上，第一版的伪代码就是：QUICKSORT(A, p, q)。是不是第二版的伪代码出错了呢？这点我也没有仔细分析。quickSort(a, c, p, q)配合for循环的PARTITION函数，再考虑到数组下标的边界情况，我的代码可以正常运行。更细的研究，没有太大的必要，都是一些加一减一的问题了。



8.3 快速排序的随机化版本
8.2 快速排序的性能一节里面，没有伪代码，被我跳过。但是，里面讲到快速排序的最坏情况，会退化成Θ(n^2)，类似于冒泡插入等排序了。为了不依赖于样本（被排序的原始序列），PARTITION执行前追加一步随机处理，就是将p到r之间随机抽取一个值i，交换A[r]和A[i]。


伪代码：

RANDOMIZED-PARTITION(A, p, r) 1 i ← RANDOM(p, r) 2 exchange A[r] ↔ A[i] 3 return PARTITION(A, p, r)RANDOMIZED-QUICKSORT(A, p, r) 1 if p < r 2 then q ← RANDOMIZED-PARTITION(A, p, r) 3 RANDOMIZED-QUICKSORT(A, p, q - 1) 4 RANDOMIZED-QUICKSORT(A, q + 1, r)

Java代码：
public static <T> void randomizedQuickSort(T[] a, Comparator<? super T> c) {randomizedQuickSort(a, c, 0, a.length);}public static <T> void randomizedQuickSort(T[] a, Comparator<? super T> c,int p, int r) {if (p < r) {int q = randomizedPartition(a, c, p, r);randomizedQuickSort(a, c, p, q);randomizedQuickSort(a, c, q + 1, r);}}public static <T> int randomizedPartition(T[] a, Comparator<? super T> c,int p, int r) {int i = new Random().nextInt(r - p) + p;T tmp = a[i];a[i] = a[r - 1];a[r - 1] = tmp;return partition(a, c, p, r);}

测试代码：

 

public static void main(String[] args) {Integer[] temp = new Integer[] { 2, 8, 7, 1, 3, 5, 6, 4 };randomizedQuickSort(temp, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}});for (int i : temp) {System.out.print(i + " ");}System.out.println();}

输出：
1 2 3 4 5 6 7 8

code后感
随机化版本本身没有什么好说的，快速排序的变种之一。
但是变种的出现，是个有趣的话题。
《算法导论》通读后，如果你大部分都能搞懂了，那么我恭喜你，可以称为一个合格的程序员了。但是如果仅仅通读正文的话，那么我就很遗憾的告诉你，太可惜了，《算法导论》这本书就连习题部分都是很牛叉的。
比方说这里的STOOGE-SORT排序
伪代码：
1 if A[i] > A[j] 2 then exchange A[i] ↔ A[j] 3 if i + 1 ≥ j 4 then return 5 k ← ┕(j - i + 1)/3┙ 6 STOOGE-SORT(A, i, j - k) 7 STOOGE-SORT(A, i + k, j) 8 STOOGE-SORT(A, i, j - k)