第 09 章中位数与顺序统计量

学习目标

理解顺序统计量、上/下中位数的定义，知道选择问题为什么不需要排序。
掌握最小值需要恰好 \(n-1\) 次比较的锦标赛论证，以及同时求最小、最大值只需 \(3\lfloor n/2\rfloor\) 次比较的成对技巧。
掌握随机选择（quickselect）的算法与期望 \(O(n)\) 证明。
掌握"中位数的中位数"（BFPRT）算法，能推出 \(T(n)\le T(\lceil n/5\rceil)+T(7n/10+6)+O(n)=O(n)\)，并理解为什么分组大小取 5 而不是 3。
能把选择算法用在因子研究中：截面分位数、去极值（winsorize）、MAD 稳健标准化、Top-K 选股、十分组断点、成交量加权中位价。

读前导读

这一章在解决什么问题。 你每天做因子预处理时要算 1% 和 99% 分位数去极值、算中位数做稳健标准化、选出得分最高的 50 只股票——这些都是"找出第 \(i\) 小的那个数"，统称选择问题。直觉做法是先把 5000 只股票全部排序再取第 \(i\) 个，但这做了大量无用功：你只关心第 50 名是谁，并不关心第 3127 名和第 3128 名谁先谁后。本章证明：不排序也能找到第 \(i\) 小，而且只需与 \(n\) 成正比的时间，比排序的 \(n\lg n\) 更快。

本章两个算法的核心想法相同，都来自快速排序：随便挑一个"主元"，把比它小的放左边、比它大的放右边，然后看答案在哪边，只追那一边，另一边整个扔掉。区别在于怎么挑主元：随机挑（9.2 节，平均很快，偶尔很慢），或者用一个精心设计的方法保证主元"不太偏"（9.3 节，永远不会很慢，但平时较慢）。这种"期望好 vs 最坏有保证"的取舍，和你在风险管理里比较"平均损失"与"压力情景损失"是同一种思路。

本章结尾的带权中位数和你的工作关系最密切：它是成交量加权的"中位价"，对错单的抵抗力远强于 VWAP；数学上它是"使加权绝对偏差最小"的点，正如均值是"使平方偏差最小"的点。

需要先想起来的数学。

取整符号 \(\lfloor x\rfloor\)、\(\lceil x\rceil\)。 \(\lfloor x\rfloor\) 是向下取整（不超过 \(x\) 的最大整数），\(\lceil x\rceil\) 是向上取整。例：\(\lfloor3.5\rfloor=3\)，\(\lceil3.5\rceil=4\)，\(\lfloor7/2\rfloor=3\)。它们在证明中常用不等式 \(x-1<\lfloor x\rfloor\le x\le\lceil x\rceil<x+1\) 去掉。见第 00 册第 08 章读懂数学证明与符号。
等差数列求和与几何级数。 \(1+2+\cdots+m=\frac{m(m+1)}2\)；\(1+r+r^2+\cdots=\frac1{1-r}\)（\(0<r<1\)）。例：\(1+\frac34+(\frac34)^2+\cdots=4\)。后者就是永续年金公式的同一个式子。见第 00 册第 04 章级数与收敛。
期望的线性性与示性变量。 \(E[\sum_k X_kY_k]=\sum_kE[X_kY_k]\)，若 \(X_k\) 与 \(Y_k\) 独立则 \(=\sum_kE[X_k]E[Y_k]\)。示性变量 \(I\{A\}\) 的期望就是 \(\Pr\{A\}\)。见第 00 册第 07 章概率中的分析工具。
代入法（数学归纳法）证明递归式。 想证 \(T(n)\le cn\)：先假设对所有比 \(n\) 小的规模都成立，把它代入递归式右边，算出左边也 \(\le cn\)，再检查最小的几个规模。这是本册第 04b 章的方法，本章用了两次。归纳法的读法见第 00 册第 08 章。
绝对值函数的"导数"。 \(|x-p|\) 在 \(p<x\) 时对 \(p\) 的变化率是 \(-1\)，\(p>x\) 时是 \(+1\)。所以 \(\sum w_i|x_i-p|\) 对 \(p\) 的变化率 = 左侧权重和 − 右侧权重和。见第 00 册第 02 章导数与泰勒展开。

怎么读这一章。 必读：9.0 定义、9.2 的算法与"直觉上更简单"那段几何级数论证、9.3 的算法步骤与"主元为什么够好"、9.4 的 Top-K 和带权中位数、9.5 全部量化实战。9.2 的代入法长推导和 9.3 的递归式证明，第一次可以只看结论和下面的讲解框，回头再细读。"精确常数"和"小顺序统计量"可以跳过。

9.0 问题与定义

\(n\) 个元素的集合中，第 \(i\) 个顺序统计量（order statistic）是第 \(i\) 小的元素。最小值是第 1 个，最大值是第 \(n\) 个。中位数（median）是"中点"：\(n\) 为奇数时唯一，\(i=(n+1)/2\)；\(n\) 为偶数时有两个，下中位数（lower median）\(i=\lfloor(n+1)/2\rfloor\) 和上中位数（upper median）\(i=\lceil(n+1)/2\rceil\)。原书为简单起见，"中位数"一律指下中位数。注意统计软件的约定不同：np.median 在 \(n\) 为偶数时取两者平均，np.quantile 默认在相邻两个顺序统计量之间线性插值。

选择问题（selection problem）：

输入：\(n\) 个（互异的）数构成的集合 \(A\)，整数 \(1\le i\le n\)。
输出：\(A\) 中恰好比其他 \(i-1\) 个元素大的那个元素 \(x\)。

白话解释：顺序统计量就是"名次"。5000 只股票按因子得分从低到高排，第 1 名是最小值，第 5000 名是最大值，第 50 名就是"1% 分位附近的那只"。\(n=5000\) 为偶数时，下中位数是第 \(\lfloor5001/2\rfloor=2500\) 名，上中位数是第 \(\lceil5001/2\rceil=2501\) 名；np.median 会把两者取平均。选择问题的输入"整数 \(i\)"就是你要找的名次，输出是排在这个名次上的那个数。

排序后取第 \(i\) 个需要 \(O(n\lg n)\)。本章证明选择可以在 \(O(n)\) 内完成：9.1 节是最小值与最大值，9.2 节是期望线性时间的随机算法（实践中用它），9.3 节是最坏线性时间的确定性算法（理论意义更大）。为方便叙述，假设元素互异，但几乎所有结论都能推广到有重复值的情形。

9.1 最小值与最大值

最小值：\(n-1\) 次比较，且不能更少

依次扫描并记住目前的最小值，用 \(n-1\) 次比较：

MINIMUM(A)
1  min = A[1]
2  for i = 2 to A.length
3      if min > A[i]
4          min = A[i]
5  return min

