形式陈述

有限全序集合中，第 $k$ 个顺序统计量是排序后位于第 $k$ 位的元素，通常 $1\le k\le n$；最小值与最大值分别是第 1 和第 $n$ 个。若元素允许相等，应采用多重集合位置或明确稳定打破平局。选择问题要求不必完全排序就找出第 $k$ 个元素；比较模型中最小值需 $n-1$ 次比较，中位数可在线性时间求得。

直觉

顺序统计只关心一个排名位置，而不是全部次序。完整排序做了大量无关比较，选择算法通过分区只追踪包含目标排名的一侧。

例子与边界

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

推论与应用

顺序统计用于中位数、分位数、鲁棒估计、负载阈值和动态排名，也连接选择算法、堆和增广搜索树。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998，Chs. 5–6。