量化交易中文教材

第 07 章 快速排序

学习目标

  1. 能写出快速排序与 Lomuto 划分，并用四区域循环不变式证明划分正确。
  2. 理解划分平衡性如何决定运行时间：最坏 \(\Theta(n^2)\)、最好 \(\Theta(n\lg n)\)，以及"任何常数比例划分都是 \(O(n\lg n)\)"。
  3. 掌握随机化快速排序期望 \(O(n\lg n)\) 的指示器变量证明：\(z_i\) 与 \(z_j\) 被比较的概率是 \(2/(j-i+1)\)。
  4. 熟悉工程改进：Hoare 划分、三路划分处理重复值、三数取中、小数组转插入排序、小侧递归控制栈深。
  5. 知道金融数据中哪些情形会让朴素快速排序退化（已排序的时间序列、离散价格的大量重复值），以及何时必须用稳定排序。

读前导读

这一章在解决什么问题

快速排序是实践中用得最多的排序算法，numpy.sort、C++ 的 std::sort 默认都以它为主干。它的思路非常朴素：挑一个"标杆"（主元），把比它小的放左边、比它大的放右边，然后对左右两堆分别重复同样的事。 这像给一批股票分档：先拿市值中位附近的某只股票当分界线，大于它的归入大盘组、小于它的归入小盘组；每组内部再找一只分界股继续细分，直到每组只剩一只。分完了，顺序也就排好了，不需要最后再"合并"。

它快不快，全看分界线选得好不好：

  • 每次都正好劈成两半：递归 \(\lg n\) 层，每层把所有元素扫一遍，总计 \(n\lg n\)，数据翻倍耗时略多于 2 倍。
  • 每次都选到最极端的那个（比如数据本来就排好了，偏偏总拿最后一个当标杆）：每次只分出 1 个，要分 \(n\) 层，总计约 \(n^2/2\)，数据翻倍耗时翻 4 倍。这在时间序列数据上真的会发生。

解决办法来自第 05 章：随机挑标杆。这样没有哪种输入能稳定地让它变慢，平均比较次数约 \(1.39n\lg n\)。本章最漂亮的部分是这个期望值的推导：它没有去分析复杂的递归过程，而是问一个简单问题，"第 \(i\) 小和第 \(j\) 小的两个数，在整个过程中被拿来比较过的概率是多少？"答案是 \(\frac{2}{j-i+1}\)，然后用第 05 章的"开关相加"技巧（指示器随机变量与期望的线性性）把所有数对加起来。

最后，本章讲了工程上必须注意的几件事，其中两件对金融数据特别要紧：价格只能取最小变动价位的整数倍，重复值极多，朴素快速排序会退化；以及快速排序不稳定，同价订单排序后可能打乱时间顺序。

需要先想起来的数学

  • 递归式与它的解。 \(T(n)=T(n-1)+\Theta(n)\) 解为 \(\Theta(n^2)\)，\(T(n)=2T(n/2)+\Theta(n)\) 解为 \(\Theta(n\lg n)\)，任何常数比例划分 \(T(\alpha n)+T((1-\alpha)n)+cn\) 都是 \(\Theta(n\lg n)\)。见第 04b 章，以及 第 00 册第 07 章 概率中的分析工具 中的大 O 一节。
  • 指示器随机变量与期望的线性性。 "某事平均发生几次 = 每个可能发生点的概率之和"，不要求独立。见第 05 章 5.2 节。
  • 调和数。 \(H_n=1+\frac12+\cdots+\frac1n\approx\ln n+0.577\)；\(\ln n\approx0.693\lg n\)。例：\(n=1000\) 时 \(H_n\approx7.49\)。详见 第 00 册第 04 章 级数与收敛。
  • 二次函数的最值。 \(f(q)=q^2+(n-q-1)^2\) 是开口向上的抛物线，在区间上的最大值一定出现在端点。例：\(n=5\) 时 \(q\) 取 0..4，\(f\) 依次为 16、10、8、10、16。
  • 定积分（只在三数取中处用到）。 \(\int_a^bf(t)\,dt\) 是曲线下的面积，这里用来算连续近似下的概率。详见 第 00 册第 03 章 积分。

怎么读这一章

7.1 节（Lomuto 划分）务必拿纸跟着原书例子一步步走，理解了"四个区域"就理解了快速排序。7.2 节的直观分析是核心中的核心，尤其是"任何常数比例划分都是 \(n\lg n\)"。7.3 节很短。7.4.1 节最坏情况的证明可以只看结论；7.4.2 节期望分析的"第三步"是全章最精彩的论证，建议慢读，第四步的求和和"另一种分析"可以第二遍再看。7.5 节挑三路划分、小侧递归、introsort 三段读即可，Hoare 划分和模糊排序可以跳过。量化实战两段的文字解读一定要读，特别是稳定性那一条。

7.1 算法描述

分治结构

快速排序（quicksort）也是分治法（第 01 章、第 04a 章），但工作量的分布与归并排序相反：归并排序"分"得随意、"合"得辛苦；快速排序"分"得辛苦、"合"不需要任何工作。对子数组 \(A[p..r]\)：

  • 分解：把 \(A[p..r]\) 重排成 \(A[p..q-1]\)、\(A[q]\)、\(A[q+1..r]\) 三段，使左段每个元素 \(\le A[q]\)，右段每个元素 \(\ge A[q]\)。下标 \(q\) 由划分过程算出。
  • 解决：递归地排序两段。
  • 合并：什么都不用做，\(A[p..r]\) 已经有序。
QUICKSORT(A, p, r)
1  if p < r
2      q = PARTITION(A, p, r)
3      QUICKSORT(A, p, q - 1)
4      QUICKSORT(A, q + 1, r)
// 初始调用 QUICKSORT(A, 1, A.length)