这已经最优。把求最小值看作一场锦标赛：每次比较是一场比赛，小的获胜。除了冠军，每个元素都至少要输一场才能被排除，所以至少要 \(n-1\) 场比赛。

同时求最小值和最大值：\(3\lfloor n/2\rfloor\) 次

分别求两者要 \(2n-2\) 次比较。原书的应用例子是图形程序：要把 \((x,y)\) 数据缩放到屏幕上，需要先知道每个坐标的最小、最大值。量化里对应的是每根 K 线的最高价和最低价、每个截面因子的取值范围。

更好的办法是成对处理：先把一对元素互相比较，较小者再和当前最小值比，较大者再和当前最大值比。每 2 个元素 3 次比较，而不是 4 次。初值：\(n\) 为奇数时最小值和最大值都设为第一个元素，其余成对处理；\(n\) 为偶数时先比较前两个元素确定初值。比较次数为

n\text{ 奇数}:\ 3\lfloor n/2\rfloor;\qquad n\text{ 偶数}:\ 1+\frac{3(n-2)}{2}=\frac{3n}{2}-2 .

两种情况都不超过 \(3\lfloor n/2\rfloor\)。练习 9.1-2★ 用对手论证说明 \(\lceil3n/2\rceil-2\) 是下界，所以这个算法是最优的。

推导拆解：为什么成对处理能省？分别求时，每个新元素要和最小值比一次、和最大值比一次，共 2 次。成对处理时，先让两个新来的元素 \(a,b\) 互比 1 次，假设 \(a<b\)；那么 \(a\) 不可能是新的最大值（\(b\) 比它大），\(b\) 不可能是新的最小值，于是 \(a\) 只需和当前最小值比、\(b\) 只需和当前最大值比，各 1 次。两个元素共 3 次，平均每个 1.5 次。偶数情形的式子：前两个元素互比 1 次定初值，剩下 \(n-2\) 个元素组成 \((n-2)/2\) 对，每对 3 次，合计 \(1+\frac{3(n-2)}2=\frac{3n}2-2\)。交易里的对应：从一天的 tick 生成 K 线的最高价、最低价，就是这个问题；数据量大时，这 25% 的节省是实打实的。

第二小元素（练习 9.1-1）

用锦标赛（两两比较、胜者晋级）以 \(n-1\) 次比较找出最小值。第二小的元素只可能输给过冠军，而冠军一路只比了 \(\lceil\lg n\rceil\) 场，所以在这些手下败将里再找最小值，只需 \(\lceil\lg n\rceil-1\) 次比较，总共 \(n+\lceil\lg n\rceil-2\) 次。这个"记住谁输给了谁"的思想在思考题 9-3 中会再次出现。

9.2 期望线性时间的选择：RANDOMIZED-SELECT

算法

RANDOMIZED-SELECT 以快速排序为模型：随机划分，然后只在包含答案的一侧递归。快速排序要处理两侧，期望 \(\Theta(n\lg n)\)；随机选择只处理一侧，期望 \(\Theta(n)\)。它常被称为 quickselect，归功于 Hoare。

RANDOMIZED-SELECT(A, p, r, i)          // 返回 A[p..r] 中第 i 小的元素
1  if p == r
2      return A[p]                      // 此时必有 i == 1
3  q = RANDOMIZED-PARTITION(A, p, r)
4  k = q - p + 1                        // 低区元素个数 + 1（主元）
5  if i == k                            // 主元就是答案
6      return A[q]
7  elseif i < k
8      return RANDOMIZED-SELECT(A, p, q - 1, i)
9  else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

第 4 行算出主元 \(A[q]\) 在 \(A[p..r]\) 中的名次 \(k\)。若 \(i=k\)，主元就是答案；若 \(i<k\)，答案在低区，仍找第 \(i\) 小；若 \(i>k\)，低区和主元共 \(k\) 个元素都比答案小，所以在高区找第 \(i-k\) 小。看上去代码可能对空数组递归，练习 9.2-1 证明这不会发生（例如 \(i<k\) 时低区有 \(k-1\ge i\ge1\) 个元素）。

白话解释：用一个具体例子走一遍。要在 10 个数里找第 3 小。随机挑一个主元，划分后发现它是第 6 小（\(k=6\)）：左边 5 个都比它小，右边 4 个都比它大。第 3 小一定在左边那 5 个里，而且在那 5 个里仍是第 3 小，于是右边 4 个和主元直接扔掉。如果要找的是第 8 小，答案就在右边 4 个里；但左边 5 个加主元共 6 个都比它小，所以在右边要找的是第 \(8-6=2\) 小——这就是第 9 行 \(i-k\) 的来历。和快速排序的唯一区别是：快速排序两边都要继续排，这里只追一边。

最坏情况是 \(\Theta(n^2)\)，即使求最小值也可能如此：如果运气极差，每次都选到剩余元素中的最大者（练习 9.2-4 用 \(\langle3,2,9,0,7,5,4,8,6,1\rangle\) 求最小值，主元依次为 9、8、7、……、1）。但因为随机化，没有任何特定输入会稳定地触发最坏情况。

期望时间分析

设 \(T(n)\) 是在 \(n\) 个元素上的运行时间（随机变量）。主元等可能是任意一个元素，所以对每个 \(1\le k\le n\)，低区加主元恰有 \(k\) 个元素的概率为 \(1/n\)。定义 \(X_k=I\{A[p..q]\text{ 恰有 }k\text{ 个元素}\}\)，\(E[X_k]=1/n\)。

我们不知道答案会落在哪一侧。为求上界，假设它总落在较大的一侧（\(T\) 单调递增）。\(X_k=1\) 时两侧规模是 \(k-1\) 和 \(n-k\)：

T(n)\le\sum_{k=1}^{n}X_k\cdot T(\max(k-1,n-k))+O(n).

取期望。\(X_k\) 与后续递归中的随机选择独立（练习 9.2-2），所以

E[T(n)]\le\sum_{k=1}^{n}\frac1n E[T(\max(k-1,n-k))]+O(n).

当 \(k\) 从 1 走到 \(n\)，\(\max(k-1,n-k)\) 取遍 \(\lfloor n/2\rfloor\) 到 \(n-1\)，大部分值恰好出现两次（\(n\) 为奇数时 \(\lfloor n/2\rfloor\) 只出现一次），于是

E[T(n)]\le\frac2n\sum_{k=\lfloor n/2\rfloor}^{n-1}E[T(k)]+O(n).

