顺序统计量

顺序统计量把数值问题转换为排名问题。最小值是第一个位置，最大值是最后一个位置，中位数处在样本的中间。求第 $k$ 个位置，并不需要知道其余所有位置的内部次序；只要证明更小的一侧还不足 $k$ 个，而不大于它的一侧已经达到 $k$ 个即可。

这就是“选择”可以比“完整排序”少做工作的原因。算法只需持续判断目标秩落在哪一部分，保留相关部分并调整秩；已经确定在目标两侧的值，不必再被彼此排好。

重复值占据一段秩区间 ​

样本 $[7,1,5,2,2]$ 排序后为 $[1,2,2,5,7]$。值 $2$ 前面只有一个更小值，把等于 $2$ 的两项加入后共有三项，因此它同时占据第 $2$ 和第 $3$ 个位置。若先去重成 $\{1,2,5,7\}$，再取第三项会得到 $5$，解决的已是另一个问题。

以 $2$ 为枢轴进行三路划分，可得到小于它的一项、等于它的两项、大于它的两项。若目标为 $k=3$，直接落在相等块中；若目标为 $k=4$，只需在大于块中找第 $4-1-2=1$ 小的值。显式保留相等块，避免在大量重复值上错误推进或重复处理。

中位数与分位数的约定 ​

奇数个实数样本的中位数是唯一的中间顺序统计量。偶数个样本的中间有两个位置，常用它们的算术平均作为样本中位数；这个平均需要数值结构，不是任意全序集合都能执行的操作。

对 $[1,3,8,10]$，常用中位数为 $5.5$，它不在样本中。更一般地，使 $\sum _i|x_i-a|$ 最小的全部实数 $a$ 恰为区间 $[3,8]$：在这段内，向右移动造成左侧两项误差增加，恰被右侧两项误差减少抵消。低于或高于该区间时，变化不再平衡。这解释了偶数样本中位数为什么存在不同合理选法。

若以经验分布理路经验测度Empirical measure · Empirical distribution把有限观测的重复频数编码为原子概率测度。的左广义逆定义分位数，则对 $0<p\le 1$，

插值型软件分位数采用其他规则，结果未必相同；$p=0$ 也须单独规定，不能把 $\lceil np\rceil =0$ 塞进从 $1$ 开始的秩。

样本排序后的分布 ​

若 $X_1,\dots ,X_n$ 独立同分布，公共分布函数为 $F$，则

理由是“第 $k$ 小不超过 $t$”等价于“至少 $k$ 个样本不超过 $t$”，后者是服从 $\mathrm{Bin}(n,F(t))$ 的二项计数理路二项分布Binomial distribution固定次数独立同概率 Bernoulli 试验中成功总数的离散分布。事件。这个 CDF 公式允许离散分布和并列值；独立同分布才是把计数写为二项分布的依据。

特别地，若样本均匀分布在 $[0,1]$，最小值满足 $\text{Pr}(X_{(1)}>t)=(1-t{)}^n$，$0\le t\le 1$，从而

总体支持集的最小端点是零，但有限样本最小值通常大于零。样本中的极端位置与总体边界之间仍有随机误差。

把所有排序值连同零、一两端点一起看，均匀次序统计量的间距理路均匀样本的随机间距Uniform spacings · Dirichlet spacings把均匀样本连同两端点之间的间距合起来，得到单纯形上的均匀随机向量，也可由独立指数变量归一化生成。具有单纯形上的联合分布；各段总和固定，彼此不独立。它还可用独立指数变量归一化构造，进一步连接经验曲线的路径极限。

选择算法理路选择算法Selection algorithm在未排序序列中求第 k 小元素而无需完全排序的算法族。可以只递归处理目标所在的一侧。随机枢轴的 Quickselect 对每个固定输入有期望 $O(n)$ 时间，但坏枢轴序列仍可产生 $\mathrm{\Theta }(n^2)$ 时间；median-of-medians 通过控制划分比例取得最坏 $O(n)$ 时间。后者的典型递推形如

两个递归规模之和小于原规模的比例，才支撑线性界。不能仅凭“每次只递归一边”就断言线性。

动态数据中，顺序统计树理路顺序统计树order-statistic tree · dynamic order statistics在平衡搜索树中维护子树大小，动态支持按秩选择与键的秩查询。在搜索树节点保存子树大小，用这些计数判断目标秩落在左侧、当前节点还是右侧。若重复值集中存于一个节点，该节点必须保存出现次数，不能把一个键误计成一条样本。

流式分位数摘要通常承诺秩误差，例如返回值的秩偏离目标至多 $\epsilon n$。这不等于数值误差至多 $\epsilon$：若中间两个观测值相差很大，只偏一个位置也可能跨越巨大的数值间隔。报告分位数精度时，应明确控制的是秩、数值还是概率覆盖。