Lomuto 划分

PARTITION(A, p, r)
1  x = A[r]                    // 主元（pivot）
2  i = p - 1
3  for j = p to r - 1
4      if A[j] <= x
5          i = i + 1
6          exchange A[i] with A[j]
7  exchange A[i + 1] with A[r]
8  return i + 1

PARTITION 总以最后一个元素 \(x=A[r]\) 为主元（pivot element）。运行时数组被分成四个区域（原书图 7.2），这就是循环不变式：第 3–6 行每次迭代开始时，对任意下标 \(k\)，

  1. 若 \(p\le k\le i\)，则 \(A[k]\le x\)；
  2. 若 \(i+1\le k\le j-1\)，则 \(A[k]>x\)；
  3. 若 \(k=r\)，则 \(A[k]=x\)。

\(A[j..r-1]\) 是尚未检查的区域，与 \(x\) 无已知关系。

  • 初始化：\(i=p-1\)、\(j=p\)，前两个区域为空，第 1 行保证条件 3。
  • 保持：若 \(A[j]>x\)，只把 \(j\) 加 1，条件 2 对新纳入的 \(A[j-1]\) 成立；若 \(A[j]\le x\)，先把 \(i\) 加 1，交换 \(A[i]\) 与 \(A[j]\)，再 \(j\) 加 1。交换后 \(A[i]\le x\) 满足条件 1，被换到 \(A[j-1]\) 的元素原本在"大区"里，满足条件 2。
  • 终止：\(j=r\)，每个元素都落在"\(\le x\)""\(>x\)""\(=x\)（仅主元）"三类之一。

第 7 行把主元与大区的第一个元素交换，主元归位，返回其下标。实际上划分后 \(A[q]\) 严格小于右段每个元素。for 循环执行 \(n-1\) 次、每次常数时间，所以 PARTITION 在 \(n=r-p+1\) 个元素上是 \(\Theta(n)\)（练习 7.1-3）。

例（原书图 7.1）：\(A=\langle2,8,7,1,3,5,6,4\rangle\)，主元 \(x=4\)。2 与自身交换进入小区；8、7 进入大区；1 与 8 交换；3 与 7 交换；5、6 进入大区；最后 4 与 \(A[i+1]=7\) 交换，得 \(\langle2,1,3,4,7,5,6,8\rangle\)，返回 \(q=4\)。

推导拆解：把这个例子逐步摊开，用竖线 | 分隔"小区 | 大区 | 未检查 | 主元"。\(i\) 指向小区最后一个位置，\(j\) 指向下一个待检查的元素。 开始：| | 2 8 7 1 3 5 6 | 4 （两区皆空） \(j=1\)，2 ≤ 4：小区扩一格，2 与自己交换。2 | | 8 7 1 3 5 6 | 4 \(j=2\)，8 > 4：只把 \(j\) 后移，8 自动并入大区。2 | 8 | 7 1 3 5 6 | 4 \(j=3\)，7 > 4：同上。2 | 8 7 | 1 3 5 6 | 4 \(j=4\)，1 ≤ 4：小区扩一格，新位置上原本是大区第一个元素 8，把它和 1 对调，等于把 8 挪到大区末尾。2 1 | 7 8 | 3 5 6 | 4 \(j=5\)，3 ≤ 4：同理，3 与 7 对调。2 1 3 | 8 7 | 5 6 | 4 \(j=6,7\)，5、6 > 4：并入大区。2 1 3 | 8 7 5 6 | | 4 收尾：主元 4 与大区第一个元素 8 对调，落在两区之间。2 1 3 4 7 5 6 8 核心技巧是"小的来了就和大区的排头对调"：大区整体往右滑一格，内部顺序被打乱也无所谓，因为我们只关心它们都大于主元。每个元素只看一次，所以是 \(\Theta(n)\)。

一个值得记住的细节（练习 7.1-2）：如果所有元素都相同，每个 \(A[j]\le x\) 都成立，PARTITION 返回 \(q=r\)，划分出 \(n-1\) 和 0——这是最坏划分。7.5 节的三路划分专门解决这个问题。

7.2 性能的直观分析

快速排序的速度完全取决于划分是否平衡，而平衡与否取决于主元选得好不好。

最坏划分：每次都分成 \(n-1\) 和 \(0\)。划分代价 \(\Theta(n)\)，\(T(0)=\Theta(1)\)：

\[ T(n)=T(n-1)+T(0)+\Theta(n)=T(n-1)+\Theta(n)=\Theta(n^2). \]

更糟的是，用最后一个元素当主元时，输入已经有序恰恰触发这种情况，而插入排序在有序输入上只要 \(O(n)\)。

推导拆解：把 \(T(n)=T(n-1)+cn\) 一层层展开：\(T(n)=cn+c(n-1)+c(n-2)+\cdots+c\cdot1=c\frac{n(n+1)}{2}\)，所以是 \(\Theta(n^2)\)。直观地说，第一次划分扫 \(n\) 个元素只"搞定"了 1 个（主元），下一次扫 \(n-1\) 个又只搞定 1 个……每次只前进一步，却每次都要全量扫描。对比一下：已排序的 1 万条时间序列，这样做约要比较 5000 万次；均匀划分只要约 13 万次。数据翻倍，前者翻 4 倍。

最好划分：每次分成两个不超过 \(n/2\) 的子问题，\(T(n)=2T(n/2)+\Theta(n)=\Theta(n\lg n)\)。

常数比例划分：设每次都按 9:1 划分（看起来很不平衡）：

\[ T(n)=T(9n/10)+T(n/10)+cn. \]

