计数排序Counting sort

统计有限整数值域内的次数，用累计计数确定输出位置。

核心约束: 计数之和等于输入元素数。
适用问题: 小值域整数排序及基数排序的子过程。
边界与取舍: 值域太大时，计数数组的时间和空间不合适。

时间与空间#

n 为元素数，k 为整数键覆盖的值域大小。

时间复杂度: $O(n+k)$
辅助空间: 稳定输出版 $O(n+k)$

键可映射到连续、可分配的计数数组，计数和前缀和按固定宽度操作。只重建整数序列可用 $O(k)$ 辅助空间，但不等同于保留记录相对顺序的稳定排序。

基础原理参考资料

MIT 6.006 · Linear Sorting计数排序、值域约束和稳定排序。