顺序统计量

第 $k$ 个顺序统计量只关心排序后的一个排名位置，而不需要恢复全部次序；完整排序因此做了大量无关比较。选择算法可围绕枢轴丢弃不含目标的大半元素，只追踪包含目标排名的一侧，把信息需求从完整次序降为一个排名。中位数、分位数和极值都是同一概念的不同 $k$，但重复值时排名约定必须明确。

数组 $[7,2,5,2]$ 的第 2 小元素按重数计为 2。中位数在偶数长度时可定义为两个中间元素之一或其平均值，算法问题必须说明。顺序统计树在每个节点存子树大小，可动态查询排名。若只给偏序而非全序，第 $k$ 小可能不唯一；比较复杂度结论也依赖比较是唯一信息来源。分位数是顺序统计量的比例化版本。

集合 $[7,1,5,2,2]$ 排序后为 $[1,2,2,5,7]$，第 $3$ 小为 $2$。若使用零基下标，代码中的 k=2 对应数学第 $3$ 小；混用会产生常见 off-by-one。

多重集合中相同值可占多个排名，不能把“第 $k$ 小值”理解为第 $k$ 个不同值。数据流中精确中位数需要维护足够信息，近似 quantile sketch 则放松误差；静态一次选择与动态排名查询是不同问题。

统计学中，$X_{(k)}$ 本身是统计量公理库统计量与抽样分布Statistic · Sampling distribution样本的可测数据摘要，以及该摘要在指定统计模型与重复抽样设计下的推前分布。；在 iid 连续模型下，其抽样分布由 $F(X_{(k)})$ 的 Beta 律刻画。样本中位数、极值和分位数的统计误差取决于总体密度与样本机制，不能从选择算法的时间复杂度推出；删失数据还需生存分析公理库生存分析基础Survival analysis · Kaplan–Meier estimator对事件时间、删失、survival 与 hazard 建模并估计生存曲线的基础框架。的 risk-set 结构。

有限集合或多重序列公理库有限集Finite set与某个自然数初始段等势、因而能够在有限步内无遗漏编号的集合。与全序公理库全序Total order · Linear order任意两个元素都可比较的偏序。共同定义排名。静态数组中的单个第 $k$ 小可由选择算法公理库选择算法Selection algorithm在未排序序列中求第 k 小元素而无需完全排序的算法族。在线性期望时间或线性最坏时间内求出；堆适合反复取极值，却不会直接给出任意排名。RMQ公理库静态区间最值查询（RMQ）Range minimum query · RMQ预处理静态数组后，返回区间最小元素的位置并固定并列规则。返回按下标限定区间内的最小位置，也不是全局第 $k$ 小。

数据持续更新时，顺序统计树公理库顺序统计树order-statistic tree · dynamic order statistics在平衡搜索树中维护子树大小，动态支持按秩选择与键的秩查询。在平衡搜索树节点中维护子树大小，Fenwick 树则在离散值域上维护频数前缀和，两者都可支持动态 rank/select。只允许少量遍历和小空间的数据流模型通常转向流式分位数公理库流式分位数摘要streaming quantiles · quantile sketch在单遍小空间中返回秩误差受控的近似分位数，而非数值距离近似。，以可控秩误差换取空间；能否更新、是否近似以及值域能否离散化，决定了应采用哪一种结构。