画递归树（原书图 7.4）：深度 \(\log_{10}n\) 之前每层代价都是 \(cn\)，之后每层不超过 \(cn\)；树在深度 \(\log_{10/9}n=\Theta(\lg n)\) 处结束。总代价 \(O(n\lg n)\)。99:1 也一样。任何常数比例的划分都给出深度 \(\Theta(\lg n)\)、每层 \(O(n)\) 的递归树，因而是 \(O(n\lg n)\)——常数比例只影响对数的底数，也就是常数因子。

平均情况的直觉：假设输入的所有排列等可能。随机输入上，PARTITION 约 80% 的时候产生比 9:1 更平衡的划分（练习 7.2-6：比 \((1-\alpha):\alpha\) 更平衡的概率约 \(1-2\alpha\)）。好坏划分随机混在树里。设想最坏的混法——坏划分与好划分逐层交替（原书图 7.5）：根上一次坏划分得到 \(n-1\) 和 0，下一层的好划分把 \(n-1\) 分成 \((n-1)/2-1\) 和 \((n-1)/2\)。两层合计代价 \(\Theta(n)+\Theta(n-1)=\Theta(n)\)，效果并不比一次直接分成两个 \((n-1)/2\) 差。坏划分的代价被随后的好划分"吸收"了，于是交替情形仍是 \(O(n\lg n)\)，只是常数稍大。

7.3 随机化快速排序

平均情况分析依赖"所有排列等可能"，但实际数据常常不是这样（例如按时间排好的行情、几乎有序的支票号，练习 7.2-4）。第 5 章的思路是：与其假设输入随机，不如让算法自己随机。这里用随机抽样（random sampling）：每次从 \(A[p..r]\) 中均匀随机选一个元素与 \(A[r]\) 交换，再照常划分。

RANDOMIZED-PARTITION(A, p, r)
1  i = RANDOM(p, r)
2  exchange A[r] with A[i]
3  return PARTITION(A, p, r)

RANDOMIZED-QUICKSORT(A, p, r)
1  if p < r
2      q = RANDOMIZED-PARTITION(A, p, r)
3      RANDOMIZED-QUICKSORT(A, p, q - 1)
4      RANDOMIZED-QUICKSORT(A, q + 1, r)

现在最坏情况不再由输入决定，而由随机数决定，并且极不可能发生；期望运行时间对每一个输入都成立（练习 7.3-1）。RANDOM 的调用次数无论好坏情况都是 \(\Theta(n)\)（练习 7.3-2）。

金融直觉：固定取最后一个元素当主元，就像一个公开、固定的交易规则：对手只要摸清规则就能构造出让你最难受的行情（这里是"已排好序的数据"）。随机选主元则像在执行算法里加入随机的下单时间和数量，对手无法预测，也就无法针对性地"狙击"。注意"期望 \(O(n\lg n)\)"的期望是对算法自己掷的骰子求的，不是对输入求的：哪怕输入是最刁钻的那一个，重复运行很多次的平均耗时依然是 \(n\lg n\) 量级。这比第 7.2 节"假设输入随机"的平均情况分析要强得多。

7.4 严格分析

7.4.1 最坏情况：\(\Theta(n^2)\)

设 \(T(n)\) 为最坏运行时间。PARTITION 产生规模 \(q\) 和 \(n-q-1\) 的两个子问题：

\[ T(n)=\max_{0\le q\le n-1}\big(T(q)+T(n-q-1)\big)+\Theta(n). \tag{7.1} \]

猜 \(T(n)\le cn^2\) 并代入：

\[ T(n)\le c\max_{0\le q\le n-1}\big(q^2+(n-q-1)^2\big)+\Theta(n). \]

\(q^2+(n-q-1)^2\) 关于 \(q\) 是开口向上的抛物线，最大值在端点 \(q=0\) 或 \(q=n-1\) 处取得（练习 7.4-3），等于 \((n-1)^2=n^2-2n+1\)。于是

\[ T(n)\le cn^2-c(2n-1)+\Theta(n)\le cn^2, \]

只要 \(c\) 足够大使 \(c(2n-1)\) 压过 \(\Theta(n)\) 项。所以 \(T(n)=O(n^2)\)；7.2 节的例子说明这个界能达到，故最坏 \(\Theta(n^2)\)。

推导拆解：为什么 \(q^2+(n-q-1)^2\) 在两端最大？两个子问题的规模之和固定为 \(n-1\)，而平方函数"凸"，越不均匀，平方和越大。和固定为 10 时：\(5^2+5^2=50\)，\(9^2+1^2=82\)，\(10^2+0^2=100\)。这和组合方差的道理相同：总仓位固定时，全部押在一只上，集中度指标（权重平方和，即 HHI）最大；平均分散时最小。所以"最坏划分"就是"最不分散"的划分，代入代入法后正好给出 \(cn^2\) 的上界。

7.4.2 期望运行时间：\(O(n\lg n)\)

假设元素互不相同。

第一步：把运行时间归结为比较次数。 每次调用 PARTITION 都会选出一个主元，该元素此后不再参与任何递归，所以 PARTITION 至多被调用 \(n\) 次。每次调用的代价是 \(O(1)\) 加上 for 循环的迭代次数，而每次迭代恰好做一次第 4 行的比较。

引理 7.1：设 \(X\) 为整个执行过程中第 4 行比较的总次数，则运行时间为 \(O(n+X)\)。

第二步：用指示器变量拆开 \(X\)。 把元素按大小重命名为 \(z_1<z_2<\cdots<z_n\)，令 \(Z_{ij}=\{z_i,z_{i+1},\dots,z_j\}\)。

  • 任意两个元素至多比较一次：比较只发生在主元与其他元素之间，一次划分后这个主元就退出了。
  • 令 \(X_{ij}=I\{z_i\text{ 与 }z_j\text{ 被比较}\}\)，则 \(X=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}X_{ij}\)，由期望的线性性