推导拆解：从上一个式子到这个式子发生了两件事。 (1) 取期望时把 \(E[X_k\cdot T(\cdot)]\) 拆成 \(E[X_k]\cdot E[T(\cdot)]\)，依据是"这一轮选哪个主元"与"后面各轮选哪个主元"相互独立；再代入 \(E[X_k]=1/n\)。 (2) 合并重复项。取 \(n=6\) 看：\(k=1,\dots,6\) 时 \(\max(k-1,6-k)\) 依次是 \(5,4,3,3,4,5\)，每个值从 \(3=\lfloor6/2\rfloor\) 到 \(5=n-1\) 恰好出现两次，所以 \(\frac16(\cdots)\) 变成 \(\frac26\sum_{k=3}^{5}\)。\(n\) 为奇数时中间值只出现一次，写成"两次"只会让右边更大，上界仍然成立。这里的 \(\max\) 是"假设运气总是差的那一边"，和压力测试里取不利情景是同一个保守思路。

代入法证明 \(E[T(n)]\le cn\)。 设 \(O(n)\) 项不超过 \(an\)，并假设对小于某常数的 \(n\) 有 \(T(n)=O(1)\)。代入归纳假设：

\begin{aligned} E[T(n)]&\le\frac{2c}{n}\Big(\sum_{k=1}^{n-1}k-\sum_{k=1}^{\lfloor n/2\rfloor-1}k\Big)+an =\frac{2c}{n}\Big(\frac{(n-1)n}{2}-\frac{(\lfloor n/2\rfloor-1)\lfloor n/2\rfloor}{2}\Big)+an\\ &\le\frac{2c}{n}\Big(\frac{(n-1)n}{2}-\frac{(n/2-2)(n/2-1)}{2}\Big)+an =\frac cn\Big(\frac{3n^2}{4}+\frac n2-2\Big)+an\\ &\le\frac{3cn}{4}+\frac c2+an=cn-\Big(\frac{cn}{4}-\frac c2-an\Big). \end{aligned}

只要 \(\frac{cn}{4}-\frac c2-an\ge0\)，即 \(n(c/4-a)\ge c/2\)。取 \(c>4a\)，则对 \(n\ge\frac{2c}{c-4a}\) 成立；更小的 \(n\) 由 \(T(n)=O(1)\) 覆盖。所以 \(E[T(n)]=O(n)\)：任意顺序统计量，特别是中位数，都能在期望线性时间内求出。

直觉上更简单：每次划分后，期望至少丢掉约四分之一的元素，所以总工作量像几何级数 \(n+\frac34n+(\frac34)^2n+\cdots\le4n\)。

推导拆解：上面的代入法长式子，逐行看用了什么。第一行：把归纳假设 \(E[T(k)]\le ck\) 代入，\(\frac2n\sum_{k=\lfloor n/2\rfloor}^{n-1}ck\)。从 \(\lfloor n/2\rfloor\) 加到 \(n-1\)，等于"从 1 加到 \(n-1\)"减去"从 1 加到 \(\lfloor n/2\rfloor-1\)"，两段都用等差数列公式 \(1+\cdots+m=m(m+1)/2\)。第二行：减号后面那项要变小才能让整体变大（我们在求上界），所以用 \(\lfloor n/2\rfloor\ge n/2-1\) 把它换成更小的 \((n/2-2)(n/2-1)/2\)。然后展开化简：\(\frac{(n-1)n}2-\frac{(n/2-2)(n/2-1)}2=\frac12\big(\frac{3n^2}4+\frac n2-2\big)\)，乘以 \(\frac{2c}n\) 得到 \(\frac cn(\frac{3n^2}4+\frac n2-2)\)。第三行：扔掉 \(-2\)（让式子变大），得 \(\frac{3cn}4+\frac c2+an\)，再把它写成"\(cn\) 减去一个括号"，目的是看出括号非负时结论成立。括号非负的条件 \(n(c/4-a)\ge c/2\)：只要 \(c\) 比 \(4a\) 大，\(n\) 足够大时左边随 \(n\) 线性增长，总会超过常数 \(c/2\)。这是代入法的标准收尾：选够大的常数 \(c\)，让"多出来的工作量 \(an\)"被"省下来的 \(cn/4\)"吸收。几何级数那句话中的 \(\frac34\) 来自：随机主元的名次平均落在中间，较大的一侧期望约占 \(\frac34n\)。

精确常数（思考题 9-4）

仿照快速排序的分析（第 07 章），把元素按大小记为 \(z_1<\cdots<z_n\)，求 \(z_k\) 时，\(z_i\) 与 \(z_j\)（\(i<j\)）被比较当且仅当 \(\{z_{\min(i,k)},\dots,z_{\max(j,k)}\}\) 中第一个被选为主元的是 \(z_i\) 或 \(z_j\)，概率为

E[X_{ijk}]=\frac{2}{\max(j,k)-\min(i,k)+1}.

对所有数对求和可证 \(E[X_k]\le4n\)。更精细的计算（Knuth）表明：求最小值期望约 \(2n\) 次比较，求中位数期望约 \(2(1+\ln2)n\approx3.39n\) 次。下面的实验会看到相近的数字。

9.3 最坏线性时间的选择：SELECT（中位数的中位数）

算法

SELECT 同样是"划分后只在一侧递归"，但它保证主元足够好。对 \(n>1\) 个互异元素求第 \(i\) 小（\(n=1\) 时直接返回）：

把 \(n\) 个元素分成 \(\lfloor n/5\rfloor\) 组、每组 5 个，外加至多一组 \(n\bmod 5\) 个。
对 \(\lceil n/5\rceil\) 组中的每一组用插入排序排好，取出组中位数。
递归调用 SELECT，求这 \(\lceil n/5\rceil\) 个组中位数的中位数 \(x\)（偶数个时取下中位数）。
以 \(x\) 为主元，用修改过的 PARTITION（主元作为参数传入）划分输入。设低区元素个数加 1 为 \(k\)，则 \(x\) 是第 \(k\) 小，高区有 \(n-k\) 个元素。
若 \(i=k\) 返回 \(x\)；若 \(i<k\) 在低区递归求第 \(i\) 小；若 \(i>k\) 在高区递归求第 \(i-k\) 小。

主元为什么够好

把每组 5 个元素排成一列，组中位数在中间（原书图 9.1）。至少一半的组中位数 \(\ge x\)。这些组中，每组至少有 3 个元素大于 \(x\)（组中位数本身和它上面的两个），但要扣除两个例外组：不足 5 个元素的那组，以及 \(x\) 自己所在的组。所以大于 \(x\) 的元素至少有

3\Big(\Big\lceil\frac12\Big\lceil\frac n5\Big\rceil\Big\rceil-2\Big)\ge\frac{3n}{10}-6

个。同理，小于 \(x\) 的元素也至少有 \(3n/10-6\) 个。因此第 5 步的递归规模最多是 \(7n/10+6\)。

