形式陈述

计数排序适用于每个键是区间 $\{0,\dots ,k\}$ 中整数的记录。先统计每个键出现次数，再取前缀和确定各键在输出中的结束位置，最后按输入逆序稳定放置，时间 $\mathrm{\Theta }(n+k)$、额外空间 $\mathrm{\Theta }(n+k)$（可按需求调整）。它不通过元素间比较排序，因此不受比较排序 $\mathrm{\Omega }(n\log n)$ 下界约束。若只输出键而不保留记录，可直接按计数重写。

直觉

键域小的时候，与其比较元素，不如为每个可能键开一个桶，直接数出它应该占据多少连续位置。

例子与边界

对键 $[2,0,2,1]$，计数为 $[1,1,2]$，前缀和给出各键区间。稳定性要求相同键记录保持原顺序，因此经典实现从右向左扫描输入。若 $k\gg n$，初始化巨大计数数组会比比较排序更差；键为任意实数时也不能直接应用。计数排序以比较排序作为复杂度边界的对照，但本身不属于比较模型。负整数可整体平移或使用稀疏映射，不过复杂度会随表示方式改变。

推论与应用

计数排序是小整数键、直方图和频次聚合的基础，也是 LSD 基数排序保持稳定性的关键子过程。

参考资料

• 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。