第 08 章 排序的下界与线性时间排序

学习目标

1. 能用决策树模型证明：任何比较排序在最坏情况下至少需要 \(\Omega(n\lg n)\) 次比较，并理解这个下界"管什么、不管什么"。
2. 掌握计数排序的三趟扫描，理解它为什么从后往前放置、为什么必须稳定。
3. 掌握基数排序的正确性条件（每位排序必须稳定），会用 \(\Theta((b/r)(n+2^r))\) 选择每遍的位数 \(r\)。
4. 掌握桶排序的平均线性时间分析（\(E[n_i^2]=2-1/n\)），以及用概率积分变换把任意已知分布化为均匀分布。
5. 能把这些"用值作下标"的思想用到量化场景：价格档位直方图、成交量分布、区间计数、分位数分组、多键排序。

读前导读

这一章在解决什么问题。 前几章的排序算法（归并、堆、快速排序）最好也只能做到大约 \(n\lg n\) 次操作。本章先回答一个"天花板"问题：只靠"两两比大小"来排序，能不能更快？答案是不能——这是一个关于所有可能算法的结论，不是某个算法写得不好。然后本章给出绕过天花板的办法：不比大小，而是直接把数值当作位置。最贴近你工作的例子是成交量分布：一天几万笔成交，价格却只落在几百个价位上，你只需准备几百个"格子"，每笔成交往对应价位的格子里一扔，扫一遍就排好了，根本不需要比较两笔成交谁的价格高。

可以把本章和你熟悉的东西这样对应：决策树下界的思路是"信息量"——你要从 \(n!\) 种可能的排列里认出真实的那一种，每问一个"是/否"问题最多把可能性砍掉一半，这和二分法估算债券到期收益率（YTM）时每试一次就把区间减半是同一个道理。桶排序的平均分析则完全是 CFA 级别的概率：二项分布的均值和方差。最后的概率积分变换，就是你熟悉的"把 z 值换成百分位"（\(\Phi(z)\)）。

需要先想起来的数学。

• 对数 \(\lg\) 与指数的互逆关系。 本书 \(\lg\) 表示以 2 为底的对数：\(\lg 8=3\) 因为 \(2^3=8\)。直观含义："要把 \(n\) 个东西每次对半分，分几次才剩一个"。不等式 \(l\le 2^h\) 两边取 \(\lg\) 得 \(\lg l\le h\)，因为 \(\lg\) 是递增函数，取对数不改变不等号方向。\(\lg(ab)=\lg a+\lg b\)，所以 \(\lg(n!)=\lg1+\lg2+\cdots+\lg n\)。见 第 00 册第 04 章 级数与收敛。
• 渐近记号 \(\Theta\)、\(O\)、\(\Omega\)。 粗略说：\(O(f)\) 是"不超过 \(f\) 的常数倍"（上界），\(\Omega(f)\) 是"至少是 \(f\) 的常数倍"（下界），\(\Theta(f)\) 是"上下都卡住，增长速度和 \(f\) 一样"。例：\(3n^2+5n=\Theta(n^2)\)。本章的下界定理用的是 \(\Omega\)。详见本册第 03 章。
• 示性随机变量与期望的线性性。 \(I\{\text{事件}\}\) 在事件发生时取 1，否则取 0，所以 \(E[I]=\Pr\{\text{事件}\}\)。期望的线性性：\(E[X+Y]=E[X]+E[Y]\)，不论 \(X,Y\) 是否独立；但 \(E[XY]=E[X]E[Y]\) 需要独立。例：掷 10 枚硬币，正面数 \(=\sum I_j\)，期望 \(=10\times0.5=5\)。见 第 00 册第 07 章 概率中的分析工具。
• 求和记号与前缀和。 \(\sum_{k=1}^{n}a_k=a_1+\cdots+a_n\)。"前缀和" \(C[i]=a_0+\cdots+a_i\) 的好处是区间和 \(a_a+\cdots+a_b=C[b]-C[a-1]\)，一次减法搞定——就像用累计净值相除得到任意区间收益。
• 分布函数（CDF）。 \(P(x)=\Pr\{X\le x\}\)，单调不减，取值在 \([0,1]\)。标准正态的 CDF 就是你查表用的 \(\Phi\)，\(\Phi(1.645)\approx0.95\)。

怎么读这一章。 8.1 节的定理 8.1 和它后面"一次比较最多 1 比特"那段是核心，务必读懂；"下界的推广"一节第一次可以只看结论。8.2 计数排序和 8.3 基数排序是全章最实用的部分，建议拿纸笔把图 8.2 的例子手算一遍。8.4 节的 \(E[n_i^2]\) 证明是一道标准的期望计算题，CFA 统计基础够用。8.5 节量化实战值得精读，尤其是价位直方图和十分组的对比；8.6 节可以跳过。

8.1 比较排序的下界

比较模型

插入、归并、堆、快速排序有一个共同点：它们只通过比较两个元素来获得顺序信息，称为比较排序（comparison sorts）。在这个模型里，算法可以做 \(a_i<a_j\)、\(a_i\le a_j\)、\(a_i=a_j\)、\(a_i\ge a_j\)、\(a_i>a_j\) 这类测试，但不能查看元素的值本身，也不能用其他方式获取顺序信息。为了下界证明，不妨设元素互异：此时 \(a_i=a_j\) 的测试没有用，其余四种测试提供的信息等价，所以只考虑 \(a_i\le a_j\)。

决策树

决策树（decision tree）是一棵满二叉树，表示某个比较排序算法在给定规模 \(n\) 上执行的全部比较，忽略数据移动和控制逻辑。内部结点标 \(i:j\)，表示比较 \(a_i\le a_j\)；左子树是"成立"之后的比较，右子树是"不成立"之后的比较。叶子标一个排列 \(\langle\pi(1),\dots,\pi(n)\rangle\)，表示算法认定 \(a_{\pi(1)}\le a_{\pi(2)}\le\cdots\le a_{\pi(n)}\)。算法在一个具体输入上的一次运行，就是从根到某片叶子的一条路径。