\[ E[X]=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\Pr\{z_i\text{ 与 }z_j\text{ 被比较}\}. \tag{7.2} \]

第三步：两个元素什么时候会被比较？ 看原书的例子：输入是 1 到 10 的某个排列，第一个主元是 7。第一次划分把它们分成 \(\{1,\dots,6\}\) 和 \(\{8,9,10\}\)。7 和所有其他数都比较过，但 2 和 9 从此分属两边，永远不会比较。一般地：

\(z_i\) 与 \(z_j\) 被比较，当且仅当 \(Z_{ij}\) 中第一个被选为主元的元素是 \(z_i\) 或 \(z_j\)。

理由：若第一个被选中的是夹在中间的某个 \(z_k\)（\(i<k<j\)），\(z_i\) 和 \(z_j\) 就被分到两边；若是 \(z_i\)（或 \(z_j\)），它作为主元会和同一划分中的所有元素比较，包括对方。在 \(Z_{ij}\) 中有元素被选为主元之前，整个 \(Z_{ij}\) 都待在同一个子数组里，因此 \(Z_{ij}\) 的 \(j-i+1\) 个元素等可能地第一个被选中。两个事件互斥：

\[ \Pr\{z_i\text{ 与 }z_j\text{ 被比较}\}=\frac{1}{j-i+1}+\frac{1}{j-i+1}=\frac{2}{j-i+1}. \tag{7.3} \]

这个式子很直观：大小相邻的两个元素（\(j=i+1\)）一定被比较（否则无法区分它们的先后）；大小相差很远的两个元素几乎不会被比较。

推导拆解：用 1 到 10 具体算两对。 2 和 9：\(Z_{2,9}=\{2,3,\dots,9\}\) 共 8 个数。只要这 8 个数里第一个被选为主元的是 3 到 8 中的某一个（6 种情形），2 和 9 就被劈到两边，再也碰不到；只有当 2 或 9 本身先被选中（2 种情形），才会比较。随机选主元下，这 8 个数谁先被选中机会均等（1、10 等区间外的数先被选中不影响它们，它们仍待在同一个子数组里），所以概率是 \(\frac28=\frac14\)。 4 和 5：\(Z_{4,5}=\{4,5\}\)，无论谁先被选中，都是 4 或 5 本身，概率 \(\frac22=1\)，一定比较。 金融直觉：可以把主元看成"分档线"。两只股票只要在分档线还没落在它们之间时，其中一只先被选为分档线，它们才会被直接比较；它们市值越接近，中间能插进来的分档线越少，被直接比较的可能就越大。

第四步：求和。 令 \(k=j-i\)，用调和级数 \(\sum_{k=1}^n 1/k=\ln n+O(1)\)：

\[ E[X]=\sum_{i=1}^{n-1}\sum_{k=1}^{n-i}\frac{2}{k+1}<\sum_{i=1}^{n-1}\sum_{k=1}^{n}\frac{2}{k}=\sum_{i=1}^{n-1}O(\lg n)=O(n\lg n). \tag{7.4} \]

结合最好情况 \(\Omega(n\lg n)\)（练习 7.4-2、7.4-4），随机化快速排序的期望运行时间是 \(\Theta(n\lg n)\)。

推导拆解：(7.4) 的三个等号或不等号分别做了什么。 第一个等号：换元。固定 \(i\)，令 \(k=j-i\)，\(j\) 从 \(i+1\) 走到 \(n\)，\(k\) 就从 1 走到 \(n-i\)，分母 \(j-i+1\) 变成 \(k+1\)。 第一个 \(<\)：两处放大。把 \(\frac2{k+1}\) 放大成 \(\frac2k\)；把上限 \(n-i\) 放大到 \(n\)（多加一些正项）。放大后内层和与 \(i\) 无关了，便于计算。 第二个等号：内层 \(\sum_{k=1}^n\frac2k=2H_n\approx2\ln n=O(\lg n)\)。 最后：外层把同一个 \(O(\lg n)\) 加 \(n-1\) 次，得 \(O(n\lg n)\)。 直观地看：对一个排在中间的元素，与它名次相差 1 的邻居一定和它比较，相差 2 的有 \(\frac23\) 的概率，相差 \(d\) 的只有 \(\frac2{d+1}\)。左右两边各加起来是一段调和级数，合计约 \(4\ln n\) 次，是对数而不是线性。每次比较牵涉两个元素，所以总比较次数约 \(\frac{n\times4\ln n}{2}=2n\ln n\)。数值例子：\(n=1000\) 时精确期望约 \(2\times1001\times7.485-4000\approx10986\) 次，与下面实验的 11035 次吻合。

如果不放缩而是精确求和（按差值 \(j-i+1=k\) 分组，共有 \(n-k+1\) 对），可得

\[ E[X]=\sum_{k=2}^{n}\frac{2(n-k+1)}{k}=2(n+1)H_n-4n\approx 2n\ln n\approx 1.39\,n\lg n, \]

其中 \(H_n=\sum_{k=1}^n1/k\)。也就是说，随机化快速排序平均只比信息论下界 \(\lg n!\approx n\lg n\)（第 08 章）多 39% 的比较——而且内循环非常简单，这正是它在实践中快的原因。下面的实验会验证这个精确值。

另一种分析（思考题 7-3）：不数比较，而对每层递归的期望时间建立递归式。第 \(q\) 小元素被选为主元的概率是 \(1/n\)，可得

\[ E[T(n)]=\frac{2}{n}\sum_{q=2}^{n-1}E[T(q)]+\Theta(n), \]

