2.3 Quicksort：随机切分、性能边界与熵最优三向排序

2.3 · Quicksort覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

  • 能解释“2.3 · Quicksort”如何用随机打乱、切分不变量和三向切分解释快速排序的平均性能与重复键边界
  • 能逐项核对 快速排序、切分、随机打乱、性能特征、三向切分快速排序、熵最优排序，并区分作者站内容与本页独立补充
  • 能按“随机排列下比较次数约 2N ln N；三向切分把等值区一次固定”手算一个最小输入，逐步检查“切分结束时 a[lo..j-1]≤v、a[j]=v、a[j+1..hi]≥v，元素多重集不变”
  • 能注入“省略随机打乱却固定取首元素为 pivot，使已有序输入递归深度达到 N”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“2·3 · Quicksort”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“2·3 · Quicksort”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“2·3 · Quicksort”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：2.3 · Quicksort

  • 1. 快速排序：在本页通过“随机打乱输入”连接解释、交互状态和练习验收。
  • 2. 切分：在本页通过“选择切分元素”连接解释、交互状态和练习验收。
  • 3. 随机打乱：在本页通过“推进左右指针”连接解释、交互状态和练习验收。
  • 4. 性能特征：在本页通过“固定切分位置”连接解释、交互状态和练习验收。
  • 5. 三向切分快速排序：在本页通过“递归并核对结果”连接解释、交互状态和练习验收。
  • 6. 熵最优排序：在本页通过“随机打乱输入”连接解释、交互状态和练习验收。

从“第一个元素碰巧是最小值”开始

快速排序（quicksort）把大部分工作放在递归前的partition，而归并排序把大部分工作放在递归后的merge。若每次pivot接近中位数，递归树浅且每层线性；若每次pivot都是minimum，问题只缩短一项，比较量变成平方级。

先预测输入已升序时，直接把首项作为pivot会发生什么。每轮pivot都是minimum，左区为空、右区只少一个元素，递归深度接近N。官方 Quick.sort 因此先做随机打乱（random shuffling），让性能不再受外部输入顺序支配。

官方2.3覆盖 Basic algorithm、Partitioning、Implementation details、Performance characteristics、Improvements、Visualization、Entropy-optimal sorting。Quicksort受欢迎是因为原地、inner loop短、平均N log N，但它的保证是随机概率模型下的平均行为，不是mergesort式worst-case bound。

2.3.1 Basic algorithm：shuffle、partition、排除pivot

标准流程先shuffle整数组，再排序closed interval a[lo..hi]。Partition返回j并保证pivot已在最终rank；递归只能处理 lo..j-1 和 j+1..hi，必须排除j。

public static void sort(Comparable[] a) {
    StdRandom.shuffle(a);
    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);
    assert isSorted(a, lo, hi);
}

正确性用partition postcondition归纳：a[j] 已在最终位置；左侧没有大于它的key，右侧没有小于它的key；recursive calls分别把两侧排好后，全区间非降且permutation不变。Termination依赖partition每次固定至少一个位置并从两个children排除它。

Preserving randomness也属于proof premise。Uniform shuffle后，subarray保留相对随机顺序；使用首项pivot等价于从该subarray均匀选pivot。另一设计是在每次partition中随机选一个index并与lo交换，但不能既省略shuffle又永远使用可被输入控制的首项，还宣称相同平均保证。

2.3.2 Partitioning：双向扫描与交叉点

切分（partitioning）使用 v=a[lo]、left scan i和right scan j。Left寻找大于等于v的item，right寻找小于等于v的item；未交叉时两者都处于错误侧，交换后继续。

private static int partition(Comparable[] a, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    Comparable v = a[lo];
 
    while (true) {
        while (less(a[++i], v))
            if (i == hi) break;
        while (less(v, a[--j]))
            if (j == lo) break;
 
        if (i >= j) break;
        exch(a, i, j);
    }
    exch(a, lo, j);
    return j;
}