例（原书图 8.1）：插入排序在 3 个元素上的决策树。根比较 1:2；若 \(a_1\le a_2\)，再比较 2:3，成立则输出 \(\langle1,2,3\rangle\)，否则再比较 1:3，得 \(\langle1,3,2\rangle\) 或 \(\langle3,1,2\rangle\)；若 \(a_1>a_2\)，比较 1:3，成立得 \(\langle2,1,3\rangle\)，否则比较 2:3，得 \(\langle2,3,1\rangle\) 或 \(\langle3,2,1\rangle\)。输入 \(\langle6,8,5\rangle\) 走到叶子 \(\langle3,1,2\rangle\)，即 \(a_3=5\le a_1=6\le a_2=8\)。

一个正确的排序算法必须能输出所有 \(n!\) 种排列，所以每种排列都必须作为可达叶子出现。

白话解释：决策树就是"猜谜游戏"的完整剧本。你手里有 3 张写了数字的牌，对手只允许你问"第 \(i\) 张是否不大于第 \(j\) 张"这类是非题。每问一题，剧本就往左或往右分叉；问到能确定 3 张牌的大小顺序时停下，这个停下的位置就是叶子，叶子上写着答案（一个排列）。3 张牌的顺序共有 \(3!=6\) 种，所以剧本至少要有 6 个结局。 "满二叉树"指每个分叉点恰好有两个分支（是/否）。"排列 \(\langle3,1,2\rangle\)"的意思是"第 3 个元素最小、第 1 个次之、第 2 个最大"，记的是下标，不是数值本身。

定理与证明

算法的最坏比较次数就是从根到可达叶子的最长路径，即决策树的高度。

定理 8.1：任何比较排序算法在最坏情况下都需要 \(\Omega(n\lg n)\) 次比较。

证明：设决策树高度为 \(h\)、有 \(l\) 片可达叶子。每种排列都要出现，故 \(n!\le l\)；高度为 \(h\) 的二叉树至多 \(2^h\) 片叶子，故

最后一步用斯特林公式，或者不用它：\(\lg n!=\sum_{k=1}^{n}\lg k\ge\sum_{k=\lceil n/2\rceil}^{n}\lg\frac n2\ge\frac n2\lg\frac n2\)（练习 8.1-2）。\(\blacksquare\)

推导拆解：这个证明只有三步，每步用的东西都很朴素。 第一步 \(n!\le l\)：每种排列都得有一片叶子对应它（否则这种输入会被排错），所以叶子数至少是排列数。 第二步 \(l\le 2^h\)：每往下一层，结点数最多翻一倍；第 0 层 1 个，第 1 层至多 2 个，……第 \(h\) 层至多 \(2^h\) 个。 第三步取对数：\(n!\le2^h\) 两边取 \(\lg\)，得 \(h\ge\lg(n!)\)。 最后估计 \(\lg(n!)\) 的大小：\(\lg(n!)=\lg1+\lg2+\cdots+\lg n\)（对数把乘积变成和）。扔掉前一半较小的项（扔掉非负项只会让和变小，不等号方向正确），后一半至少有 \(n/2\) 项，每项 \(\lg k\ge\lg(n/2)\)，所以和 \(\ge\frac n2\lg\frac n2\)。而 \(\frac n2\lg\frac n2=\frac n2(\lg n-1)\)，\(n\) 大时就是 \(n\lg n\) 的常数倍，这正是 \(\Omega(n\lg n)\) 的意思。 数值感受：\(n=1000\) 时 \(\lg(1000!)\approx8530\)，即任何比较排序最坏都要 8530 次以上比较；而 \(n\lg n\approx9966\)。

推论 8.2：堆排序和归并排序是渐近最优的比较排序。

把这个证明换个角度理解会更有用：**一次比较最多提供 1 比特信息，而要从 \(n!\) 种可能中确定一种，至少需要 \(\lg n!\) 比特。**这就是"信息论下界"。按这个角度，第 07 章的随机化快速排序平均用 \(1.39n\lg n\) 次比较，只比下界多 39%。

金融直觉：这个下界说的是"信息不够就不可能做到"，不是"目前没人做到"。类比：要从 1024 只候选债券里通过"是/否"问题锁定一只，最少要问 \(\lg1024=10\) 个问题，再聪明的提问方式也省不掉。排序要锁定的是 \(n!\) 种顺序之一，所以至少要问 \(\lg(n!)\) 次。想突破，就只能换一种"每次能得到更多信息"的提问方式——比如直接看数值，这就是后面三种算法的出发点。

下界的推广

• 几乎所有输入都难（练习 8.1-3）：不存在一种比较排序，能对 \(n!\) 个输入中的一半、\(1/n\) 甚至 \(1/2^n\) 在线性时间内完成。因为深度不超过 \(h\) 的叶子至多 \(2^h\) 个，而 \(\lg(n!/2)\)、\(\lg(n!/n)\)、\(\lg(n!/2^n)\) 都还是 \(\Theta(n\lg n)\)。
• 平均情况与随机化（思考题 8-1）：即使按平均情况计，或允许算法使用随机数，比较排序的期望时间仍是 \(\Omega(n\lg n)\)。思路是：所有叶子深度之和（外部路径长度）在 \(k\) 片叶子的二叉树中至少是 \(\Omega(k\lg k)\)，取 \(k=n!\) 再平均；随机化算法可以看成一族确定性算法的混合，其中最好的那个不会比平均差。
• 分块排序（练习 8.1-4）：输入由 \(n/k\) 个块组成，块与块之间已经有序，只需块内排序。可能的输出有 \((k!)^{n/k}\) 种，所以下界是 \(\lg\big((k!)^{n/k}\big)=\frac nk\lg k!=\Omega(n\lg k)\)。
• 最少比较（练习 8.1-1）：决策树里叶子的最小深度是 \(n-1\)——要确认输入已经有序，至少得把相邻元素都比一遍。
• 合并的下界（思考题 8-6）：合并两个各含 \(n\) 个元素的有序表，有 \(\binom{2n}{n}\) 种可能结果，信息论下界是 \(\lg\binom{2n}{n}=2n-o(n)\)；更精细的论证（来自不同表、在结果中相邻的两个元素必须直接比较）给出 \(2n-1\) 的精确下界。

