Counting Sort

计数排序适用于键值是整数且值域有限的场景。它统计每个值出现次数，再按值域顺序写回；不依赖元素间比较。

设输入规模为 $n$，值域宽度为 $k=max-min+1$，时间复杂度为 $O(n+k)$，额外空间为 $O(k)$。

Stable Version

1. 统计每个键出现次数；
2. 对计数数组做前缀和，得到每个键在输出数组中的结束位置；
3. 从右向左扫描输入，把元素放入对应位置并减少计数。

从右向左写出可以保持相同键的原始相对顺序，因此能作为基数排序的稳定子过程。

Boundaries

• 负数可通过 value - min 映射到数组下标；
• 当 $k$ 远大于 $n$ 时，空间和初始化成本可能超过比较排序；
• 对复杂对象排序时，计数的是 key，输出时移动整个记录或引用；
• 只需要频率统计而不需要排序结果时，不必执行前缀和与回写。

计数排序突破 $O(n\log n)$ 比较下界，是因为它利用了整数值域这一额外假设。