选择算法

选择算法只需找到第 $k$ 小元素。partition 后枢轴的最终排名已知：目标在左就完全忽略右边，在右就忽略左边，因此每层只递归包含目标排名的一侧，另一侧可整体丢弃。随机 quickselect 期望线性；median-of-medians 用分组中位数保证枢轴不会太偏，从而得到最坏线性。它比完整排序少恢复了大量无关相对次序。

找中位数时，随机 Quickselect 在实践中常比保证线性的算法常数更小。若每次总选最小元素为枢轴，会退化为 $n+(n-1)+\cdots$。重复元素需要三向分区或仔细定义“等于枢轴”的排名区间，否则可能不收缩。线性选择不产生完全有序数组；若随后需要所有排名，排序仍更合适。比较模型下选择有 $\mathrm{\Omega }(n)$ 下界，因为至少要检查所有潜在极端元素。

数组 $[7,1,5,2,4]$ 求第 $3$ 小，取枢轴 $4$ 分区后左侧有 $1,2$，枢轴排名正好为 $3$，可直接返回。若目标在左侧，只需继续处理左分区。

重复元素时最好三路分区为小于、等于、大于枢轴，目标落在等值段即可停止。朴素总取极端枢轴会退化为二次时间；median-of-medians 的线性保证依赖分组和递归规模分析，不是“先找精确中位数”。

数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。、全序公理库全序Total order · Linear order任意两个元素都可比较的偏序。与分治公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。构成静态选择框架。Quickselect 的期望 $O(n)$ 针对随机枢轴和固定输入，median-of-medians 则给比较/RAM 模型下的确定性最坏 $O(n)$；两者都计算一次快照中的顺序统计量公理库顺序统计量Order statistic有限有序样本排序后第 k 个位置的元素。。

一次选择即可确定 top-$k$ 的分界值，再在线性扫描中收集阈值一侧的元素；反复选择适当秩可求精确 quantile。中位数与截尾统计对少量极端值比均值稳健，因此选择算法也是鲁棒统计的基础原语，不过“找出 top-$k$ 集合”不等于把这 $k$ 个元素内部完全排序，重复值处还须规定是否恰好输出 $k$ 个。

若元素会动态插删，顺序统计树公理库顺序统计树order-statistic tree · dynamic order statistics在平衡搜索树中维护子树大小，动态支持按秩选择与键的秩查询。用 $O(n)$ 空间换取最坏 $O(\log n)$ 的更新和 rank/select。若数据只能顺序到达，数据流分位数公理库流式分位数摘要streaming quantiles · quantile sketch在单遍小空间中返回秩误差受控的近似分位数，而非数值距离近似。以受限空间返回带秩误差的近似答案。随机增量构造公理库随机增量构造randomized incremental construction · RIC按随机排列插入对象，以冲突关系和反向分析控制几何结构的期望构建成本。同样随机排列输入，却在逐项加入时维护一个全局结构；它与 quickselect 每轮随机选枢轴的状态演化不同，不能共享一张期望复杂度表。