发明者：Sir Charles Antony Richard Hoare
基本思想：
- 先对数据进行洗牌（Shuffle the array）
以数据a[j]为中心进行分区（Partition），使得a[j]左侧的数据都小于等于a[j]，a[j]右侧的数据都大于等于a[j]
- 分区完后递归排序
分区演示（partitioning demo）
重复操作指导i和j指针相遇
- 当a[i] < a[lo]时，令i从左往右扫描
- 当a[j] > a[lo]时，令j从右往左扫描
- 交换a[i]和a[j]
当指针相遇时
- 交换a[lo]和a[j]
Java实现
public class Quick
{
private static int partition(Comparable[] a, int lo, int hi)
{
int i = lo, j = hi + 1;
while (true)
{
while (less(a[++i], a[lo]))
if (i == hi) break; // 从左向右找到不小于a[lo]的元素 while (less(a[lo], a[--j]))
if (j == lo) break; // 从右向左找到不大于a[lo]的元素 if (i >= j) break; // 指针相遇
exch(a, i , j); // 交换 } exch(a, lo, j); // 和比较元素交换
return j; // 返回比较元素所在的下标
} public static void sort(Comparable[] a)
{
StdRandom.shuffle(a); // 先对数组进行洗牌，复杂度是N
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);
}
}
实现细节（implementation details）
- 原地分区（Partitioning in-place）：不用开辟额外的辅助数组
- 终止循环：检查两个指针是否相遇
- 边界：(j == lo)的检查是多余的，但(i == hi)的检查是必要的
- 保留随机性（Preserving randomness）：需要洗牌（Shuffling）来保证运动（Performance guarantee）
- 相同的值（Equal keys）：当存在重复的元素，最好将指针停在和比较元素相同的位置上（When duplicates are present, it is (counter-intuitively) better to stop on keys equal to the partitioning item's key.）
复杂度平均情况分析（average-case analysis）：平均复杂度为 1.39NlgN，比归并排序还快
运行特征（Performance characteristic）
- 最坏情况（Worst case）：1/2*N^2
- 几乎不会出现
- 平均情况（Average case）：比较次数约等于1.39NlgN
- 比归并排序多出39%的比较次数
- 但是由于更少的数据交换，实际中比归并排序更快
- 随机洗牌（Random shuffle）：
- 对最坏情况的概率性保证（Probabilistic guarantee）
- 经过实验验证的数学模型的基础（Basic for math model that can be validated with experiments.）
- 留心：出现以下情况时，运算是平方级的（quadratic）
- 当数组逆序排列
- 当存在多个重复元素
特性（Properties）：
- 快速排序是一种原地排序算法（in-place sorting algorithm）
- 不具有稳定性
实践上的改善（practical improvements）
改善1：使用插入排序对小的子序列进行排序
- 即使是快速排序，也对小数组有不少的开销
- 当数组大小达到10时，停止（Cutoff）插入排序
- 大概有20%的改善
private static void sort(Comparable[] a, int lo, int hi)
{
if (hi <= lo + CUFOFF -1)
{
Insertion.sort(a, lo, hi);
return;
}
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
}
改善2：使用平均数作为比较元素
- 最好的选择是比较元素刚好是中值
- 通过取样估计中值（Estimate true median by taking median of sample.）
- 对三个取样元素取平均值
- 大概有10%的改善
private static void sort(Comparable[] a, int lo, int hi)
{
if (hi <= lo) return; int m = medianOF3(a, lo, lo + (hi - lo)/2, hi);
swap(a, lo, m); int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
}