再借助不等式 \(\sum_{k=2}^{n-1}k\lg k\le\frac12n^2\lg n-\frac18n^2\)（把求和拆成 \(k<\lceil n/2\rceil\) 和 \(k\ge\lceil n/2\rceil\) 两段，前段用 \(\lg k\le\lg n-1\)）用代入法证明 \(E[T(n)]\le an\lg n\)。这种"对随机划分位置取平均"的递归式在第 09 章分析随机选择时会再次出现。

7.5 工程实现要点

教科书版本与工业级实现之间隔着一系列改进，它们大多来自原书的思考题和练习。

Hoare 划分（思考题 7-1）

Hoare 最初的划分方法用两个指针从两端相向扫描：

HOARE-PARTITION(A, p, r)
1  x = A[p]
2  i = p - 1;  j = r + 1
3  while TRUE
4      repeat j = j - 1  until A[j] <= x
5      repeat i = i + 1  until A[i] >= x
6      if i < j
7          exchange A[i] with A[j]
8      else return j

它返回的 \(j\) 满足 \(p\le j<r\)，且 \(A[p..j]\) 中每个元素都 \(\le\) \(A[j+1..r]\) 中每个元素。与 Lomuto 不同，主元并不被单独放到最终位置，而是落在两段之一里，因此递归调用应改为 QUICKSORT\((A,p,j)\) 与 QUICKSORT\((A,j+1,r)\)。Hoare 划分交换次数更少（平均约为 Lomuto 的三分之一），遇到大量相等元素时两个指针都会停下来交换，划分仍趋于平衡。它的边界条件（为什么指针不越界、为什么 \(j<r\)）极易写错，原书要求逐条证明。

三路划分：重复元素（思考题 7-2）

7.4.2 节的分析假设元素互异。如果所有元素都相等，Lomuto 划分每次都产生 \(n-1\) 和 0，随机化也救不了：运行时间 \(\Theta(n^2)\)。解决办法是三路划分 PARTITION′，返回两个下标 \(q\le t\)，使

\[ A[p..q-1]<x,\qquad A[q..t]=x,\qquad A[t+1..r]>x, \]

时间 \(\Theta(r-p)\)。之后只对两侧递归，中间等于主元的一整段不再参与。这就是 Dijkstra 的"荷兰国旗问题"。有了它，分析中的元素互异假设可以去掉：等于主元的元素不再参与后续比较，任意一对元素被比较的概率仍不超过 \(2/(j-i+1)\)。

白话解释：为什么全相等时二路划分会崩？Lomuto 的规则是"\(\le\) 主元的放左边"，所有元素都等于主元，于是全部挤到左边，右边空，每次只排掉主元一个，正是 7.2 节的最坏划分。三路划分多开一个"等于主元"的中间区，一趟扫描就把所有相等的元素一次性归位，之后只处理严格小于和严格大于的两堆。代码 partition3 用三个指针 lt、i、gt 把数组分成"小于 | 等于 | 未检查 | 大于"四段，和 Lomuto 的四区域思路一样，只是多了一个区。

金融数据里重复值多得超出直觉：价格只能落在最小变动价位上，A 股大量股票同价；停牌日价格不变、收益恰为 0；涨跌停时整片股票收益相同；评级、行业代码更是只有几十种取值。对这类数据，三路划分不是锦上添花，而是避免退化的必要条件。

主元选择

  • 随机主元：最简单的防御手段，见 7.3 节。

  • 三数取中（median-of-3，思考题 7-5）：随机抽 3 个元素取中位数做主元。设元素互异，第 \(i\) 小元素被选中的概率为

    \[ p_i=\frac{6(i-1)(n-i)}{n(n-1)(n-2)},\quad 2\le i\le n-1 . \]

    选中真正中位数的概率是普通随机法的约 \(3/2\) 倍；把"好划分"定义为主元名次在 \([n/3,2n/3]\) 之间，其概率从 \(1/3\) 提高到约 \(\int_{1/3}^{2/3}6t(1-t)\,dt=13/27\)。最坏比 \(\alpha:(1-\alpha)\) 还不平衡的概率从 \(2\alpha\) 降到 \(2(3\alpha^2-2\alpha^3)\)（练习 7.4-6）。但它只改进常数因子，不改变 \(\Theta(n\lg n)\)。

  • 用线性时间中位数做主元（练习 9.3-3）：可以把最坏情况降到 \(O(n\lg n)\)，但常数太大，实践中不用。

小数组与栈深

  • 小数组交给插入排序（练习 7.4-5）：子数组长度小于 \(k\) 时直接返回，最后对整个数组跑一遍插入排序。期望时间 \(O(nk+n\lg(n/k))\)：递归树只到深度 \(\lg(n/k)\)，而插入排序时每个元素只在自己所在的长度小于 \(k\) 的块内移动。理论上 \(k\) 取 \(O(\lg n)\) 量级，实践中靠测量，一般在 16 左右。

白话解释：先解释"栈"。程序每调用一次函数，就要在内存里开一页"工作底稿"，记下这次调用的参数和做到哪一步；函数返回时这页底稿才撕掉。递归调用自己时，底稿一页页叠上去，叠的最大高度叫"栈深"。底稿的空间有限，叠太高程序就崩溃（Python 默认上限约 1000 页）。下面这一条讲的就是如何让底稿叠得不太高。

  • 尾递归与栈深（思考题 7-4）：第二个递归调用可以改成循环。但这还不够——若每次左段都是 \(n-1\) 个元素，栈深仍是 \(\Theta(n)\)。正确做法是对较小的一侧递归、较大的一侧循环，最坏栈深降到 \(\Theta(\lg n)\)，因为每进一层递归，规模至少减半。在 Python 里这一点尤其重要：默认递归深度上限只有 1000，对已排序的 10 万条数据跑朴素递归快排会直接报错。

Introsort 与库函数