这个下界不管什么

下界只约束"只能比较"的算法。如果算法能直接利用元素的值（比如把值当数组下标），就跳出了这个模型。下面三种算法都是这样做的，代价是对输入做了假设：整数范围有限、位数有限、或分布已知。第 09 章还会看到另一种绕开方式：不排序，只做选择。

8.2 计数排序

思想与伪代码

计数排序（counting sort）假设 \(n\) 个输入都是 \(0..k\) 之间的整数。对每个元素 \(x\)，如果知道有多少个元素小于等于它，就能把它直接放到输出的正确位置——例如有 17 个元素小于 \(x\)，\(x\) 就属于第 18 位。有重复值时，每放一个就把计数减 1，让下一个同值元素放到它前面。

COUNTING-SORT(A, B, k)
1   let C[0..k] be a new array
2   for i = 0 to k
3       C[i] = 0
4   for j = 1 to A.length
5       C[A[j]] = C[A[j]] + 1          // C[i] = 等于 i 的元素个数
6   for i = 1 to k
7       C[i] = C[i] + C[i - 1]         // C[i] = 小于等于 i 的元素个数
8   for j = A.length downto 1
9       B[C[A[j]]] = A[j]
10      C[A[j]] = C[A[j]] - 1

例（原书图 8.2）：\(A=\langle2,5,3,0,2,3,0,3\rangle\)，\(k=5\)。第一趟计数后 \(C=\langle2,0,2,3,0,1\rangle\)；求前缀和后 \(C=\langle2,2,4,7,7,8\rangle\)。从后往前放：\(A[8]=3\) 放到 \(B[7]\)，\(C[3]\) 变为 6；\(A[7]=0\) 放到 \(B[2]\)，\(C[0]\) 变为 1；\(A[6]=3\) 放到 \(B[6]\)，\(C[3]\) 变为 5；……最终 \(B=\langle0,0,2,2,3,3,3,5\rangle\)。

白话解释：计数排序像给一场考试排座位。第一趟点名：数出 0 分的有 2 人、2 分的 2 人、3 分的 3 人、5 分的 1 人。第二趟累加：0 分及以下 2 人，所以 0 分的人坐 1–2 号；2 分及以下 4 人，所以 2 分的人坐 3–4 号；3 分及以下 7 人，所以 3 分的人坐 5–7 号。第三趟入座：每来一个人，按他的分数直接走到"本分数段的最后一个空座"，坐下后把这个分数段的空座指针往前挪一格。 这里的 \(C[i]\) 先后有两层意思：第 5 行之后是"等于 \(i\) 的个数"，第 7 行之后变成"小于等于 \(i\) 的个数"，也就是"值为 \(i\) 的元素中最后一个该坐的位置"。整个过程没有拿任何两个人的分数互相比较，只用了"分数本身就是格子编号"这一点。

运行时间

第 2–3 行 \(\Theta(k)\)，第 4–5 行 \(\Theta(n)\)，第 6–7 行 \(\Theta(k)\)，第 8–10 行 \(\Theta(n)\)，合计 \(\Theta(n+k)\)。当 \(k=O(n)\) 时就是 \(\Theta(n)\)。代码里没有任何两个输入元素之间的比较，所以不受 \(\Omega(n\lg n)\) 约束。

稳定性

排序是稳定的（stable），如果值相同的元素在输出中保持输入中的相对次序。第 8 行从后往前扫描保证了这一点：同值元素中最后出现的那个被放到同值区段的最后。如果改成从前往后扫（练习 8.2-3），排序仍然正确，但同值元素的次序会被反转，不再稳定。

推导拆解：为什么从后往前扫就稳定？以图 8.2 中的三个 3 为例，它们在 \(A\) 中的位置是 3、6、8。前缀和后 \(C[3]=7\)，即值为 3 的区段占 \(B[5..7]\)。从后往前扫：先遇到 \(A[8]\)，放进 \(B[7]\)（区段最后）；再遇到 \(A[6]\)，放进 \(B[6]\)；最后 \(A[3]\) 放进 \(B[5]\)。原来靠后的仍然靠后，次序保住了。若从前往后扫，\(A[3]\) 会先拿到 \(B[7]\)，次序就整个倒过来。

当只排孤立的数时，稳定不稳定看不出来；带卫星数据时它很重要。计数排序的稳定性还有一个更关键的用途：它是基数排序的子程序，而基数排序的正确性依赖子排序稳定。

区间计数

练习 8.2-4 给出一个副产品：做完前 7 行（\(\Theta(n+k)\) 预处理）后，"有多少个元素落在 \([a,b]\)"可以 \(O(1)\) 回答：\(C[b]-C[a-1]\)。这就是前缀和技巧，量化里用它做价位区间成交量、收益区间计数等查询。

原地版本（思考题 8-2，了解即可）

计数排序需要输出数组 \(B\)，不是原地的。思考题 8-2 讨论关键字只有 0 和 1 时三个性质——\(O(n)\) 时间、稳定、原地——只能三选二：计数排序满足前两个；类似 PARTITION 的双指针交换满足第一和第三个；插入排序满足后两个。关键字在 \(1..k\) 时，可以先算出每个值的目标区间，再循环交换把元素放进所属区间，得到原地、\(O(n+k)\) 但不稳定的版本（与 American flag sort 同一思路）。

8.3 基数排序

从卡片排序机说起

