选择问题：第 k 小元素

选择问题要求在未排序数组中找第 $k$ 小元素。中位数只是 $k=\lceil n/2\rceil$ 的特殊情况。

1. 基础方法

排序后取第 $k$ 个： $O(n\log n)$ ；
维护大小为 $k$ 的最大堆： $O(n\log k)$ ；
若 $k$ 很小，维护最小堆后弹出 $k-1$ 次： $O(n+k\log n)$ 。

但选择问题其实可以做到线性时间。

2. Randomized-Select

Quickselect 复用快速排序的分区。设分区后主元是区间中的第 $q$ 小：

$k=q$ ：直接返回主元；
$k<q$ ：只递归左侧；
$k>q$ ：只递归右侧，并把目标秩改为 $k-q$ 。

Select(A, l, r, k):
    if l == r: return A[l]
    q = RandomizedPartition(A, l, r)
    rank = q - l + 1
    if k == rank: return A[q]
    if k < rank:  return Select(A, l, q - 1, k)
    return Select(A, q + 1, r, k - rank)

与快速排序不同，它每层只进入一个子问题。

3. 复杂度直觉

最坏情况下每次只去掉一个元素：

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

但随机主元有常数概率落在中间一半，使问题规模至少缩小到 $3n/4$ 。把若干失败尝试看作几何分布，可以证明期望复杂度

\mathbb E[T(n)]=O(n).

这里“期望线性”不是说每次运行都严格线性，而是随机主元下的平均运行时间线性。

4. 最坏线性的 median of medians

若必须保证最坏 $O(n)$ ，可以构造质量有保证的主元：

把元素每 5 个分一组；
每组内部排序并取中位数；
递归找这些组中位数的中位数 $x$ ；
用 $x$ 分区；
只递归包含第 $k$ 小元素的一侧。

为什么每组取 5 个？它能在寻找主元的成本和主元质量之间取得方便的常数平衡。

5. 至少能丢掉多少元素

至少一半的组中位数不小于 $x$ 。在每个这样的完整五元组中，至少有 3 个元素不小于该组中位数，因此不小于 $x$ 的元素至少约为

3\cdot\frac12\cdot\frac n5=\frac{3n}{10}.

对不大于 $x$ 的一侧同理。忽略少量不完整组，递归子问题最大不超过约 $7n/10$ 。

递推式为

T(n) \le T(n/5)+T(7n/10+O(1))+O(n).

两个递归规模系数之和为 $1/5+7/10=9/10<1$ ，所以总复杂度为 $O(n)$ 。

6. 正确性关键

分区后，左边元素不大于主元，右边元素不小于主元。主元的秩因此可以确定：

若目标秩就是主元秩，答案已找到；
若更小，右侧不可能含答案；
若更大，左侧不可能含答案。

每次丢弃的区域都经由秩关系证明不含答案。

7. 重复元素

存在大量重复值时，应使用三路分区：

[<x],\quad[=x],\quad[>x].

设左段长度为 $L$ 、等值段长度为 $E$ ：

$k\le L$ ：递归左段；
$L<k\le L+E$ ：答案就是 $x$ ；
否则递归右段，目标秩改为 $k-L-E$ 。

8. 实际选择

随机 Quickselect 常数小、实现简单，工程中更常用。Median of medians 的价值主要是提供最坏线性保证，也是一个典型证明：不要求主元正好是中位数，只要每次能丢掉常数比例元素，就足够线性。