计数排序(Counting Sort)

计数排序是一种不依赖元素间比较的整数排序算法。它统计待排序序列中每个不同取值出现的次数,再据此直接计算出每个元素在有序结果中的位置,当取值范围有限时能实现线性时间排序。

概述

计数排序适用于键值为有限范围整数或可映射为整数的场景。它突破了比较排序至少需要对数线性时间的下界,因为它根本不做元素比较,而是利用取值本身作为索引直接定位。其代价是需要与键值范围成正比的额外空间。

核心原理

• 统计频次:用一个大小等于键值范围的计数数组,记录每个取值出现的次数。
• 前缀累加:对计数数组求前缀和,得到每个取值在有序序列中的结束位置。
• 倒序放置:从后向前扫描原序列,依据前缀和把元素放入输出数组,以保证稳定性。
• 复杂度:时间和空间均为元素个数加键值范围的量级,当范围不大时接近线性。

应用场景

计数排序适合对取值范围较小的整数、字符或分数进行排序,例如按年龄、成绩、字节值分桶。它最重要的用途是作为基数排序每一位的稳定子排序,支撑起对大整数或字符串的高效排序。在直方图统计等场景也常见其身影。

常见问题

问:计数排序为什么能突破比较排序下界?答:比较排序下界只约束基于两两比较的算法;计数排序不比较元素,而是用取值当索引直接定位,属于另一类模型,故不受该下界限制。

问:计数排序什么时候不适用?答:当键值范围远大于元素个数时,计数数组会占用大量空间且效率下降,此时应改用比较排序或基数排序。