基数排序（radix sort）源自穿孔卡片排序机：机器一次只能按一列把卡片分到 10 个箱子里。直觉的做法是先按最高位分箱，再对每个箱子递归，但这要保管大量中间卡片堆（练习 8.3-5★：最坏需要 \((10^d-1)/9\) 遍）。反直觉但高效的做法是先按最低有效位（least significant digit）排序，合成一叠，再按次低位排序……直到最高位，只需 \(d\) 遍。

例（原书图 8.3）：\(\langle329,457,657,839,436,720,355\rangle\)。按个位排序得 \(\langle720,355,436,457,657,329,839\rangle\)；按十位排序得 \(\langle720,329,436,839,355,457,657\rangle\)；按百位排序得 \(\langle329,355,436,457,657,720,839\rangle\)。

RADIX-SORT(A, d)
1  for i = 1 to d                      // 第 1 位最低，第 d 位最高
2      use a stable sort to sort array A on digit i

为什么必须稳定

用归纳法证明（练习 8.3-3）：设前 \(i-1\) 位已排好，现在按第 \(i\) 位排序。第 \(i\) 位不同的两个数，按第 \(i\) 位排好就对了；第 \(i\) 位相同的两个数，它们的先后应该由低 \(i-1\) 位决定，而这个顺序上一遍已经排好——只有稳定排序才会保留它。

同样的道理用于多字段记录：按年、月、日排序日期，可以写一个先比年、再比月、再比日的比较函数，也可以用稳定排序排三遍：先按日，再按月，最后按年。pandas 的 sort_values([...], kind='stable') 和"先按次要键、再按主要键各做一次稳定排序"结果相同（第 07 章 7.6.2 节验证过）。

金融直觉：成交回报要按"交易日 → 账户 → 成交时间"排序。用稳定排序的做法是倒着来：先按成交时间排，再按账户排，最后按交易日排。最后一遍按交易日排时，同一天的记录之间不会被打乱，它们仍保持上一遍排好的"账户、时间"顺序。如果最后一遍不稳定，同一天内的记录会被随意重排，前两遍就白做了。"卫星数据"指跟着关键字一起移动的其他字段，比如按评级排序时跟着走的股票代码。

运行时间

引理 8.3：\(n\) 个 \(d\) 位数，每位取 \(k\) 种值，若每遍用 \(\Theta(n+k)\) 的稳定排序（计数排序），则基数排序用时 \(\Theta(d(n+k))\)。\(d\) 为常数且 \(k=O(n)\) 时为线性。

引理 8.4：\(n\) 个 \(b\) 位二进制数，对任意 \(r\le b\)，把每个数看成 \(\lceil b/r\rceil\) 个 \(r\) 位"数字"，每个数字在 \(0..2^r-1\) 之间，则基数排序用时

例如 32 位整数取 \(r=8\)：4 遍，每遍计数数组长 256。

怎样选 \(r\)

目标是最小化 \((b/r)(n+2^r)\)：

• 若 \(b<\lfloor\lg n\rfloor\)：任何 \(r\le b\) 都有 \(n+2^r=\Theta(n)\)，取 \(r=b\)，一遍完成，\(\Theta(n)\)。
• 若 \(b\ge\lfloor\lg n\rfloor\)：取 \(r=\lfloor\lg n\rfloor\)，代价 \(\Theta(bn/\lg n)\)，在常数因子内最优。\(r\) 再大，分子里的 \(2^r\) 涨得比分母里的 \(r\) 快；\(r\) 再小，遍数 \(b/r\) 变多而每遍仍是 \(\Theta(n)\)。

一句话：**每遍处理 \(\lg n\) 位，让计数数组和输入一样大。**下面的实验里 \(n=20000\)，\(\lg n\approx14.3\)，理论代价在 \(r=11\) 附近最小。

推导拆解：代价 \((b/r)(n+2^r)\) 是"遍数 × 每遍工作量"。遍数 \(b/r\)：32 位整数每遍处理 8 位，要 4 遍。每遍工作量 \(n+2^r\)：扫一遍 \(n\) 个数，加上清零和累加长度为 \(2^r\) 的计数数组。这是一个典型的此消彼长：\(r\) 大则遍数少，但计数数组按 \(2^r\) 指数膨胀。 取 \(r=\lg n\) 时 \(2^r=n\)，每遍工作量 \(2n\)，遍数 \(b/\lg n\)，总代价约 \(2bn/\lg n\)。若 \(r\) 比 \(\lg n\) 大 1，计数数组翻倍；大 5，计数数组变成 \(32n\)，远超遍数减少带来的节省。所以平衡点就在"计数数组和输入差不多大"处。这和久期管理里"在两个反向成本之间找平衡"是同一种权衡思路，只是这里没有用导数，而是直接比较数量级。 注意实验里的 \(r=11\) 并不等于 \(\lg n\approx14\)：因为遍数要向上取整，\(r=11\) 恰好 3 遍，\(r=14\) 也是 3 遍但计数数组大 8 倍，所以 11 更划算。

基数排序 vs 快速排序

若 \(b=O(\lg n)\)、取 \(r\approx\lg n\)，基数排序是 \(\Theta(n)\)，渐近上优于快速排序的 \(\Theta(n\lg n)\)。但 \(\Theta\) 里藏着不同的常数：基数排序遍数少，每遍却可能慢得多（随机写入计数数组对 cache 不友好）；快速排序顺序扫描数组，更善于利用 cache。再者，以计数排序为子程序的基数排序不是原地的。实践中怎么选取决于实现、机器和数据，需要实测。NumPy 的做法可作参考：kind='stable' 对 16 位及以下整数类型用基数排序，其他类型用 Timsort。

变长数据（思考题 8-3）

• 整数位数不同、总位数为 \(n\)：先按位数分组（没有前导零时，位数多的数更大），每组内部做基数排序，总时间 \(O(n)\)。
• 字符串总字符数为 \(n\)，按字典序排序（\(a<ab<b\)）：按首字符用计数排序分组，组内对剩余字符递归，已经用完的短串排在组首，总时间 \(O(n)\)。这是 MSD（最高位优先）基数排序的思路，股票代码、合约代码这类定长短字符串都可以这样排。