C++ std::sort 和 NumPy np.sort(kind='quicksort') 实际用的是 introsort：以快速排序为主，递归深度超过约 \(2\lg n\) 时切换为堆排序（第 06 章）兜底，小段用插入排序。这样既有快速排序的平均速度，又有堆排序的最坏 \(O(n\lg n)\) 保证。原书章末注记提到，McIlroy 曾构造"杀手对手"，能让几乎任何确定性快速排序实现退化到 \(\Theta(n^2)\)；introsort 的兜底机制正是为了防这种情况。

这些实现都不稳定。需要稳定排序时（7.6 节），NumPy 用 kind='stable'（对一般类型是 Timsort/归并，对 16 位及以下整数是基数排序），pandas 用 sort_values(kind='stable')。

模糊排序（思考题 7-6，了解即可）

如果只知道每个数落在区间 \([a_i,b_i]\) 内，模糊排序（fuzzy sorting）要找区间的一个排列，使得能在各区间里各取一点构成非降序列。算法是对左端点做快速排序的变体：选一个主元区间后，把与它重叠的区间（取它们的公共交集）都归入"相等"的中间组，只对两侧递归。一般情况期望 \(\Theta(n\lg n)\)；所有区间有公共点时期望 \(\Theta(n)\)，而且算法不需要专门检测这种情况——重叠越多，自动越快。

对量化研究的启发是：如果因子得分有估计误差，排名本质上是"区间的排序"。区间大面积重叠时，可区分的排序信息很少；按点估计精细排名、频繁调仓，交易的大部分是噪声。

7.6 量化实战

7.6.1 验证期望比较次数，观察两类退化

下面的实现用小侧递归控制栈深，并统计比较次数。实验分三部分：随机输入下的平均比较次数与精确期望 \(2(n+1)H_n-4n\) 对照；已排序输入在固定主元和随机主元下的差别；大量重复值下二路划分与三路划分的差别。

import math, random
import numpy as np

class Counter:
    def __init__(self): self.cmp = 0

def lomuto_partition(A, p, r, c):
    x = A[r]; i = p - 1
    for j in range(p, r):
        c.cmp += 1
        if A[j] <= x:
            i += 1; A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

def quicksort(A, c, randomized=True):
    """小侧递归、大侧循环（思考题 7-4），最坏栈深 O(lg n)。"""
    def qs(p, r):
        while p < r:
            if randomized:
                k = random.randint(p, r); A[k], A[r] = A[r], A[k]   # RANDOMIZED-PARTITION
            q = lomuto_partition(A, p, r, c)
            if q - p < r - q:
                qs(p, q - 1); p = q + 1
            else:
                qs(q + 1, r); r = q - 1
    qs(0, len(A) - 1)

def partition3(A, p, r, c):
    """三路划分（思考题 7-2）：返回 (q, t)，A[p..q-1] < x，A[q..t] == x，A[t+1..r] > x。"""
    k = random.randint(p, r); x = A[k]
    lt, i, gt = p, p, r
    while i <= gt:
        c.cmp += 1
        if A[i] < x:
            A[lt], A[i] = A[i], A[lt]; lt += 1; i += 1
        elif A[i] > x:
            A[i], A[gt] = A[gt], A[i]; gt -= 1
        else:
            i += 1
    return lt, gt

def quicksort3(A, c):
    def qs(p, r):
        while p < r:
            q, t = partition3(A, p, r, c)
            if q - p < r - t:
                qs(p, q - 1); p = t + 1
            else:
                qs(t + 1, r); r = q - 1
    qs(0, len(A) - 1)

random.seed(0); rng = np.random.default_rng(0)

# 原书图 7.1 的例子
A = [2, 8, 7, 1, 3, 5, 6, 4]; q = lomuto_partition(A, 0, 7, Counter())
print("图7.1 划分结果:", A, " 主元位置(1 起始) q =", q + 1)

# (1) 随机输入：比较次数 vs 期望 E[X] = 2(n+1)H_n - 4n ≈ 2n ln n
for n, trials in [(1000, 200), (10000, 20), (100000, 3)]:
    cnt = []
    for _ in range(trials):
        A = rng.permutation(n).tolist(); c = Counter(); quicksort(A, c)
        assert A == sorted(A); cnt.append(c.cmp)
    H = sum(1 / k for k in range(1, n + 1))
    exact = 2 * (n + 1) * H - 4 * n                      # E[X] 的精确值
    print(f"n={n:>6d}  平均比较次数={np.mean(cnt):>10.0f}  E[X]={exact:>10.0f}  2n·ln n={2*n*math.log(n):>10.0f}")

# (2) 已排序输入 + 固定取最后一个元素作主元：最坏情况 n(n-1)/2
n = 2000; A = list(range(n)); c = Counter(); quicksort(A, c, randomized=False)
print(f"已排序输入、固定主元: 比较 {c.cmp}，n(n-1)/2 = {n*(n-1)//2}")
A = list(range(n)); c = Counter(); quicksort(A, c)
print(f"已排序输入、随机主元: 比较 {c.cmp}")

# (3) 大量重复值：价格在 0.01 的最小变动价位上只有 50 种取值
n = 20000
ticks = rng.integers(0, 50, n).tolist()
A = ticks[:]; c2 = Counter(); quicksort(A, c2); assert A == sorted(ticks)
A = ticks[:]; c3 = Counter(); quicksort3(A, c3); assert A == sorted(ticks)
print(f"50 种取值的 {n} 个价格: 二路划分比较 {c2.cmp}，三路划分比较 {c3.cmp}")
A = [7] * 3000; c2 = Counter(); quicksort(A, c2)
A = [7] * 3000; c3 = Counter(); quicksort3(A, c3)
print(f"3000 个完全相同的值: 二路划分比较 {c2.cmp}，三路划分比较 {c3.cmp}")

