计数排序

键域小时，与其比较元素，不如用值域索引为每个可能键开桶：先统计每个键出现次数，再把计数累加成连续输出区间。它把时间从 $n\log n$ 改为 $n+k$，代价是依赖有限且可寻址的键范围 $k$。稳定版本的前缀计数不仅告诉“有多少”，还精确给出每个键在输出中的结束位置。

输入 $[2,0,2,1]$ 时，频数 $[1,1,2]$ 的前缀和会直接给出三个键各自占据的输出区间。进一步看一个包含空桶的例子：

输入 $[2,5,3,0,2,3,0,3]$、值域 $0\dots 5$ 时，频数为 $[2,0,2,3,0,1]$；累加后可把每个元素从右向左放入对应位置，得到稳定排序 $[0,0,2,2,3,3,3,5]$。

从右向左放置是为了让相同键的记录保持原顺序；若只排序键而不附带记录，则无须这一步稳定性保证。若 $k\gg n$，例如键范围是 $0\dots {10}^9$ 而只有几百个元素，直接分配桶既浪费空间又会比比较排序更差；可压缩坐标或使用稀疏映射，但表示方式会改变复杂度，压缩本身通常还需要排序。负键可整体平移，浮点、任意实数或对象则需先提取有限整数键。计数排序以比较排序作为复杂度边界的对照，但本身不属于比较模型。

数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。存储频数，前缀和公理库前缀和Prefix sum · Cumulative sum预先累计序列前缀，使静态区间和查询可由两个前缀值相减得到。把频数变成位置。计数排序是小整数键、直方图与离散事件聚合的基础，也是 LSD 基数排序公理库基数排序Radix sort按稳定子程序逐位处理固定长度键的非比较排序。保持稳定性的关键子过程。更一般的整数排序公理库超越比较下界的整数排序integer sorting · non-comparison integer sorting通过有限整数宇宙、按位操作和分桶，说明排序复杂度可突破比较模型的 n log n 下界。会在 $k$ 太大而不能直接开桶时改用分位、打包或递归字典结构；这些算法的界依赖字长 $w$ 和允许的字操作，不能由 $\mathrm{\Theta }(n+k)$ 简单删去 $k$ 得到。