第 13 讲：顺序统计量与线性时间选择

一、选择问题

第 k 小元素（k-th order statistic） 输入：n 个互异元素的集合 A，整数 k（1 ≤ k ≤ n） 输出：A 中第 k 小的元素

特例：k = 1 是最小值，k = n 是最大值，k = ⌊(n+1)/2⌋ 是中位数。

朴素做法：排序后取 A[k−1]，Θ(n log n)。

问题：排序做了太多工作——它确定了所有 n 个元素的相对顺序，而我们只关心其中一个位置。能不能只花 Θ(n)？

答案是能，而且有两种做法：一种简单、期望线性；一种复杂、最坏线性。

二、快速选择（Quickselect）

思想：借用快速排序的划分，但只递归一侧。

划分后主元落在下标 p：
   若 p == k−1  ⟹  主元就是答案
   若 p >  k−1  ⟹  答案在左半，递归左边
   若 p <  k−1  ⟹  答案在右半，递归右边（k 要减去左半和主元的个数）

// 返回 a 中第 k 小的元素（k 从 1 开始），会重排 a
func QuickSelect(a []int, k int) int {
    lo, hi := 0, len(a)-1
    for {
        if lo == hi {
            return a[lo]
        }
        p := randomizedPartition(a, lo, hi)
        switch {
        case p == k-1:
            return a[p]
        case p > k-1:
            hi = p - 1
        default:
            lo = p + 1
        }
    }
}

func randomizedPartition(a []int, lo, hi int) int {
    r := lo + rand.IntN(hi-lo+1)
    a[r], a[hi] = a[hi], a[r]
    pivot := a[hi]
    i := lo - 1
    for j := lo; j < hi; j++ {
        if a[j] <= pivot {
            i++
            a[i], a[j] = a[j], a[i]
        }
    }
    a[i+1], a[hi] = a[hi], a[i+1]
    return i + 1
}

⭐ 注意这里写成了循环而非递归——只递归一侧的算法天然是尾递归，可以直接改成循环，空间降到 O(1)。

复杂度

最坏情况：每次划分都极不平衡：

T(n) = T(n−1) + Θ(n)  ⟹  Θ(n²)

最好情况：每次对半：

T(n) = T(n/2) + Θ(n)  ⟹  Θ(n)     （主定理情形 3）

⭐ 注意这个递归式与快排的差别：快排是 2T(n/2) + n（两侧都要递归，得 n log n），选择是 T(n/2) + n（只递归一侧）。少递归一侧，就从 n log n 降到了 n——因为几何级数 n + n/2 + n/4 + … < 2n 收敛。

期望 Θ(n) 的证明

用与第 11 讲相同的思路，但更简单。

随机主元把数组划分成 (i, n−i−1) 两部分，i 均匀分布在 {0,…,n−1}。最坏情况下递归进较大的一侧：

E[T(n)] ≤ (1/n) Σ_{i=0}^{n-1} E[T(max(i, n−i−1))] + O(n)
        ≤ (2/n) Σ_{i=⌊n/2⌋}^{n-1} E[T(i)] + O(n)

用代换法（第 3 讲），猜 E[T(n)] ≤ cn：

E[T(n)] ≤ (2c/n) Σ_{i=⌊n/2⌋}^{n-1} i + an
        ≤ (2c/n) · (3n²/8) + an              （求和上界）
        = (3c/4)n + an
        ≤ cn                                  只要 c ≥ 4a  ✓        ∎

结论：随机化快速选择的期望时间是 Θ(n)。

直觉版：随机主元有 1/2 的概率落在中间一半，此时问题规模至少缩小到 3/4。期望常数次划分后规模就减半，于是总代价被 n + 3n/4 + 9n/16 + … = 4n 这样的几何级数控制住。

三、中位数的中位数（BFPRT）

问题：快速选择的最坏情况仍是 Θ(n²)。能不能确定性地保证线性？

1973 年 Blum、Floyd、Pratt、Rivest、Tarjan 给出的答案是能——关键在于花线性时间选一个「保证足够好」的主元。

算法

SELECT(A, k):
  1. 把 n 个元素分成 ⌈n/5⌉ 组，每组 5 个（最后一组可能不足）
  2. 每组内部排序（5 个元素，O(1)），取出各组的中位数
  3. 递归调用 SELECT，求这 ⌈n/5⌉ 个中位数的中位数 x        ← 这就是主元
  4. 以 x 为主元划分 A
  5. 根据 k 与划分点的关系，递归进一侧（或直接返回 x）

func Select(a []int, k int) int { // 第 k 小，k 从 1 开始
    if len(a) <= 5 {
        slices.Sort(a)
        return a[k-1]
    }
    // ① ② 每 5 个一组求中位数
    medians := make([]int, 0, (len(a)+4)/5)
    for i := 0; i < len(a); i += 5 {
        g := a[i:min(i+5, len(a))]
        slices.Sort(g)
        medians = append(medians, g[len(g)/2])
    }
    // ③ 递归求中位数的中位数
    pivot := Select(medians, (len(medians)+1)/2)

    // ④ 以 pivot 划分（三路，处理相等元素）
    var lo, eq, hi []int
    for _, x := range a {
        switch {
        case x < pivot:
            lo = append(lo, x)
        case x > pivot:
            hi = append(hi, x)
        default:
            eq = append(eq, x)
        }
    }
    // ⑤ 只递归一侧
    switch {
    case k <= len(lo):
        return Select(lo, k)
    case k <= len(lo)+len(eq):
        return pivot
    default:
        return Select(hi, k-len(lo)-len(eq))
    }
}

⭐ 关键引理：主元至少排除 3n/10

