阅读经典——《算法导论》06
顾名思义，快速排序必然是所有排序算法中最快的一个。它的最坏情况时间复杂度是Θ(n2)，但期望时间复杂度是Θ(nlgn)，而且Θ(nlgn)中隐含的常数因子非常小。
使用随机抽样的快速排序算法可以避免最坏情况的发生，在元素互异的情况下，期望时间复杂度是O(nlgn)。
算法思想
与归并排序类似，快速排序也利用了分治的思想。每一趟快速排序将整个序列分成小于x的部分，x，大于x的部分。下一趟快速排序再递归对这几个部分排序。
接下来简要介绍具体的实现方案。排序过程中维护四个区域，如下图所示。
每一趟快速排序之前选取最后一个数作为主元x，通过遍历整个序列，把“无限制”区域的数放到“小于x”或“大于x”中。下图展示了给定序列的一趟快速排序过程。
其中最后一步将主元放在了前后两部分中间。
代码实现
/**
* 使用快速排序算法对给定的数组排序
* @param arr 需要排序的数组
* @param p 指定排序区间的起始下标
* @param r 指定排序区间的结束下标
*/
public void quickSort(int[] arr, int p, int r) {
if (p < r) {
int q = partition(arr, p, r);
quickSort(arr, p, q - 1);
quickSort(arr, q + 1, r);
}
}
/**
* 快速排序中的一趟划分
* @param arr 需要排序的数组
* @param p 指定排序区间的起始下标
* @param r 指定排序区间的结束下标
* @return 划分后主元的位置
*/
public int partition(int[] arr, int p, int r) {
int x = arr[r];
int i = p - 1;
int temp;
for (int j = p; j < r; j++) {
if (arr[j] <= x) {
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i + 1];
arr[i + 1] = arr[r];
arr[r] = temp;
return i + 1;
}
完整代码见QuickSort.java。
性能分析
快速排序的运行时间依赖于划分是否平衡，而平衡与否又依赖于用于划分的元素。在最坏情况下，极度不平衡的划分（主元恰好是极大值或极小值）导致时间复杂度为Θ(n2)。比如输入数组大部分有序的情况下，快速排序速度会很低，反而插入排序速度很快。因此需要根据实际输入的情况选择排序算法。
人们想出了许多方法来尽量保证划分的平衡，比如随机取三个元素，并用这三个元素的中位数对数组进行划分。但是无论怎样，使用快速排序是有风险的，普遍的观点是，如果最差情况的性能会对你的程序造成很坏的影响，还是放弃快速排序为好。
关于时间复杂度的具体计算，随机化快速排序算法的渐近上界的证明，由于太过复杂难懂，我也无法完全理解，可以阅读原文或浏览本文文末给出了几个链接，里面有更详细的讨论。
获取文集中的全套源码请访问GitHub代码仓库Algorithm。
扩展阅读
Engineering Quicksort tef
A Killer Adversary for Quicksort M. D. MCILROY
Why is quicksort better than other sorting algorithms in practice? A question in StackExchange