输出：

图7.1 划分结果: [2, 1, 3, 4, 7, 5, 6, 8]  主元位置(1 起始) q = 4
n=  1000  平均比较次数=     11035  E[X]=     10986  2n·ln n=     13816
n= 10000  平均比较次数=    156343  E[X]=    155772  2n·ln n=    184207
n=100000  平均比较次数=   1957199  E[X]=   2018053  2n·ln n=   2302585
已排序输入、固定主元: 比较 1999000，n(n-1)/2 = 1999000
已排序输入、随机主元: 比较 23460
50 种取值的 20000 个价格: 二路划分比较 4120437，三路划分比较 119546
3000 个完全相同的值: 二路划分比较 4498500，三路划分比较 3000

白话解释：代码里几处语法。class Counter: 只是造了一个装计数器 cmp 的小盒子，传进各个函数，函数里 c.cmp += 1 就能累加比较次数。def qs(p, r): 定义在 quicksort 内部，可以直接使用外层的 A 和 c。while p < r: 循环配合 p = q + 1 或 r = q - 1 就是"大侧不递归、改用循环继续处理"的写法：每轮只对较小的一侧调用 qs，较大的一侧通过修改 p、r 留在本层循环里接着划分。random.randint(p, r) 在 \(p\) 到 \(r\) 之间（含两端）均匀取一个整数，对应伪代码的 RANDOM(p, r)。

读结果：

  • 随机输入的平均比较次数与 \(2(n+1)H_n-4n\) 吻合（\(n=10^5\) 只做了 3 次，波动大一些；单次比较次数的标准差约为 \(0.65n\)）。常用的近似 \(2n\ln n\) 偏高，因为它忽略了 \(-2.85n\) 左右的线性项。
  • 已排序输入 + 固定主元的比较次数恰好是 \(n(n-1)/2\)，与 7.2 节的分析一致；换成随机主元后降了两个数量级。
  • 只有 50 种取值的价格数据，二路划分的比较次数是三路划分的 35 倍；所有值相同时，二路划分是 \(n^2/2\)，三路划分只需一趟 \(n\) 次。

7.6.2 稳定性、多键排序与近乎有序的数据

import time
import numpy as np, pandas as pd

rng = np.random.default_rng(1)

# (1) 稳定性：同价订单必须保持到达顺序（时间优先）
n = 10_000
orders = pd.DataFrame({
    "arrive": np.arange(n),                                  # 到达序号，已按时间排好
    "price": np.round(100 + rng.integers(-5, 6, n) * 0.01, 2),
})
idx_q = np.argsort(-orders["price"].to_numpy(), kind="quicksort")   # introsort，不稳定
idx_s = np.argsort(-orders["price"].to_numpy(), kind="stable")      # 稳定排序
def time_priority_ok(idx):
    o = orders.iloc[idx]
    return bool((o.groupby("price", sort=False)["arrive"].apply(lambda s: s.is_monotonic_increasing)).all())
print("quicksort 排序后同价位仍按时间先后:", time_priority_ok(idx_q))
print("stable    排序后同价位仍按时间先后:", time_priority_ok(idx_s))

# (2) 多关键字排序 = 从次要键到主要键依次做稳定排序（基数排序的思想，第 08 章）
df = pd.DataFrame({"date": rng.integers(0, 20, n), "code": rng.integers(0, 300, n), "x": rng.random(n)})
a = df.sort_values(["date", "code"], kind="stable")
b = df.sort_values("code", kind="stable").sort_values("date", kind="stable")
print("两遍稳定排序与多列排序结果一致:", a.index.equals(b.index))

# (3) 近乎有序的时间戳（练习 7.2-4）：插入排序 Θ(n + 逆序对数)
def insertion_sort(A):
    moves = 0
    for j in range(1, len(A)):
        key, i = A[j], j - 1
        while i >= 0 and A[i] > key:
            A[i + 1] = A[i]; i -= 1; moves += 1
        A[i + 1] = key
    return moves
m = 200_000
ts = np.arange(m) * 1000 + rng.integers(0, 3000, m)        # 网络抖动让少量记录轻微乱序
A = ts.tolist(); t0 = time.perf_counter(); inv = insertion_sort(A); t1 = time.perf_counter()
assert A == sorted(ts.tolist())
print(f"{m} 条轻微乱序记录: 逆序对 {inv}（约 {inv/m:.2f} 个/条），纯 Python 插入排序 {t1-t0:.2f}s")

输出：

quicksort 排序后同价位仍按时间先后: False
stable    排序后同价位仍按时间先后: True
两遍稳定排序与多列排序结果一致: True
200000 条轻微乱序记录: 逆序对 55397（约 0.28 个/条），纯 Python 插入排序 0.01s
  1. 稳定性：模拟一批按到达时间排好的订单，按价格从高到低排序。用不稳定的 introsort 后，同价位订单的先后顺序被打乱，违反时间优先；稳定排序则保留了到达顺序。凡是"先按一个键排好、再按另一个键排序且希望保留前一次顺序"的场景（订单的价格-时间优先、同一因子值的股票保持代码顺序以便结果可复现），都要显式指定稳定排序。
  2. 多键排序：先按次要键（代码）稳定排序，再按主要键（日期）稳定排序，结果与一次按 [date, code] 排序相同。这正是第 08 章基数排序的原理。
  3. 近乎有序的数据（练习 7.2-4）：交易所推送的记录因网络抖动轻微乱序，20 万条只有约 5.5 万个逆序对。插入排序的代价是 \(\Theta(n+I)\)（\(I\) 为逆序对数），纯 Python 也只花了约 0.01 秒；而固定主元的快速排序在这种数据上会趋近最坏情况。这也是 Timsort 的设计出发点：它先识别已有序的"顺串"再归并，对时间序列数据非常高效。所以对按时间到达的数据重排，首选 kind='stable'，而不是默认的快速排序。

