Blog地址：
《算法导论的Java实现》 8 快速排序
8 快速排序
8.1 对快速排序的描述
快速排序是基于“分治算法”的。在《1.3.1 分治算法》里面已经介绍过的，就不重复讲了。只要记住基于“分治”的算法，一般都是主函数是个“分治”语句（if…else…）,分治块里面一般是调用本身的递归。
伪代码：
- Java code
QUICKSORT(A, p, r) if p < r then q ← PARTITION(A, p, r) QUICKSORT(A, p, q - 1) QUICKSORT(A, q + 1, r)PARTITION(A, p, r) x ← A[r] i ← p - 1 for j ← p to r - 1 do if A[j] ≤ x then i ← i + 1 exchange A[i] ←→ A[j] exchange A[i + 1] ←→ A[r] return i + 1
Java代码：
- Java code
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>() { @Override public 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]。
伪代码：
- Java code
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 < r2 then q ← RANDOMIZED-PARTITION(A, p, r)3 RANDOMIZED-QUICKSORT(A, p, q - 1)4 RANDOMIZED-QUICKSORT(A, q + 1, r)
Java代码：
- Java code
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); }