Loop过程中，a[lo+1..i-1] 都不大于pivot，a[j+1..hi] 都不小于pivot，i到j之间尚未分类。Pointers交叉时，j是left side最右位置；把pivot与 a[j] 交换后，pivot final，三段postcondition成立。

Bounds很微妙。若pivot是largest，left scan可一直走到hi，必须有right boundary check；right scan有 a[lo] 作为sentinel，官方仍保留说明性boundary logic。Empty/single interval在调用partition前被base case挡住。把closed和half-open intervals混用，常导致读取 a[hi+1] 或漏掉最后项。

2.3.3 Equal keys：扫描要停，不是跳过

双向partition遇到equal pivot key时，两侧scan都应停止，必要时交换两个equal items。看似多余，却能让大量相等keys时partition保持平衡。若left scan越过所有equal keys，all-equal input每次会切成0与N-1，重现平方级退化。

官方标准two-way版本在N个all-equal items上约做N lg N compares，因为i与j从两端相向停止，subproblems近乎均分；但它仍反复递归处理equal items。Three-way版本会在一次linear pass后把整个equal band完成，因此可进一步降到linear。

Quicksort通常不稳定。Partition的远距离exchanges可让equal records跨越；shuffle本身也打乱equal identity order。若业务要求stable，不应只修改一个tie branch后宣称完成，必须重新设计partition或保留原index作secondary key，并重新评估space与comparison contract。

2.3.4 Performance characteristics：平均快，最坏仍平方

性能特征（performance characteristics）来自pivot rank递归。对distinct keys，官方命题给出平均比较：

E[CN]∼2Nln⁡N\mathbb E[C_N]\sim 2N\ln N

平均exchanges约为compares的六分之一。Standard deviation约为 0.65N，相对N log N平均值随N增长而减小，因此大N运行时间通常集中在平均附近。Random shuffle使特定外部排列不能稳定触发坏pivot链，但随机事件仍不是形式上的worst-case elimination。

最坏情况下每次只固定一个extreme pivot：

Cworst(N)=(N−1)+(N−2)+⋯+1=N(N−1)2C_{\mathrm{worst}}(N) =(N-1)+(N-2)+\cdots+1 =\frac{N(N-1)}{2}

相应recursion stack也可能达到Theta(N)，不仅慢，还可能stack overflow。平衡切分则满足：

T(N)=2T(N/2)+Θ(N)=Θ(Nlog⁡N)T(N)=2T(N/2)+\Theta(N)=\Theta(N\log N)

“In-place”指partition不分配N-length copy；recursive stack仍是auxiliary space。Average stack depth为Theta(log N)，worst为Theta(N)。生产实现可先递归较小partition、对较大partition用loop继续，把stack depth控制到log N，即使时间仍可能平方。

2.3.5 Improvements、visualization与selection

官方列出两类常见改进。第一，对size 5到15附近的小subarray切换insertion sort，减少recursive overhead；cutoff要按system benchmark。第二，用lo、middle、hi三项的median作为pivot，通常改善partition quality，但要支付sample comparisons。Current QuickX 使用median-of-three与cutoff 8。

Visualization应显示pivot、i/j scans、已分类边界、交换和递归区间，而不只展示柱高。真正有诊断价值的trace会检查每次partition后：

  1. j落在lo到hi；
  2. 左侧所有keys不大于pivot；
  3. 右侧所有keys不小于pivot；
  4. frequency map与调用前一致；
  5. child intervals严格小于parent。

Quick.select(a,k) 复用partition，只沿包含rank k的一侧继续，因此randomized average time linear：

while (hi > lo) {
    int j = partition(a, lo, hi);
    if      (j > k) hi = j - 1;
    else if (j < k) lo = j + 1;
    else            return a[j];
}
return a[lo];

Select会shuffle并重排array，contract返回第k小key，不保证其他items全局sorted。K必须落在0到N-1；只验证返回value而不验证rank partition，可能漏掉duplicates或boundary bug。

