选择算法

完整排序确定所有秩之间的相对次序，选择只确定一个目标位置。划分已经说明目标在何处后，另一侧的内部次序就与答案无关。不同枢轴策略控制的是每次还能丢掉多少：随机选择给平均进度，组中位数则强制每次保留的最大比例。

“只递归一边”本身还不保证线性。如果每次只丢一个元素，扫描账本依旧是 $n+(n-1)+\cdots$。真正的分析要把枢轴质量与整条递归规模序列联系起来。

数组 $[7,1,5,2,4]$ 求第 $3$ 小。取枢轴 $4$ 后，小于块是 $[1,2]$，相等块只有 $4$，目标正好落在其中。无需排好 $[5,7]$ 即可返回。图中对同一输入改求第 $4$ 小，因此保留大于块 $[7,5]$，并把目标改成其中第 $1$ 小。

再取 $[7,1,5,2,2]$，以 $2$ 划分得到长度 $\ell =1,e=2,g=2$。第 $2$、第 $3$ 小都直接返回 $2$；第 $4$ 小则转成在 $[7,5]$ 中求第 $1$ 小。全相等输入一轮扫描即可完成，而不是继续处理一串大小仅减一的子数组。

若允许输入为空或秩越界，接口应先报告非法请求。要返回具体记录而非键值，还需约定同键身份的选择规则。

采用原地三路划分时，Quickselect 的目标侧递归可以改成循环，只保留常数个边界和秩变量，使用 $O(1)$ 额外空间。确定性分组版本可把组中位数搬到数组前缀，避免另开线性数组；其枢轴递归和目标侧递归的栈深为 $O(\log (n+1))$。使用新数组收集各块的实现则需要另报分配与空间成本。

在纯比较模型中，选择也有线性下界。正确执行的比较图必须把选中元素与其他元素都约束起来；若存在与它完全断开的比较连通分量，可把该分量的全部值移到它的上方或下方而保留所有既有比较，改变选中元素的秩。因此比较图必须连通，至少有 $n-1$ 条比较边。该论证针对互异键的最坏输入，足以与线性选择上界匹配。

一次选择可确定 top-$k$ 的阈值，再扫描收集阈值一侧，并从相等块补足所需数量。这给出恰好 $k$ 个元素的集合，却没有把它们内部排好。分位数和截尾统计也可以复用这个秩接口；多次求秩时，还应重新比较反复选择、复用划分与一次完整排序的总成本。

动态插删由顺序统计树理路顺序统计树order-statistic tree · dynamic order statistics在平衡搜索树中维护子树大小，动态支持按秩选择与键的秩查询。维护大小摘要，流式受限空间则可采用分位数摘要理路流式分位数摘要streaming quantiles · quantile sketch在单遍小空间中返回秩误差受控的近似分位数，而非数值距离近似。并报告秩误差。这些是不同更新和误差接口。随机增量构造理路随机增量构造randomized incremental construction · RIC按随机排列插入对象，以冲突关系和反向分析控制几何结构的期望构建成本。逐项加入并维护全局结构，Quickselect 则不断缩小一个秩子问题，两者需要各自的期望分析。