计数排序

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

图中把相同键的记录标成 $2_a,2_b$，输入为 $[2_a,0,2_b,1]$。频数 $[1,1,2]$ 累加成 $P=[1,2,4]$，所以键 $2$ 占下标 $2,3$。逆序扫描时，$1$ 先放入 $B[1]$，$2_b$ 放入 $B[3]$，$0$ 放入 $B[0]$，最后 $2_a$ 放入 $B[2]$，结果是 $[0,1,2_a,2_b]$。较晚出现的同键记录先占右侧位置，因而原先的相对次序得以保留。

再看包含空桶的例子：

输入 $[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]$。

若仍使用递减的结束位置却从左向右扫描，$2_a$ 会先占最右槽，从而颠倒同键次序。也可以用各桶的起始位置配合正序扫描实现稳定性；扫描方向必须与指针含义匹配。若只排序键而不附带记录，则无须这一步稳定性保证。若 $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$ 得到。