2.3.6 Three-way quicksort：一次消除equal band

三向切分快速排序（three-way quicksort）解决重复keys。Dijkstra Dutch National Flag loop维护四段：

  • a[lo..lt-1] 小于v；
  • a[lt..i-1] 等于v；
  • a[i..gt] 未检查；
  • a[gt+1..hi] 大于v。
int lt = lo;
int gt = hi;
Comparable v = a[lo];
int i = lo + 1;
 
while (i <= gt) {
    int cmp = a[i].compareTo(v);
    if      (cmp < 0) exch(a, lt++, i++);
    else if (cmp > 0) exch(a, i, gt--);
    else              i++;
}
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);

Greater case与gt交换后不能增加i，因为换入 a[i] 的item尚未检查；less case交换的是equal region开头，交换后该equal item进入新equal band，所以lt与i都前进。Loop结束时unknown为空，整个equal band已经final，不再递归。

2.3.7 Entropy-optimal sorting：成本随信息量下降

熵最优排序（entropy-optimal sorting）不应把64个只有两种key的items当64个distinct ranks处理。若第r种key频率为f_r、概率为p_r，frequency entropy为：

H=−∑rprlog⁡2pr,pr=frNH=-\sum_r p_r\log_2 p_r, \qquad p_r=\frac{f_r}{N}

区分multiset arrangements需要的信息量为Theta(NH)加线性项。All equal时H等于0，一次scan即可；keys接近all distinct时H接近lg N，回到N lg N。三向quicksort让equal band不再进入children，因此其比较成本对该distribution达到熵下界同阶。

“Entropy-optimal”不是stable，也不是worst-case linear；它描述重复key distribution下的comparison efficiency。仍需randomization防止distinct或skewed partitions被输入顺序操控，还要明确comparator equivalence与object equality不是同一概念：compareTo 返回0的records属于同一key class。

统一验收：从随机性到重复键分布

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“2.3 · Quicksort”的两个最小情境间切换，再逐项选择正式概念。预测“随机排列下比较次数约 2N ln N；三向切分把等值区一次固定”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

2.3 · Quicksort：对象、操作与不变量

用随机打乱、切分不变量和三向切分解释快速排序的平均性能与重复键边界

选择最小情境

切换正式概念

输入合同操作证书algs4-2.3 · 先给前提，再执行，再验收当前概念：1/6
有序输入
[1,2,3,4,5] 固定首元素切分，再与随机打乱比较
当前观察
quicksort：未打乱时产生极不平衡子问题，随机化恢复期望对数深度
随机排列下比较次数约 2N ln N；三向切分把等值区一次固定

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

  • 快速排序：在实验 1 中指出对应状态，并写出一个通过条件。
  • 切分：在实验 2 中指出对应状态，并写出一个通过条件。
  • 随机打乱：在实验 3 中指出对应状态，并写出一个通过条件。
  • 性能特征：在实验 1 中指出对应状态，并写出一个通过条件。
  • 三向切分快速排序：在实验 2 中指出对应状态，并写出一个通过条件。
  • 熵最优排序：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“随机排列下比较次数约 2N ln N；三向切分把等值区一次固定”不是孤立结论？

问题 3：故障恢复。 怎样证明“省略随机打乱却固定取首元素为 pivot，使已有序输入递归深度达到 N”已经修复？

本章回顾

  1. Quicksort先partition再递归两侧，pivot j必须进入最终位置并从children排除。
  2. Random shuffling把输入顺序影响转化为可分析的随机pivot rank序列。
  3. Two-way scans在equal keys处停止，交叉后以a[j]接收pivot。
  4. Distinct random input平均约2N ln N compares，极端pivot链仍需N平方除2。
  5. In-place partition只用constant locals，但递归栈average log N、worst N。
  6. Three-way partition维护小于、等于、未知、大于四段，并跳过整个equal band递归。
  7. Frequency entropy越低，三向quicksort越能把comparison成本从N log N降向linear。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…