8.4 桶排序

思想

桶排序（bucket sort）假设输入由随机过程产生，在 \([0,1)\) 上独立均匀分布。把 \([0,1)\) 等分成 \(n\) 个桶（bucket），把 \(n\) 个数分进去；因为分布均匀，每个桶里预期只有很少几个数。每个桶内部排序，再按桶的顺序首尾相接。

BUCKET-SORT(A)
1  n = A.length
2  let B[0..n-1] be a new array of empty lists
3  for i = 1 to n
4      insert A[i] into list B[floor(n * A[i])]
5  for i = 0 to n - 1
6      sort list B[i] with insertion sort
7  concatenate the lists B[0], B[1], ..., B[n-1] together in order

例（原书图 8.4）：\(n=10\)，\(A=\langle.78,.17,.39,.26,.72,.94,.21,.12,.23,.68\rangle\)。桶 \(i\) 存放 \([i/10,(i+1)/10)\) 中的值：\(B[1]=\{.12,.17\}\)，\(B[2]=\{.21,.23,.26\}\)，\(B[3]=\{.39\}\)，\(B[6]=\{.68\}\)，\(B[7]=\{.72,.78\}\)，\(B[9]=\{.94\}\)，依次连接即有序。

正确性：若 \(A[i]\le A[j]\)，则 \(\lfloor nA[i]\rfloor\le\lfloor nA[j]\rfloor\)，\(A[i]\) 要么与 \(A[j]\) 同桶（桶内排序负责），要么在更靠前的桶（连接顺序负责）。

平均情况分析

除第 6 行外，各行最坏都是 \(O(n)\)。设 \(n_i\) 是落入桶 \(i\) 的元素个数（随机变量），插入排序是二次的，所以

断言：对每个 \(i\)，

证明：令 \(X_{ij}=I\{A[j]\text{ 落入桶 }i\}\)，则 \(n_i=\sum_{j=1}^nX_{ij}\)。展开平方：

\(X_{ij}\) 以概率 \(1/n\) 取 1，所以 \(E[X_{ij}^2]=1/n\)；\(k\ne j\) 时 \(X_{ij}\) 与 \(X_{ik}\) 独立，\(E[X_{ij}X_{ik}]=1/n^2\)。代入：

推导拆解：逐步看清每一步用了什么。 (a) \(n_i=\sum_j X_{ij}\)：桶 \(i\) 里的个数，就是"第 1 个数是否落入桶 \(i\)"+"第 2 个数是否落入"+……，每项是 0 或 1。 (b) 展开平方：\((X_{i1}+\cdots+X_{in})^2\) 展开后有 \(n^2\) 项，其中 \(j=k\) 的 \(n\) 项是 \(X_{ij}^2\)，其余 \(n(n-1)\) 项是交叉项 \(X_{ij}X_{ik}\)。再对整体取期望，用期望的线性性把期望分配到每一项上。 (c) \(X_{ij}^2=X_{ij}\)，因为 0 和 1 的平方还是自己，所以 \(E[X_{ij}^2]=\Pr\{\text{落入桶 }i\}=1/n\)（\(n\) 个等宽桶，均匀分布落入每个的概率相同）。 (d) 交叉项要用独立性：不同输入独立抽取，所以 \(E[X_{ij}X_{ik}]=E[X_{ij}]E[X_{ik}]=\frac1n\cdot\frac1n\)。 直觉：平均每桶 1 个数，但"平方的平均"是 2 左右，因为有的桶 0 个、有的 2–3 个，平方会放大不均匀。插入排序的成本是 \(n_i^2\) 量级，所以要看 \(E[n_i^2]\) 而不是 \(E[n_i]\)；好在它是常数，\(n\) 个桶加起来仍是线性。

另一种看法：\(n_i\sim\text{Binomial}(n,1/n)\)，\(E[n_i^2]=\text{Var}(n_i)+(E[n_i])^2=(1-1/n)+1\)。注意 \(E[n_i^2]\ne(E[n_i])^2=1\)（练习 8.4-3 用抛两次硬币的例子说明 \(E[X^2]=3/2\ne E^2[X]=1\)）。

代回 (8.1)，平均运行时间是 \(\Theta(n)+n\cdot O(2-1/n)=\Theta(n)\)。

推广与局限

• 不一定要均匀：只要各桶大小的平方和的期望与 \(n\) 成线性，桶排序就是线性时间。
• 最坏情况是所有元素落进同一个桶，\(\Theta(n^2)\)；把桶内排序换成归并排序或堆排序，最坏降到 \(O(n\lg n)\)，平均仍为线性（练习 8.4-2）。
• 按等概率而不是等宽分桶：单位圆内均匀分布的点按到原点距离排序（练习 8.4-4★），距离 \(d\) 不是均匀的，但面积是：第 \(i\) 个桶取 \(\sqrt{i/n}\le d<\sqrt{(i+1)/n}\)，或者直接对 \(d^2\) 做桶排序。
• 任意已知连续分布（练习 8.4-5★）：若 \(X_1,\dots,X_n\) 独立同分布，分布函数 \(P(x)=\Pr\{X\le x\}\) 连续且可 \(O(1)\) 计算，则 \(P(X_i)\) 在 \([0,1]\) 上均匀，且 \(P\) 单调保序。对 \(P(X_i)\) 做桶排序即可平均线性时间排序。这就是统计学里的概率积分变换。

金融直觉：概率积分变换就是你熟悉的"z 值换百分位"。若某因子得分服从标准正态，得分 1.28 对应 \(\Phi(1.28)\approx0.90\)，即"第 90 百分位"。把所有得分都换成百分位后，它们就均匀铺在 \([0,1]\) 上，等宽分桶自然每桶人数差不多。为什么 \(P(X)\) 是均匀的：\(\Pr\{P(X)\le u\}=\Pr\{X\le P^{-1}(u)\}=P(P^{-1}(u))=u\)，这正是 \([0,1]\) 上均匀分布的分布函数。代价是你必须知道真实分布；分布假设错了（如收益率有厚尾却按正态处理），百分位就不准，桶就不均匀，8.5.2 节的实验会演示这一点。