白话解释：想象把 100 只股票分成 20 个小组，每组 5 只按得分从低到高竖着排，中间那只是组长。再把 20 个组长按得分从左到右排，取中间那位组长作为 \(x\)。看 \(x\) 右边的 10 个组长（含 \(x\) 所在组）：每个组长自己比 \(x\) 高（或就是 \(x\)），组里排在组长上面的 2 只又比组长高，所以每组至少 3 只股票 \(\ge x\)。10 组 × 3 只 = 30 只，即至少 \(3n/10\) 个元素大于等于 \(x\)。"\(-6\)"是扣掉两个可能不满员或包含 \(x\) 本身的组的保守修正。结论：\(x\) 不会太靠边，左右两边都至少有 30%，所以无论答案在哪边，下一轮最多剩 70%。公式里的 \(\lceil\frac12\lceil n/5\rceil\rceil\)：\(\lceil n/5\rceil\) 是组数，再取一半向上取整，就是"至少一半的组"。

递归式与线性证明

第 1、2、4 步是 \(O(n)\)（第 2 步是 \(O(n)\) 次对常数规模集合的插入排序），第 3 步是 \(T(\lceil n/5\rceil)\)，第 5 步至多 \(T(7n/10+6)\)：

T(n)\le\begin{cases}O(1),&n<140,\\ T(\lceil n/5\rceil)+T(7n/10+6)+O(n),&n\ge140.\end{cases}

用代入法证明 \(T(n)\le cn\)。设 \(O(n)\) 项不超过 \(an\)：

T(n)\le c\lceil n/5\rceil+c(7n/10+6)+an\le\frac{cn}{5}+c+\frac{7cn}{10}+6c+an=cn+\Big(-\frac{cn}{10}+7c+an\Big).

需要 \(-cn/10+7c+an\le0\)，即当 \(n>70\) 时 \(c\ge10a\cdot\frac{n}{n-70}\)。因为 \(n\ge140\) 时 \(\frac{n}{n-70}\le2\)，取 \(c\ge20a\) 即可。常数 140 没有特别含义，任何大于 70 的整数都可以，只需相应调整 \(c\)。

关键在于 \(\frac15+\frac{7}{10}=\frac{9}{10}<1\)：两个子问题的规模之和严格小于 \(n\) 的一个固定比例，递归树每层的总工作量按几何级数衰减，总和是 \(O(n)\)。

推导拆解：忽略 \(+6\) 和取整，把递归画成一棵树。第 0 层处理 \(n\) 个元素，花 \(an\)；它产生两个子问题，规模 \(n/5\) 和 \(7n/10\)，第 1 层合计工作 \(a\cdot\frac9{10}n\)；每个子问题又按同样比例拆，第 2 层合计 \(a(\frac9{10})^2n\)……总工作 \(an(1+0.9+0.9^2+\cdots)=10an\)。这正是 \(c\ge10a\) 的来源（上面取 \(20a\) 是为了吸收 \(+7c\) 这些零头）。对比分组大小为 3 的情形：比例和 \(\frac13+\frac23=1\)，每层工作量都是 \(an\) 不衰减，层数约 \(\log n\)，总和就成了 \(n\log n\)。所以"比例和小于 1"是线性的分水岭——这和"增长率 \(g\) 小于贴现率 \(r\) 时永续增长年金才有有限现值"是同一个几何级数收敛条件。

分组大小（练习 9.3-1）

每组 7 个：大于 \(x\) 的元素至少 \(4(\lceil\frac12\lceil n/7\rceil\rceil-2)\ge\frac{2n}{7}-8\)，递归式 \(T(n)\le T(\lceil n/7\rceil)+T(5n/7+8)+O(n)\)，\(\frac17+\frac57<1\)，仍是线性。
每组 3 个：递归式变成 \(T(n)\le T(n/3)+T(2n/3+4)+O(n)\)，\(\frac13+\frac23=1\)，每层工作量不衰减，只能得到 \(O(n\lg n)\)，证不出线性。

与排序下界的关系

SELECT 和 RANDOMIZED-SELECT 都只通过比较获得顺序信息，却不受 \(\Omega(n\lg n)\) 的约束——因为它们没有排序。第 08 章的线性时间排序要对输入做假设；本章的线性时间选择不需要任何假设。所以"先排序再取第 \(i\) 个"在渐近意义上是浪费。

SELECT 的常数很大（下面实验中约 \(13n\) 次比较，而 quickselect 求中位数的理论期望约 \(3.39n\)），实践中很少直接用。它的价值在于两点：理论上给出最坏保证；工程上作为保底——NumPy 的 np.partition 用的 introselect 就是先跑 quickselect，发现进展不佳时切换到中位数的中位数，从而兼得两者的优点。

用线性选择构造其他算法

最坏 \(O(n\lg n)\) 的快速排序（练习 9.3-3）：用 SELECT 找中位数作主元，\(T(n)=2T(n/2)+O(n)\)。
用中位数黑盒求任意顺序统计量（练习 9.3-5）：用中位数划分，只在一侧递归，\(T(n)=T(n/2)+O(n)=O(n)\)。
\(k\) 分位数（练习 9.3-6）：\(n\) 元集合的 \(k\) 分位数（\(k\)th quantiles）是把有序集合分成 \(k\) 个大小相等（误差至多 1）部分的 \(k-1\) 个顺序统计量。先选出最中间的那个分位点并划分，两侧递归；递归深度 \(\lg k\)，每层总工作 \(O(n)\)，合计 \(O(n\lg k)\)。十分组只需 \(O(n\lg10)\)，而全排序是 \(O(n\lg n)\)。
离中位数最近的 \(k\) 个数（练习 9.3-7）：求中位数，算出各元素到它的距离，再选第 \(k\) 小的距离并划分，\(O(n)\)。
两个有序数组的中位数（练习 9.3-8）：\(X[1..n]\)、\(Y[1..n]\) 各自有序，比较两者的中位数，扔掉不可能含答案的一半，二分下去，\(O(\lg n)\)。
只用比较求第 \(i\) 小时的附带结果（练习 9.3-4★）：比较记录已经确定了谁比答案小、谁比答案大，不需要额外比较就能列出比它小的 \(i-1\) 个和比它大的 \(n-i\) 个元素。
输油管选址（练习 9.3-9）：一条东西向主输油管要经过 \(n\) 口油井的油田，每口井用南北向支线连到主管。支线总长 \(\sum_i|y_i-y|\) 由各井 \(y\) 坐标的中位数最小化，可在线性时间求出。这是"中位数最小化绝对偏差和"最直观的例子。

9.4 思考题精要

Top-K 有序输出（思考题 9-1）：要按顺序列出最大的 \(i\) 个数，三种做法：

方法	时间
(a) 全排序，取最后 \(i\) 个	\(O(n\lg n+i)\)
(b) 建最大堆，EXTRACT-MAX \(i\) 次	\(O(n+i\lg n)\)
(c) 选出第 \(i\) 大，围绕它划分，再对最大的 \(i\) 个排序	\(O(n+i\lg i)\)