断言：至少有 3n/10 个元素小于 x，也至少有 3n/10 个元素大于 x。

证明（图示）：把每组竖着画，组内从小到大自上而下，各组按其中位数从小到大自左而右排列：

                    各组中位数递增 ──────────▶

  小  ┌───┬───┬───┬───┬───┬───┬───┐
   ▲  │ • │ • │ • │ • │ • │ • │ • │
   │  ├───┼───┼───┼───┼───┼───┼───┤
   │  │ • │ • │ • │ • │ • │ • │ • │
      ├───┼───┼───┼───┼───┼───┼───┤
组内  │ m │ m │ m │ x │ M │ M │ M │  ← 各组中位数这一行
      ├───┼───┼───┼───┼───┼───┼───┤
   │  │ • │ • │ • │ ▓ │ ▓ │ ▓ │ ▓ │
   ▼  ├───┼───┼───┼───┼───┼───┼───┤
  大  │ • │ • │ • │ ▓ │ ▓ │ ▓ │ ▓ │
      └───┴───┴───┴───┴───┴───┴───┘
                    ▓ 区域内的元素全部 > x

x 是各组中位数的中位数，所以有一半的组（约 n/10 组）其中位数 ≥ x。在这些组里，中位数及其下方的 3 个元素都 ≥ x：

大于等于 x 的元素数 ≥ 3 · (1/2 · ⌈n/5⌉) ≈ 3n/10

对称地，小于等于 x 的元素也至少有 3n/10。∎

推论：划分后要递归的那一侧，规模最多是

n − 3n/10 = 7n/10

递归式与求解

T(n) ≤ T(n/5)      ← 第 ③ 步：递归求中位数的中位数
     + T(7n/10)    ← 第 ⑤ 步：递归一侧
     + O(n)        ← 分组、组内排序、划分

⚠️ 这不是主定理的形式（两个子问题规模不同），用代换法。猜 T(n) ≤ cn：

T(n) ≤ c(n/5) + c(7n/10) + an
     = c(2n/10 + 7n/10) + an
     = (9c/10)n + an
     ≤ cn                    只要 c ≥ 10a  ✓                        ∎

⭐ 成立的关键：1/5 + 7/10 = 9/10 < 1。 两个子问题的规模之和严格小于原问题，剩下的 1/10 “空间"正好吸收掉线性项 an。这就是几何级数收敛的条件。

四、为什么组大小必须是 5

这是本讲最值得回味的设计细节。

g = 3 恰好不行：T(n) = T(n/3) + T(2n/3) + O(n)，两项之和正好等于 1，得到的是 Θ(n log n)（正是第 3 讲分析过的不平衡递归树）。

g = 5 是使和 < 1 的最小奇数（偶数组求中位数要取两个数的平均或做额外选择，麻烦）。g 更大虽然也线性，但每组排序的常数开销增加。

⭐ “5” 不是魔法数字，而是"让 g/(g+1) 型的递归规模和刚好落到 1 以下"的最小可行值。 这个推理过程本身比结论更值得掌握。

五、两种算法的实际取舍

⚠️ BFPRT 在实践中几乎从不单独使用：常数因子实在太大，随机化快速选择在真实数据上快 5–10 倍。

但它的存在有两重价值：

1. 理论上它证明了"选择比排序容易”——选择是 Θ(n)，排序是 Θ(n log n)。这不是显然的。
2. 工程上它作为兜底：introselect（C++ std::nth_element 的实现）先跑随机化快速选择，若递归层数过深就切换到 BFPRT，从而在保持平均高速的同时获得最坏线性保证。这与第 11 讲的 introsort 是同一个设计模式。

⭐ 模式总结：用一个快但最坏很糟的算法作为主路径，用一个慢但有保证的算法作为兜底，靠一个「事情不对劲」的检测器切换。 这个模式在系统设计中远比在算法课上出现得多。

六、相关问题

Top-K：三种方法的完整对比

⭐ 选择依据不是复杂度而是约束：数据是流吗（必须用堆）？能否修改原数组（快速选择会重排）？需要输出有序吗？

加权中位数

给每个元素 xᵢ 一个权重 wᵢ（Σwᵢ = 1），求满足下式的 x_k：

Σ_{xᵢ < x_k} wᵢ < 1/2    且    Σ_{xᵢ > x_k} wᵢ ≤ 1/2

可以用同样的划分思路在 Θ(n) 内解决：划分后比较两侧权重和，只递归权重不足的那一侧。

应用：一维邮局选址问题（在直线上选一点使加权距离和最小）的最优解就是加权中位数。⭐ 顺带一提，这也解释了为什么最小化绝对误差和用中位数、最小化平方误差和用均值——前者的最优解是中位数，是一个可以在 Θ(n) 内求出的量。

随堂自测

1. 快速选择与快速排序的递归式差在哪一个字符上？为什么这个差别把 n log n 变成了 n？
2. 用代换法证明随机化快速选择的期望时间是 Θ(n)。
3. 为什么快速选择可以写成循环而不是递归？这带来什么好处？
4. 画图说明 BFPRT 中"至少 3n/10 个元素大于主元"的理由。
5. 求解 T(n) = T(n/5) + T(7n/10) + O(n)，指出证明中"9/10 < 1"用在哪一步。
6. 如果 BFPRT 的组大小取 3，递归式变成什么？解是多少？为什么恰好不行？
7. 组大小取 7 也是线性的，为什么标准做法仍取 5？
8. 排 10 亿条日志找最大的 100 条，数据是流式的。用堆还是快速选择？为什么？
9. std::nth_element 是 introselect，说明它的两条路径与切换条件，并类比 introsort。