median-algorithm

Posted on 2026-04-21 Edited on 2026-05-12 In 算法/Algorithm Views: Word count in article: 3.5k Reading time ≈ 6 mins.

中位数以及k位数选取的算法

中位数
- 众数
- 归并有序序列
k位数

引子-众数

给出一个严格的众数的定义：众数是严格大于 n/2 的数字

在这个定义下，众数就是中位数

怎么计算 Maj 呢？一个比较经典的算法就是摩尔投票法

当一个数字满足众数的时候，如果这时从数组里消去一对不同的数字，有两种情况：

众数不在这两个数里，消去之后的数组的众数不变
众数在这两个数里， $n_{maj} > n - n_{maj}$ 推出 $n_{maj}-1 > (n - n_{maj} )-1$ ，众数仍然不变

这是一种经典的***减而治之(decrease and conquer)***的算法

按照这个思想可以在遍历的一遍中让所有元素都”投票“一次，找到最终的众数

ALGORITHM FindMajority(A):
    // 输入: 长度为 n 的数组 A
    // 输出: 数组 A 的主元素，若不存在则返回 null

    // 阶段 1: 寻找候选者
    candidate ← null
    count ← 0

    FOR EACH element IN A DO:
        IF count == 0 THEN:
            candidate ← element
            count ← 1
        ELSE IF element == candidate THEN:
            count ← count + 1
        ELSE:
            count ← count - 1
    END FOR

    // 阶段 2: 验证候选者 (在某些已知必存在主元素的场景下可跳过)
    actual_count ← 0
    FOR EACH element IN A DO:
        IF element == candidate THEN:
            actual_count ← actual_count + 1
    END FOR

    IF actual_count > length(A) / 2 THEN:
        RETURN candidate
    ELSE:
        RETURN null

归并两个有序序列

decrease and conquer

按照这个减而治之的思想，假如有两个有序序列，怎么找到他们合并后的中位数？

可以先找到分别的中位数 $m_A, m_B$ ，

如果两者相等，就已经找到了中位数
两者不等，则根据两者的大小关系，可以确定 $m$ 是在 A 的右半 + B的左半 / A 的左半 + B的右半，这样再减而治之的递归

这样得到的时间复杂度

T(n) = T(n/2)

即为 $O(logN)$

leetcode

其实这道题在leetcode里做过一次，当时是要求用 $O(min(m,n))$ 的时间，也就是只遍历一遍长度更小的数组，得到中位数

这里的精髓在于确定了中位数在A中的位置i，就能确定B中中位数的位置j，因为满足 $i+j = m + n$

所以只需要检验每一次 $j$ 的位置是不是中位数的位置，也就是 $A[i-1]<=B[j],B[j-1]<=A[i]$ ，最终的结果会在四个边界值中产生

二分切割

有了刚刚的思路之后，其实可以将上面两个融合一下，不再使用对半分来更新查找的区域，而是使用二分查找，在更短的序列中找到一个位置 $i$ ，使它对应的 $j$ 能够满足条件即可

这样的复杂度只有 $O(log(min(m,n)))$ ，而且这样感觉代码要考虑的边界比第一种要少，因为第一种选取左/右区间的时候会造成长度不等的情况，需要考虑怎么处理

1. 快速选择 (Quickselect)

核心思想： 减治法 (Decrease and Conquer)。

快速选择的目标是从无序数组中找到第 $k$ 小的元素。它利用了快速排序中的 Partition (分区) 操作，但不同于快排的双侧递归，它仅进入包含目标元素的一侧，所以不会“还原”成一个二叉树，而是退化到一个线性的复杂度

执行流程

Pivot Selection：随机或选取首尾元素作为基准值。
Partitioning：将数组划分为三个逻辑区域：
- Q (Smaller)：小于基准值。
- L (Equal)：等于基准值。
- G (Greater)：大于基准值。
Branching：根据 $k$ 与分区边界的关系，决定是直接返回基准值，还是递归进入 Q 区或 G 区。

时间复杂度计算

平均情况：假设每次分区都能平分数组。
$T(n) = T(n/2) + O(n)$
利用等比数列展开： $T(n) = n + n/2 + n/4 + ... + 1 \approx 2n$ 。因此平均复杂度为 $O(n)$ 。
最坏情况：基准值始终选到极值，导致每次只排除一个元素。
$T(n) = T(n-1) + O(n)$
这是一个等差数列求和： $n + (n-1) + ... + 1$ 。因此最坏复杂度为 $O(n^2)$ 。

2. BFPRT 算法 (中位数的中位数)

核心思想： 确定性基准值筛选。

BFPRT 解决了普通快速选择在最坏情况下退化的问题，通过一系列预处理，从理论上保证了分区平衡性

本质上就是避免在quickselect中选取了一个极值的pivot，为此先进行了一次类 median 的

执行流程

分组：将 $n$ 个元素每 5 个分为一组。
局部中位数：对每组进行排序，取出该组的中位数。
递归找基准：对这 $n/5$ 个中位数递归调用 BFPRT，找到其中的中位数，记为 $x$ 。
分区：使用 $x$ 作为基准值进行三向切分 (Three-way Partition)。

时间复杂度计算

BFPRT 的复杂度由三部分组成：

$O(n)$ ：分组及找局部中位数的线性开销。
$T(n/5)$ ：递归寻找中位数的中位数的代价。
$T(7n/10)$ ：在最坏情况下，剩余待处理子问题的规模。

为什么是 $7n/10$ ？

在所有中位数中，有 $1/2$ 的中位数比 $x$ 小。而这些组中又有 3 个元素（包括中位数本身）小于或等于其组内中位数。

因此，至少有 $\frac{n}{5} \times \frac{1}{2} \times 3 = \frac{3}{10}n$ 的元素保证不大于 $x$ 。同理，至少有 $3/10n$ 的元素不小于 $x$ 。最坏情况只需处理剩下的 $7/10n$ 。

最终递推式：

T(n) \leq T(n/5) + T(7n/10) + O(n)

由于 $1/5 + 7/10 = 9/10 < 1$ ，该递归树是收敛的，最终证明 $T(n) = \mathbf{O(n)}$ 。

3. 对比与权衡

Figure_1

其实实际上 quickselect 的使用比 BRPRT 更常见，因为虽然后者保证最坏的情况仍然是线性的，但是在随机情况下引入的额外计算的overhead实际上会带来负效益

特性	快速选择 (Quickselect)	BFPRT 算法
理论最坏复杂度	$O(n^2)$	$O(n)$
实际运行常数	极小 (约为 $2n$ )	较大 (约为 $10n$ - $20n$ )
访存特征	Cache Friendly (顺序访存)	Cache Miss 较高 (逻辑跳转多)
实现难度	简单	复杂
典型应用	`std::nth_element` (结合 Introselect)	算法理论研究、安全敏感型任务

为什么 Quickselect 更常用？

访存局部性 (Memory Locality)：快速选择的线性扫描极大地利用了 CPU L1/L2 缓存。BFPRT 的分组和二次提取操作破坏了空间局部性。
分支预测 (Branch Prediction)：Quickselect 逻辑单一，现代 CPU 分支预测准确率高；BFPRT 的多重递归和分组逻辑易导致流水线停顿。
概率论保证：随机化基准选择在实践中触发 $O(n^2)$ 的概率极低，远小于硬件故障的概率