方法 (c) 最好。它对应 NumPy 的 argpartition 加一次小排序。第 06 章的流式最小堆是 \(O(n\lg i)\)，适合数据逐条到达、不能整体装入内存的场景。

带权中位数（思考题 9-2）：\(n\) 个互异元素 \(x_1,\dots,x_n\)，正权重 \(w_1,\dots,w_n\)，\(\sum w_i=1\)。带权（下）中位数是满足

\sum_{x_i<x_k}w_i<\frac12\qquad\text{且}\qquad\sum_{x_i>x_k}w_i\le\frac12

的元素 \(x_k\)。原书的例子：元素 \(0.1,0.35,0.05,0.1,0.15,0.05,0.2\)，权重等于元素值，则中位数是 0.1，带权中位数是 0.2。

权重都是 \(1/n\) 时，带权中位数就是普通中位数。
排序后累加权重，到首次达到 \(1/2\) 为止，\(O(n\lg n)\)。
用线性时间选择：求当前子集的中位数并划分，比较低区权重和与 \(1/2\)，只在一侧递归，\(T(n)=T(n/2)+\Theta(n)=\Theta(n)\)。
邮局选址问题（post-office location problem）：求点 \(p\) 最小化 \(\sum_iw_i\,d(p,p_i)\)。一维且 \(d(a,b)=|a-b|\) 时，最优解就是带权中位数。证明思路：把 \(p\) 向右移动一点，左侧点的距离都增加、右侧点都减少，目标函数的变化率是"左侧权重和减右侧权重和"；带权中位数正是这个变化率由负变非负的位置。二维曼哈顿距离 \(|x_1-x_2|+|y_1-y_2|\) 下，目标函数按坐标可分离，\(x\)、\(y\) 各取带权中位数即可。

金融直觉：均值和中位数的分工可以用"损失函数"一句话说清：均值让平方偏差之和最小，中位数让绝对偏差之和最小。 对 \(\sum w_i(x_i-p)^2\) 求导令其为 0，得 \(p=\sum w_ix_i\)，就是 VWAP；对 \(\sum w_i|x_i-p|\)，变化率是"左侧权重 − 右侧权重"，它从负变正的点就是带权中位数。平方会放大远处的点，所以一笔离谱的错单能把 VWAP 拉走很远；绝对值对远近一视同仁，错单只算"一票"，带权中位数几乎不动。这就是 9.5.3 节实验里 VWAP 从 20.00 掉到 17.84、而中位价只动了一分钱的原因。用原书例子核对定义：按元素排序为 \(0.05,0.05,0.1,0.1,0.15,0.2,0.35\)，每个元素的权重就是它自己。看 0.15：左侧权重和 \(0.05+0.05+0.1+0.1=0.3<0.5\)，但右侧和 \(0.2+0.35=0.55>0.5\)，不满足。看 0.2：左侧和 \(0.3+0.15=0.45<0.5\)，右侧和 \(0.35\le0.5\)，两个条件都满足，所以带权中位数是 0.2。普通中位数是第 4 个元素 0.1，两者差别来自 0.35 这个"大权重"把重心拉向右边。

小顺序统计量（思考题 9-3，了解即可）：当 \(i\) 远小于 \(n\) 时，可以先做 \(\lfloor n/2\rfloor\) 次两两比较，在所有"较小者"组成的集合上递归求最小的 \(i\) 个；答案一定在这 \(i\) 个及其配对元素共 \(2i\) 个元素中。比较次数 \(U_i(n)=\lfloor n/2\rfloor+U_i(\lceil n/2\rceil)+T(2i)\)，可证 \(i<n/2\) 时 \(U_i(n)=n+O(T(2i)\lg(n/i))\)；\(i\) 为常数时只需 \(n+O(\lg n)\) 次比较。

章末注记：最坏线性时间的中位数算法由 Blum、Floyd、Pratt、Rivest、Tarjan 设计（俗称 BFPRT），快速的随机版本归功于 Hoare，Floyd 与 Rivest 又提出了围绕小样本递归选主元的改进版（Floyd–Rivest 算法，平均约 \(1.5n\) 次比较求中位数）。求中位数到底需要多少次比较至今未知：已知下界约 \((2+\epsilon)n\)，上界略小于 \(2.95n\)。

9.5 量化实战

9.5.1 选择算法的比较次数

import random
import numpy as np

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

def min_and_max(A, c):
    """成对处理：每两个元素 3 次比较，总共至多 3*floor(n/2) 次。"""
    n = len(A)
    if n % 2:
        mn = mx = A[0]; start = 1
    else:
        c.cmp += 1
        mn, mx = (A[0], A[1]) if A[0] < A[1] else (A[1], A[0]); start = 2
    for i in range(start, n, 2):
        c.cmp += 3
        a, b = (A[i], A[i + 1]) if A[i] < A[i + 1] else (A[i + 1], A[i])
        if a < mn: mn = a
        if b > mx: mx = b
    return mn, mx

def randomized_select(A, i, c):
    """迭代版 RANDOMIZED-SELECT（练习 9.2-3）：返回第 i 小（i 从 1 开始），原地、期望 Θ(n)。"""
    p, r = 0, len(A) - 1
    while True:
        if p == r:
            return A[p]
        k = random.randint(p, r); A[k], A[r] = A[r], A[k]
        x, s = A[r], p - 1                                  # Lomuto 划分
        for j in range(p, r):
            c.cmp += 1
            if A[j] <= x:
                s += 1; A[s], A[j] = A[j], A[s]
        q = s + 1; A[q], A[r] = A[r], A[q]
        k = q - p + 1
        if i == k:
            return A[q]
        elif i < k:
            r = q - 1
        else:
            p, i = q + 1, i - k