本章小结

快速排序把工作全放在划分上：选一个主元，把小的放左边、大的放右边，再分别递归，不需要合并。划分平衡时 \(\Theta(n\lg n)\)，任何常数比例划分都只影响常数；每次都极端不平衡时退化为 \(\Theta(n^2)\)，已排序输入和全相等输入是两种典型触发条件。随机选主元后，期望比较次数为 \(\sum_{i<j}2/(j-i+1)=2(n+1)H_n-4n\approx1.39n\lg n\)，对任何输入都成立。工业实现再叠加三路划分（重复值）、三数取中、小数组插入排序、小侧递归（栈深 \(O(\lg n)\)）和堆排序兜底（introsort）。快速排序不稳定；需要保留原有顺序时必须用稳定排序。

概念/公式 内容
Lomuto 划分不变式 \(A[p..i]\le x\)，\(A[i+1..j-1]>x\)，\(A[r]=x\)
最坏情况 \(T(n)=T(n-1)+\Theta(n)=\Theta(n^2)\)
最好情况 \(T(n)=2T(n/2)+\Theta(n)=\Theta(n\lg n)\)
常数比例划分 \(T(n)=T(9n/10)+T(n/10)+cn=O(n\lg n)\)
关键概率 \(\Pr\{z_i,z_j\text{ 被比较}\}=2/(j-i+1)\)
期望比较次数 \(E[X]=2(n+1)H_n-4n\approx2n\ln n\)
三路划分 \(A[p..q-1]<x=A[q..t]<A[t+1..r]\)，重复值下避免 \(\Theta(n^2)\)
三数取中 \(p_i=6(i-1)(n-i)/[n(n-1)(n-2)]\)，好划分概率 \(1/3\to13/27\)
小侧递归 最坏栈深 \(\Theta(\lg n)\)
小数组插入排序 期望 \(O(nk+n\lg(n/k))\)

练习

基础

  1. 手工演示 PARTITION 作用于 \(\langle13,19,9,5,12,8,7,4,21,2,6,11\rangle\)。（练习 7.1-1） 答案要点：主元 11；最终得 \(\langle9,5,8,7,4,2,6,11,21,13,19,12\rangle\)，返回 \(q=8\)。
  2. 所有元素相同时 PARTITION 返回什么？修改它，使这种情况下返回 \(\lfloor(p+r)/2\rfloor\)。（练习 7.1-2） 提示：返回 \(r\)；可对等于主元的元素交替放入两侧。
  3. 如何把 QUICKSORT 改成降序排序？（练习 7.1-4） 提示：第 4 行改为 A[j] >= x。
  4. 证明元素互异且降序排列时，固定取末元素为主元的 QUICKSORT 运行时间为 \(\Theta(n^2)\)。（练习 7.2-3） 提示：每次主元都是最小值，划分出 0 和 \(n-1\)。
  5. 在你的研究代码里，下面哪些操作需要稳定排序？（a）按因子值选前 50 只；（b）按 (日期, 因子值) 排序后取每日前 50 只，要求结果可复现；（c）订单簿同价位按到达顺序排队。 提示：（a）不需要；（b）在因子值有并列时需要（或加代码作第三键）；（c）需要。

进阶

  1. 设每层划分比例为 \((1-\alpha):\alpha\)（\(0<\alpha\le1/2\)），证明递归树叶子的最小深度约为 \(-\lg n/\lg\alpha\)、最大深度约为 \(-\lg n/\lg(1-\alpha)\)。（练习 7.2-5） 提示：沿"总取小的一侧"的路径，规模每层乘 \(\alpha\)，到 1 需 \(\log_{1/\alpha}n\) 层。
  2. 从 \(\sum_{i<j}2/(j-i+1)\) 出发，推导 \(E[X]=2(n+1)H_n-4n\)。 提示：差值为 \(k-1\) 的数对有 \(n-k+1\) 个，\(\sum_{k=2}^n\frac{2(n-k+1)}{k}=2(n+1)(H_n-1)-2(n-1)\)。
  3. 证明"小侧递归、大侧循环"的版本最坏栈深为 \(\Theta(\lg n)\)，并说明只消除尾递归为什么不够。（思考题 7-4） 提示：每次递归进入的子数组规模不超过当前的一半。
  4. 写出三路划分 PARTITION′ 并证明它是 \(\Theta(r-p)\)；在 7.6.1 节的代码中把 50 种取值改成 5 种，比较二路与三路划分的比较次数。（思考题 7-2） 提示：取值越少，二路划分越接近 \(n^2/2\)，三路划分越接近 \(n\cdot(\text{取值数})\) 量级。
  5. （思考题 7-5）验证三数取中时，"主元名次落在 \([n/3,2n/3]\)"的概率极限为 \(13/27\)。 提示：\(\int_{1/3}^{2/3}6t(1-t)\,dt=6\big[\tfrac{t^2}{2}-\tfrac{t^3}{3}\big]_{1/3}^{2/3}=13/27\)。

原书推荐习题：7.1-2、7.2-2、7.2-4、7.4-5；思考题 7-1、7-2、7-3、7-4、7-5。

原书对照

本章小节 原书章节 PDF 页码
7.1 算法描述 7.1 Description of quicksort p.191–195
7.2 性能的直观分析 7.2 Performance of quicksort p.195–200
7.3 随机化快速排序 7.3 A randomized version of quicksort p.200–201
7.4 严格分析 7.4 Analysis of quicksort p.201–206
7.5 工程实现要点 Chapter 7 Problems（7-1 至 7-6）与 Notes p.206–211