8.5 量化实战

8.5.1 计数排序与基数排序的实现

import numpy as np

def counting_sort(A, k, key=lambda v: v):
    """稳定计数排序：key(v) 取值于 0..k。时间 Θ(n+k)，额外空间 Θ(n+k)。"""
    C = [0] * (k + 1)
    for v in A:
        C[key(v)] += 1                 # C[i] = 等于 i 的个数
    for i in range(1, k + 1):
        C[i] += C[i - 1]               # C[i] = 小于等于 i 的个数
    B = [None] * len(A)
    for v in reversed(A):              # 从后往前放，保证稳定
        C[key(v)] -= 1
        B[C[key(v)]] = v
    return B

def radix_sort(A, b=32, r=8):
    """LSD 基数排序：把 b 位非负整数看成 ceil(b/r) 个 r 位“数字”，每位用稳定计数排序。"""
    mask = (1 << r) - 1
    for shift in range(0, b, r):
        A = counting_sort(A, mask, key=lambda v: (v >> shift) & mask)
    return A

# 原书图 8.2 与图 8.3 的例子
print("图8.2:", counting_sort([2, 5, 3, 0, 2, 3, 0, 3], 5))
A = [329, 457, 657, 839, 436, 720, 355]
for d in range(3):                                      # 十进制逐位，打印每一遍的结果
    A = counting_sort(A, 9, key=lambda v: v // 10**d % 10)
    print(f"图8.3 第{d+1}遍(按第{d+1}位):", A)

# 稳定性演示：按“评级”排序，同评级保持原有（代码）顺序
recs = [("600519", 2), ("000001", 0), ("600036", 2), ("000858", 1), ("601318", 0)]
print("按评级稳定排序:", counting_sort(recs, 2, key=lambda t: t[1]))

# 随机测试：32 位整数，r 取 4/8/11/16 都应正确
rng = np.random.default_rng(3)
x = rng.integers(0, 2**32, 20000).tolist()
for r in (4, 8, 11, 16):
    assert radix_sort(x, 32, r) == sorted(x)
n = len(x)
for r in (4, 8, 11, 16):
    passes = -(-32 // r)
    print(f"r={r:>2d}: 遍数 d={passes}，理论代价 (b/r)(n+2^r) ≈ {passes * (n + 2**r):>7d}")
print("lg n ≈", round(np.log2(n), 1))

# 练习 8.2-4：预处理前缀计数后，O(1) 回答“有多少数落在 [a, b]”
vals = rng.integers(0, 100, 1000)
C = np.cumsum(np.bincount(vals, minlength=100))
a, b = 20, 35
print("落在 [20,35] 的个数:", C[b] - C[a - 1], "  直接数:", int(((vals >= a) & (vals <= b)).sum()))

输出：

图8.2: [0, 0, 2, 2, 3, 3, 3, 5]
图8.3 第1遍(按第1位): [720, 355, 436, 457, 657, 329, 839]
图8.3 第2遍(按第2位): [720, 329, 436, 839, 355, 457, 657]
图8.3 第3遍(按第3位): [329, 355, 436, 457, 657, 720, 839]
按评级稳定排序: [('000001', 0), ('601318', 0), ('000858', 1), ('600519', 2), ('600036', 2)]
r= 4: 遍数 d=8，理论代价 (b/r)(n+2^r) ≈  160128
r= 8: 遍数 d=4，理论代价 (b/r)(n+2^r) ≈   81024
r=11: 遍数 d=3，理论代价 (b/r)(n+2^r) ≈   66144
r=16: 遍数 d=2，理论代价 (b/r)(n+2^r) ≈  171072
lg n ≈ 14.3
落在 [20,35] 的个数: 146   直接数: 146

图 8.2、图 8.3 的结果与原书一致。"按评级稳定排序"一行中，评级同为 0 的 000001 与 601318、同为 2 的 600519 与 600036 都保持了原来的先后。基数排序对 \(r=4,8,11,16\) 都正确；理论代价在 \(r=11\)（接近 \(\lg n\approx14\)，且 \(32/11\) 向上取整只要 3 遍）时最小，\(r=16\) 时计数数组长 65536，比 \(n\) 还大，代价反而上升。

8.5.2 价格档位、成交量分布、分位数分组与均线

import numpy as np, pandas as pd
from scipy.stats import norm

rng = np.random.default_rng(8)

# ---------- (1) 价格离散化为整数 tick：计数排序 = 成交量分布（volume profile） ----------
tick = 0.01
px = np.round(10 + np.cumsum(rng.normal(0, 0.01, 50_000)), 2)     # 一天的逐笔成交价
vol = rng.integers(1, 50, px.size) * 100
lo = px.min()
idx = np.rint((px - lo) / tick).astype(int)          # 价格 -> 0..k 的整数下标
k = idx.max()
profile = np.bincount(idx, weights=vol, minlength=k + 1)      # 每个价位的成交量，Θ(n+k)
cum = np.concatenate([[0], np.cumsum(profile)])               # 前缀和，用于 O(1) 区间查询
def volume_between(p1, p2):                                    # [p1, p2] 价位区间内的总成交量
    i = int(round((p1 - lo) / tick)); j = int(round((p2 - lo) / tick))
    return cum[j + 1] - cum[i]
poc = lo + profile.argmax() * tick                            # 成交量最大的价位（POC）
print(f"价位数 k+1 = {k+1}，逐笔数 n = {px.size}，成交量最大价位 = {poc:.2f}")
print("区间 [poc-0.05, poc+0.05] 成交量占比 = %.3f" % (volume_between(poc - 0.05, poc + 0.05) / vol.sum()))
order = np.argsort(idx, kind="stable")                        # 按价位稳定排序，用作核对
assert np.array_equal(np.sort(px), px[order])

# ---------- (2) 桶排序 + 概率积分变换（练习 8.4-5）：已知分布时线性时间分组 ----------
def bucket_sort_known_cdf(x, cdf):
    n = len(x)
    B = [[] for _ in range(n)]
    for v in x:
        B[min(int(n * cdf(v)), n - 1)].append(v)       # P(X) ~ U[0,1)，均匀落入 n 个桶
    sizes = np.array([len(b) for b in B])
    out = [v for b in B for v in sorted(b)]             # 桶内元素很少，任何排序都行
    return out, sizes

n = 2000
z = rng.standard_normal(n)                              # 已标准化的因子得分，近似 N(0,1)
out, sizes = bucket_sort_known_cdf(z.tolist(), norm.cdf)
assert out == sorted(z.tolist())
print(f"桶大小平方均值 = {np.mean(sizes**2):.3f}，理论 E[n_i^2] = 2 - 1/n = {2 - 1/n:.4f}")

# 十分组：用 CDF 直接分桶 vs 按截面排名分组
dec_cdf = np.minimum((norm.cdf(z) * 10).astype(int), 9)
dec_rank = pd.qcut(pd.Series(z).rank(method="first"), 10, labels=False).to_numpy()
print("CDF 分组各组人数:", np.bincount(dec_cdf, minlength=10).tolist())
print("排名分组各组人数:", np.bincount(dec_rank, minlength=10).tolist())
print("两种分组一致的比例 = %.3f" % (dec_cdf == dec_rank).mean())

# 分布假设不对时（厚尾 t(3) 得分却按正态 CDF 分桶），桶就不均匀了
zt = rng.standard_t(3, n) / np.sqrt(3)                  # 方差为 1 的 t(3)
_, sizes_t = bucket_sort_known_cdf(zt.tolist(), norm.cdf)
print(f"厚尾数据按正态分桶: 桶大小平方均值 = {np.mean(sizes_t**2):.3f}，最大桶 = {sizes_t.max()}")

# ---------- (3) 思考题 8-5：k 有序 <=> 滑动 k 期均值单调不减 <=> A[i] <= A[i+k] ----------
p = 100 + np.cumsum(rng.normal(0.05, 1, 300))
kk = 20
ma = pd.Series(p).rolling(kk).mean().to_numpy()
up_ma = np.diff(ma[kk - 1:]) >= 0                      # 均线上行的日子
up_kk = p[kk:] >= p[:-kk]                              # 今日价格 >= k 日前价格
print("“均线上行”与“今日价 >= k 日前价”逐日一致:", bool(np.array_equal(up_ma, up_kk)))

输出：

价位数 k+1 = 326，逐笔数 n = 50000，成交量最大价位 = 10.67
区间 [poc-0.05, poc+0.05] 成交量占比 = 0.075
桶大小平方均值 = 2.003，理论 E[n_i^2] = 2 - 1/n = 1.9995
CDF 分组各组人数: [222, 212, 199, 178, 193, 194, 180, 200, 204, 218]
排名分组各组人数: [200, 200, 200, 200, 200, 200, 200, 200, 200, 200]
两种分组一致的比例 = 0.916
厚尾数据按正态分桶: 桶大小平方均值 = 2.238，最大桶 = 13
“均线上行”与“今日价 >= k 日前价”逐日一致: True

（1）价格档位就是天然的计数排序输入。 股票、期货价格只能落在最小变动价位（tick size）的整数倍上，一天之内的价格范围通常只有几百个价位，\(k\ll n\)。把价格换成整数价位下标后：np.bincount 一趟得到每个价位的成交量（成交量分布，volume profile），前缀和让"某价位区间成交了多少"变成 \(O(1)\) 查询，找成交最密集的价位（POC）也只要一次 argmax。同样的"值作下标"思想用于订单簿：在价格范围有限时，用一个按价位下标直接寻址的数组存放各档挂单量，读写某一档都是 \(O(1)\)，这是许多撮合引擎和行情重建程序的实际做法（比第 06 章的堆更快，代价是要预知价格范围）。

（2）桶排序与分位数分组。 因子研究中常把截面得分分成十组（十分组回测）。如果得分已经标准化且近似正态，用正态分布函数 \(\Phi\) 把它映射到 \([0,1)\) 后乘 10 取整，就能在 \(O(n)\) 内直接得到组号；把桶数取成 \(n\)，就是练习 8.4-5 的线性排序，实验中桶大小平方的均值 2.003 与理论值 \(2-1/n\) 吻合。但要清楚两者的区别：

• 按排名分组，每组恰好 \(n/10\) 只股票，与分布无关；排名需要排序（或第 09 章的选择算法）。
• 按假定分布的 CDF 分组，只在分布假设正确时近似等人数（实验中各组 178–222 只，与排名分组的一致率约 92%）；分布假设错了，桶就不均匀——厚尾数据按正态分桶时，最大的桶有 13 个元素，平方和也偏离了理论值。

实际研究中，截面分组一般用排名或经验分位数（pd.qcut），因为每期样本的分布并不稳定；按理论 CDF 分桶适合分布已知且稳定的场合（例如对已经做过排名-正态化的得分再分组，或对 p 值、均匀化后的分数分桶）。

（3）思考题 8-5 与均线。 若对所有 \(i\) 都有

称数组 \(A\) 是 \(k\) 有序的（\(k\)-sorted）。两边相减，左右两个和只差首尾两项，所以 \(k\) 有序当且仅当 \(A[i]\le A[i+k]\) 对所有 \(i\) 成立。翻译成交易语言：**\(k\) 日均线今天上行，等价于今天的价格不低于 \(k\) 日前的价格。**均线方向其实只是一个 \(k\) 期动量信号的符号，并不包含更多信息。实验逐日验证了这一点。原书在这道题里还给出：把下标模 \(k\) 同余的 \(k\) 个子序列各自排序，就能在 \(O(n\lg(n/k))\) 时间把数组变成 \(k\) 有序；反过来，把 \(k\) 有序的数组完全排序，可以用第 06 章的 \(k\) 路归并在 \(O(n\lg k)\) 内完成；而 \(k\) 为常数时，"\(k\) 排序"本身也需要 \(\Omega(n\lg n)\)。

8.6 其他思考题简介

以下内容与量化实践关系较弱，了解它们讲什么即可，需要时回原书。

• 水壶问题（思考题 8-4）：\(n\) 个红壶与 \(n\) 个蓝壶容量一一配对，只能拿一红一蓝比较。暴力配对 \(\Theta(n^2)\)；决策树给出 \(\Omega(n\lg n)\) 下界（\(n!\) 种配对、每次比较三种结果，高度至少 \(\log_3 n!\)）；随机选一个红壶划分蓝壶、找到配对的蓝壶再划分红壶，按快速排序的方式递归，期望 \(O(n\lg n)\)。这就是著名的"螺母与螺栓"问题。
• 0-1 排序引理与列排序（思考题 8-7）：无关比较交换算法（oblivious compare-exchange algorithm）的比较位置事先固定，与数据无关。0-1 排序引理说：这样的算法只要能排好所有 0-1 输入，就能排好任意输入。原书用它证明 Leighton 的列排序（columnsort）：在 \(r\times s\) 矩阵（\(r\) 偶数、\(s\) 整除 \(r\)、\(r\ge2s^2\)）上，交替做"各列排序"和固定置换，共 8 步完成排序。它适合并行和外存场景：每一步只需对能装进内存的一列排序。

本章小结

比较排序的决策树至少要有 \(n!\) 片叶子，所以高度至少 \(\lg n!=\Omega(n\lg n)\)；这个下界对最坏、平均、随机化情形都成立，归并排序和堆排序因此渐近最优。要更快，就必须利用比较以外的信息。计数排序把小范围整数当数组下标，三趟扫描完成，\(\Theta(n+k)\)，从后往前放置保证稳定。基数排序从最低位开始逐位稳定排序，\(b\) 位整数每遍取 \(r\approx\lg n\) 位时为 \(\Theta(bn/\lg n)\)。桶排序假设输入在 \([0,1)\) 上均匀，平均 \(\Theta(n)\)，关键是 \(E[n_i^2]=2-1/n\)；已知分布时用概率积分变换先化为均匀。量化里最常用的是"值作下标"：价格档位直方图、成交量分布、区间计数和按档位寻址的订单簿。

练习

基础

1. 演示计数排序作用于 \(\langle6,0,2,0,1,3,4,6,1,3,2\rangle\)，写出前缀和之后的 \(C\)。（练习 8.2-1） 答案要点：计数 \(C=\langle2,2,2,2,1,0,2\rangle\)，前缀和 \(\langle2,4,6,8,9,9,11\rangle\)，输出 \(\langle0,0,1,1,2,2,3,3,4,6,6\rangle\)。
2. 把计数排序第 8 行改成 for j = 1 to A.length，算法还正确吗？还稳定吗？（练习 8.2-3） 提示：正确但不稳定，同值元素次序反转。
3. 哪些排序算法是稳定的：插入、归并、堆、快速？给出让任意排序算法稳定的通用办法及其代价。（练习 8.3-2） 提示：插入、归并稳定；把原下标作为次关键字，额外 \(\Theta(n)\) 空间（每个下标 \(\lg n\) 位），时间只多常数因子。
4. 如何在 \(O(n)\) 时间内排序 \(n\) 个取值于 \(0..n^3-1\) 的整数？（练习 8.3-4） 提示：看成 3 位 \(n\) 进制数，基数排序 3 遍，每遍计数排序 \(\Theta(n)\)。
5. 设 A 股某日全市场约 5000 只股票的收益率已四舍五入到 0.01%，涨跌幅限制在 \(\pm20\%\) 内。说明如何在线性时间内得到全市场收益率的排序和任意分位数。 提示：映射为 \(0..4000\) 的整数，\(k=4001=O(n)\)，计数排序；前缀计数直接给出分位数位置。

进阶

6. 证明 \(\lg(n!)=\Theta(n\lg n)\)，不使用斯特林公式。（练习 8.1-2） 提示：上界 \(\lg n!\le n\lg n\)；下界只保留后一半项，每项至少 \(\lg(n/2)\)。
7. 用归纳法证明基数排序正确，并指出证明中哪一步用到了稳定性。（练习 8.3-3） 提示：见 8.3 节"为什么必须稳定"。
8. 给定 \(n\) 个 32 位整数，\(n=10^6\)。按 \((b/r)(n+2^r)\) 计算 \(r=8,16,20\) 时的代价，哪个最好？若考虑 cache（计数数组超过 L2 缓存会变慢），你会怎么选？ 提示：\(r=16\) 理论最好（2 遍，计数数组 65536）；\(r=20\) 要 2 遍且计数数组达百万级，cache 未命中多；实践中常取 8 或 11。
9. 练习 8.4-5★：从已知连续分布 \(P\) 抽样的 \(n\) 个数，给出平均线性时间的排序算法，并说明在因子十分组中用它的前提条件。 提示：对 \(P(X_i)\) 桶排序；前提是截面得分确实服从 \(P\) 且各股独立。
10. （思考题 8-5）证明把 \(k\) 有序数组完全排序需要 \(O(n\lg k)\) 时间，并说明为什么当 \(k\) 为常数时，把任意数组变成 \(k\) 有序仍需 \(\Omega(n\lg n)\)。 提示：\(k\) 个同余子序列各自有序，用 \(k\) 路归并；若 \(k\) 排序能 \(o(n\lg n)\)，再加 \(O(n\lg k)\) 的归并就能 \(o(n\lg n)\) 完全排序，与定理 8.1 矛盾。

原书推荐习题：8.1-3、8.1-4、8.2-3、8.2-4、8.3-2、8.3-4、8.4-2、8.4-5；思考题 8-1、8-4、8-5、8-6。

原书对照