def select_bfprt(A, i, c):
    """最坏线性时间 SELECT（中位数的中位数）。为清晰起见用列表推导，非原地。"""
    if len(A) <= 5:
        c.cmp += len(A) * (len(A) - 1) // 2                  # 小规模直接排序，按比较次数上界计
        return sorted(A)[i - 1]
    medians = []
    for j in range(0, len(A), 5):
        g = sorted(A[j:j + 5]); c.cmp += len(g) * (len(g) - 1) // 2
        medians.append(g[(len(g) - 1) // 2])                # 每组的下中位数
    x = select_bfprt(medians, (len(medians) + 1) // 2, c)   # 中位数的中位数
    low = [a for a in A if a < x]; high = [a for a in A if a > x]
    c.cmp += 2 * len(A)                                    # 按实现计：每个元素与 x 比两次
    k = len(low) + 1
    if i == k:  return x
    if i < k:   return select_bfprt(low, i, c)
    return select_bfprt(high, i - k, c)

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

for n in (1001, 1000):
    x = rng.permutation(n).tolist(); c = Counter()
    print(f"n={n}: min/max = {min_and_max(x, c)}，比较 {c.cmp} 次，3*floor(n/2) = {3*(n//2)}，2n-2 = {2*n-2}")

n = 100_001
data = rng.standard_normal(n)
med_true = np.partition(data, n // 2)[n // 2]
for name, i in [("最小值", 1), ("1% 分位", n // 100), ("中位数", (n + 1) // 2)]:
    cs = []
    for _ in range(50):
        c = Counter(); v = randomized_select(data.tolist(), i, c); cs.append(c.cmp)
        assert v == np.partition(data, i - 1)[i - 1]
    print(f"quickselect 求{name}: 平均比较 {np.mean(cs)/n:.2f}n")
c = Counter(); v = select_bfprt(data.tolist(), (n + 1) // 2, c)
assert v == med_true
print(f"BFPRT 求中位数: 比较 {c.cmp/n:.2f}n（最坏线性，但常数大）")

输出：

n=1001: min/max = (0, 1000)，比较 1500 次，3*floor(n/2) = 1500，2n-2 = 2000
n=1000: min/max = (0, 999)，比较 1498 次，3*floor(n/2) = 1500，2n-2 = 1998
quickselect 求最小值: 平均比较 1.93n
quickselect 求1% 分位: 平均比较 2.14n
quickselect 求中位数: 平均比较 3.22n
BFPRT 求中位数: 比较 13.06n（最坏线性，但常数大）

成对求最小、最大值：\(n=1001\) 恰好 \(3\lfloor n/2\rfloor=1500\) 次，\(n=1000\) 是 \(3n/2-2=1498\) 次，都比分别求的 \(2n-2\) 少四分之一。
quickselect 求最小值、1% 分位、中位数的平均比较次数分别接近 \(2n\)、略多于 \(2n\) 和 \(3.39n\)（单次波动较大，50 次平均仍有几个百分点的误差）。离两端越近，丢掉的元素越多，越快。
BFPRT 的比较次数约 \(13n\)（按本实现的计法），是 quickselect 的约 4 倍，印证了"理论保证好、常数大"。

9.5.2 截面分位数、去极值、Top-K 与十分组断点

因子研究的标准预处理流程是：每个交易日对全市场截面做去极值（winsorize）、标准化，再按分位数分组。所有这些"分位数"都是选择问题，而不是排序问题。

import time, heapq
import numpy as np

rng = np.random.default_rng(9)
T, N = 250, 5000                                    # 250 个交易日 × 5000 只股票
F = rng.standard_t(3, (T, N))                       # 厚尾的原始因子值
F[rng.random((T, N)) < 0.001] *= 50                 # 少量脏数据（错价、单位错误）

def quantile_by_partition(X, q):
    """按行求分位数，结果与 np.quantile(method='linear') 完全相同，但只用选择、不全排序。"""
    n = X.shape[1]
    h = (n - 1) * np.asarray(q)
    lo = np.floor(h).astype(int); hi = np.minimum(lo + 1, n - 1)
    P = np.partition(X, np.unique(np.r_[lo, hi]), axis=1)   # 一次 introselect 定位所有需要的顺序统计量
    return P[:, lo] + (h - lo) * (P[:, hi] - P[:, lo])

# (1) 去极值（winsorize，1%/99%）与 MAD 稳健标准化
def quantile_by_sort(X, q):                                   # 对照：先整行排序再取
    n = X.shape[1]; h = (n - 1) * np.asarray(q)
    lo = np.floor(h).astype(int); hi = np.minimum(lo + 1, n - 1)
    S = np.sort(X, axis=1)
    return S[:, lo] + (h - lo) * (S[:, hi] - S[:, lo])
def best_time(f, *a, rep=5):
    ts = []
    for _ in range(rep):
        t0 = time.perf_counter(); r = f(*a); ts.append(time.perf_counter() - t0)
    return r, min(ts)
Q1, t_sort = best_time(quantile_by_sort, F, [0.01, 0.99])
Q2, t_part = best_time(quantile_by_partition, F, [0.01, 0.99])
assert np.allclose(Q1, Q2) and np.allclose(Q2, np.quantile(F, [0.01, 0.99], axis=1).T)
print(f"250×5000 截面分位数: 全排序 {1e3*t_sort:.1f}ms，partition {1e3*t_part:.1f}ms")

W = np.clip(F, Q2[:, [0]], Q2[:, [1]])                        # 截面去极值
med = quantile_by_partition(F, [0.5])
mad = quantile_by_partition(np.abs(F - med), [0.5])
Z = (F - med) / (1.4826 * mad)                                # 稳健 z 分数（正态下 1.4826·MAD ≈ σ）
print("原始因子最大绝对值 %.1f，去极值后 %.2f" % (np.abs(F).max(), np.abs(W).max()))
Zs = (F - F.mean(1, keepdims=True)) / F.std(1, keepdims=True)   # 均值/标准差标准化
iqr = lambda Z: np.median(np.subtract(*np.percentile(Z, [75, 25], axis=1)))
print("z 分数的截面四分位距(中位数): 均值/标准差法 %.2f，中位数/MAD 法 %.2f（正态应为 1.35）"
      % (iqr(Zs), iqr(Z)))

# (2) Top-K（思考题 9-1）：三种方法得到同一个有序列表
x = F[0]; k = 50
t0 = time.perf_counter(); a = np.argsort(-x)[:k]; t1 = time.perf_counter()               # (a) 全排序
b = [i for _, i in heapq.nlargest(k, zip(x, range(N)))]; t2 = time.perf_counter()       # (b) 堆
idx = np.argpartition(-x, k - 1)[:k]; c = idx[np.argsort(-x[idx])]; t3 = time.perf_counter()  # (c) 选择 + 排前 k
assert list(a) == b == list(c)
print(f"Top-{k}: 全排序 {1e3*(t1-t0):.2f}ms，堆 {1e3*(t2-t1):.2f}ms，argpartition+排序 {1e3*(t3-t2):.2f}ms")

# (3) k 分位数（练习 9.3-6）：递归“选中间那个分位点再划分”，O(n lg k)
def k_quantiles(A, k):
    """返回把有序 A 分成 k 等份的 k-1 个顺序统计量（第 ceil(j*n/k) 小，j=1..k-1）。"""
    n = len(A); ranks = [-(-j * n // k) for j in range(1, k)]   # 目标名次（1 起始）
    out = {}
    def rec(arr, offset, rs):
        if not rs: return
        mid = rs[len(rs) // 2]                                  # 中间那个分位点
        P = np.partition(arr, mid - offset - 1)                 # 线性时间选择
        out[mid] = P[mid - offset - 1]
        rec(P[:mid - offset - 1], offset, [r for r in rs if r < mid])
        rec(P[mid - offset:], mid, [r for r in rs if r > mid])
    rec(np.asarray(A), 0, ranks)
    return [out[r] for r in ranks]
qs = k_quantiles(F[0], 10)
s = np.sort(F[0]); ref = [s[-(-j * N // 10) - 1] for j in range(1, 10)]
assert np.allclose(qs, ref)
print("十分位断点:", np.round(qs, 3).tolist())

输出：

250×5000 截面分位数: 全排序 19.3ms，partition 9.4ms
原始因子最大绝对值 1074.0，去极值后 5.35
z 分数的截面四分位距(中位数): 均值/标准差法 0.58，中位数/MAD 法 1.35（正态应为 1.35）
Top-50: 全排序 0.21ms，堆 0.29ms，argpartition+排序 0.03ms
十分位断点: [-1.691, -1.005, -0.599, -0.28, 0.006, 0.288, 0.581, 0.993, 1.639]

（1）分位数用选择，不用排序。 quantile_by_partition 先算出线性插值需要的两个名次，再用 np.partition 一次定位，结果与 np.quantile 的默认方法完全一致（np.quantile 内部本来就是这样做的）。在 \(250\times5000\) 的面板上它比整行排序快一倍左右；数据越大、需要的分位点越少，差距越明显。当你要对"每日 × 全市场 × 几十个因子"重复做去极值时，这个差别会累积成可观的计算时间。

（2）稳健标准化。 原始因子中掺了千分之一的脏数据，最大绝对值上千。只看一个指标：用均值、标准差标准化后，截面 \(z\) 分数的四分位距只有 0.58——少数极端值把标准差撑大了，绝大多数正常股票被压缩到 0 附近，因子区分度大降；用中位数和 MAD（median absolute deviation，中位数绝对偏差）标准化后，四分位距是 1.35，正好是正态分布的值。常数 1.4826 来自正态分布：\(\sigma\approx1.4826\times\text{MAD}\)。中位数和 MAD 都只需要两次线性时间选择。业界常用的"中位数去极值"（把超过中位数 \(\pm5\times1.4826\,\text{MAD}\) 的值截断）也是同一套计算。

（3）Top-K 选股。 按思考题 9-1(c) 的做法，argpartition 先在 \(O(n)\) 内选出前 50 名，再只对这 50 个排序，结果与全排序、堆方法完全相同，速度快数倍。

（4）十分组断点。 按练习 9.3-6 的 \(O(n\lg k)\) 递归：先选出第 5 个断点（中位数）并划分，左右两侧各自继续找自己的断点。结果与"全排序后取第 \(\lceil jn/k\rceil\) 个"一致。实践中直接调用 np.partition(x, kth=[...]) 一次传入所有名次即可，内部做的也是类似的递归划分。

9.5.3 带权中位数：成交量加权中位价

import numpy as np

def weighted_median(x, w):
    """思考题 9-2(c)：带权（下）中位数，期望线性时间。
    每轮用选择算法找当前子集的中位数作主元，比较左侧权重和，只在一侧继续：T(n)=T(n/2)+Θ(n)。"""
    x = np.asarray(x, float); w = np.asarray(w, float); w = w / w.sum()
    left_acc = 0.0                                  # 已确定在答案左侧的权重
    while True:
        n = len(x)
        if n == 1:
            return x[0]
        m = (n - 1) // 2
        order = np.argpartition(x, m)               # 线性时间选择（introselect）
        x, w = x[order], w[order]
        wl = left_acc + w[:m].sum()                 # 严格小于主元的总权重
        if wl < 0.5 and wl + w[m] >= 0.5:           # 满足定义：左侧 < 1/2，右侧 <= 1/2
            return x[m]
        if wl >= 0.5:
            x, w = x[:m], w[:m]                     # 答案在左半
        else:
            left_acc = wl + w[m]; x, w = x[m + 1:], w[m + 1:]

# 原书例子：元素 = 权重
v = [0.1, 0.35, 0.05, 0.1, 0.15, 0.05, 0.2]
print("中位数 =", sorted(v)[(len(v) - 1) // 2], " 带权中位数 =", weighted_median(v, v))

# 与排序法（思考题 9-2(b)）对照
rng = np.random.default_rng(10)
for _ in range(500):
    n = rng.integers(1, 200); x = rng.normal(size=n); w = rng.random(n)
    o = np.argsort(x); cw = np.cumsum(w[o]) / w.sum()
    assert weighted_median(x, w) == x[o][np.searchsorted(cw, 0.5)]
print("500 组随机测试与排序法一致")

# 成交量加权中位价 vs VWAP：一笔错误的大单
px = np.round(20 + rng.normal(0, 0.05, 3000), 2)
vol = rng.integers(1, 100, 3000) * 100
px_bad, vol_bad = px.copy(), vol.copy()
px_bad[100], vol_bad[100] = 2.0, 2_000_000         # 一笔价格少了一位、数量巨大的错单
for tag, p, q in [("干净数据", px, vol), ("含错单", px_bad, vol_bad)]:
    print(f"{tag}: VWAP = {np.average(p, weights=q):.4f}，成交量加权中位价 = {weighted_median(p, q):.4f}")

# 一维邮局选址（9-2(d)）：带权中位数最小化 Σ w|x - p|
grid = np.linspace(19.8, 20.2, 4001)
cost = [np.sum(vol * np.abs(px - g)) for g in grid]
print("网格搜索的最优点 = %.4f，带权中位数 = %.4f" % (grid[int(np.argmin(cost))], weighted_median(px, vol)))

输出：

中位数 = 0.1  带权中位数 = 0.2
500 组随机测试与排序法一致
干净数据: VWAP = 20.0009，成交量加权中位价 = 20.0000
含错单: VWAP = 17.8407，成交量加权中位价 = 19.9900
网格搜索的最优点 = 20.0000，带权中位数 = 20.0000

带权中位数算法每轮用 argpartition 选中位数作主元，比较左侧权重，只保留一半，期望线性时间；500 组随机数据与排序法结果一致。

量化含义有三层：

稳健的参考价。 一笔"价格少写一位、数量巨大"的错单把 VWAP（成交量加权均价）从 20.00 拉到 17.84，而成交量加权中位价只从 20.00 变到 19.99。在做 tick 数据清洗、计算收盘参考价或评估执行价格时，带权中位数是比加权均值稳健得多的选择。
L1 最优性。 网格搜索确认，带权中位数就是 \(\sum_iw_i|x_i-p|\) 的最小点（邮局选址的一维情形）。若执行成本与成交价偏离某个参考价的绝对距离成正比，带权中位数就是最优参考价；最小绝对偏差回归与分位数回归（第 05 册）的一阶条件也正是"带权中位数条件"。
与第 06 章的联系。 静态截面上用选择算法；时间序列上逐日滚动时，用第 06 章的双堆结构维护滚动中位数，每步 \(O(\lg w)\)。两者是同一问题在批处理与流式两种场景下的解法。

本章小结

选择问题求第 \(i\) 小的元素，不需要排序就能在线性时间内解决。最小值需要且只需要 \(n-1\) 次比较；同时求最小、最大值成对处理只需 \(3\lfloor n/2\rfloor\) 次。RANDOMIZED-SELECT 像快速排序一样随机划分，但只在一侧递归，期望 \(\Theta(n)\)、最坏 \(\Theta(n^2)\)，是实践中的主力（NumPy np.partition 的核心）。SELECT 用"5 个一组取中位数，再取中位数的中位数"保证每侧至少丢掉 \(3n/10-6\) 个元素，靠 \(\frac15+\frac7{10}<1\) 得到最坏线性时间，常数较大，适合作保底。量化研究中，截面分位数、去极值、MAD 标准化、Top-K、分组断点、带权中位数都是选择问题，应该用 partition 系列函数而不是全排序。

概念/公式	内容
下/上中位数	\(i=\lfloor(n+1)/2\rfloor\)，\(i=\lceil(n+1)/2\rceil\)
最小值	\(n-1\) 次比较，最优（锦标赛论证）
同时求最小、最大值	\(\le3\lfloor n/2\rfloor\) 次，下界 \(\lceil3n/2\rceil-2\)
第二小元素	\(n+\lceil\lg n\rceil-2\) 次
随机选择递归式	\(E[T(n)]\le\frac2n\sum_{k=\lfloor n/2\rfloor}^{n-1}E[T(k)]+O(n)=O(n)\)
中位数的中位数	每侧至少 \(\frac{3n}{10}-6\) 个；\(T(n)\le T(\lceil n/5\rceil)+T(\frac{7n}{10}+6)+O(n)=O(n)\)
分组大小	5、7 线性；3 不能证明线性
Top-K 有序	\(O(n+i\lg i)\)
\(k\) 分位数	\(O(n\lg k)\)
带权中位数	\(\sum_{x_i<x_k}w_i<\frac12\)，\(\sum_{x_i>x_k}w_i\le\frac12\)；最小化 \(\sum w_i\vert x_i-p\vert \)
MAD 标准化	\(z=(x-\text{med})/(1.4826\cdot\text{MAD})\)

练习

基础

用成对比较法求 \(\langle5,1,8,3,9,2,7\rangle\) 的最小值和最大值，数一数比较次数。提示：\(n=7\) 为奇数，初值取 5，其余三对各 3 次，共 9 次 \(=3\lfloor7/2\rfloor\)。
证明 RANDOMIZED-SELECT 不会对空数组递归。（练习 9.2-1）提示：\(i<k\) 时低区有 \(k-1\ge i\ge1\) 个元素；\(i>k\) 时高区有 \(n-k\ge i-k\ge1\) 个元素。
写出 RANDOMIZED-SELECT 的迭代版本。（练习 9.2-3）提示：见 9.5.1 节代码，用 while 循环更新 \(p,r,i\)。
用 RANDOMIZED-SELECT 在 \(\langle3,2,9,0,7,5,4,8,6,1\rangle\) 中求最小值，描述导致最坏性能的主元序列。（练习 9.2-4）提示：每次都选剩余元素中的最大者：9、8、7、……、1。
某日全市场 5000 只股票，你要做 1%/99% 去极值、按中位数和 MAD 标准化、再分十组。列出需要的全部顺序统计量，并估计用选择算法的总代价。提示：两个去极值分位点、中位数、MAD（对偏差再求一次中位数）、9 个分组断点；每个都是 \(O(n)\) 或合计 \(O(n\lg k)\)。

进阶

证明 SELECT 中至少有 \(3n/10-6\) 个元素大于 \(x\)；再证明 \(n\ge140\) 时至少 \(\lceil n/4\rceil\) 个元素大于 \(x\)。（练习 9.3-2）提示：\(3n/10-6\ge n/4\) 等价于 \(n\ge120\)。
分组大小改为 7 和 3 时，分别写出 SELECT 的递归式，说明哪个是线性的。（练习 9.3-1）提示：见 9.3 节"分组大小"。
设计 \(O(\lg n)\) 算法求两个长度为 \(n\) 的有序数组合并后的中位数。（练习 9.3-8）提示：比较 \(X\) 与 \(Y\) 的中位数，较小者所在数组的前半和较大者所在数组的后半可以同时丢掉。
证明一维邮局选址问题的最优解是带权中位数，并说明二维曼哈顿距离下为什么分别取 \(x\)、\(y\) 的带权中位数即可。（思考题 9-2(d)(e)）提示：目标函数是分段线性凸函数，右导数等于"\(\le p\) 的权重和减 \(>p\) 的权重和"。
用思考题 9-1 的三种方法实现 Top-50 选股，在 \(n=5000\) 和 \(n=500000\) 两种规模下测时间，并解释结果。提示：\(n\) 越大，\(O(n+i\lg i)\) 相对 \(O(n\lg n)\) 的优势越明显。

原书推荐习题：9.1-1、9.2-3、9.3-1、9.3-3、9.3-5、9.3-6、9.3-8、9.3-9；思考题 9-1、9-2、9-4。

原书对照

本章小节	原书章节	PDF 页码
9.0 问题与定义	Chapter 9 Introduction	p.234–235
9.1 最小值与最大值	9.1 Minimum and maximum	p.235–236
9.2 期望线性时间的选择	9.2 Selection in expected linear time	p.236–241
9.3 最坏线性时间的选择	9.3 Selection in worst-case linear time	p.241–245
9.4 思考题精要	Chapter 9 Problems（9-1 至 9-4）与 Notes	p.245–248

第 09 章 中位数与顺序统计量

学习目标

读前导读

9.0 问题与定义

9.1 最小值与最大值

最小值：\(n-1\) 次比较，且不能更少

同时求最小值和最大值：\(3\lfloor n/2\rfloor\) 次

第二小元素（练习 9.1-1）

9.2 期望线性时间的选择：RANDOMIZED-SELECT

算法

期望时间分析

精确常数（思考题 9-4）

9.3 最坏线性时间的选择：SELECT（中位数的中位数）

算法

主元为什么够好

递归式与线性证明

分组大小（练习 9.3-1）

与排序下界的关系

用线性选择构造其他算法

9.4 思考题精要

9.5 量化实战

9.5.1 选择算法的比较次数

9.5.2 截面分位数、去极值、Top-K 与十分组断点

9.5.3 带权中位数：成交量加权中位价

本章小结

练习

原书对照

第 09 章中位数与顺序统计量