计数排序 (Counting Sort)
一种非比较排序算法，通过统计元素出现次数实现 O(n + k) 时间复杂度排序，适合元素值范围不大的整数排序场景。
定义
计数排序（Counting Sort）是一种非比较排序算法，其核心思想是：统计每种元素出现的次数，进而推算出每个元素在排序后数组中的索引位置，最终完成排序。
与比较排序（如快速排序、归并排序）不同，计数排序不通过比较元素大小来决定顺序，而是利用元素值作为索引直接定位。
核心特性
| 特性 | 说明 |
|---|---|
| 排序类型 | 非比较排序 |
| 时间复杂度 | O(n + k)，k = max - min + 1（元素值范围） |
| 空间复杂度 | O(n + k) |
| 稳定性 | 原生实现不稳定，可改进为稳定排序 |
| 适用数据类型 | 整数（或可以映射到整数的类型） |
| 适用场景 | 元素值范围不大的排序场景 |
基本原理
算法步骤
- 确定范围：找出待排序数组的最小值 min 和最大值 max
- 创建计数数组：创建大小为 (max - min + 1) 的 count 数组
- 统计次数：遍历原数组，count[num - min]++ 统计每个元素出现次数
- 累加计数（稳定版）：将 count 数组转换为前缀和数组，表示每个元素排序后的最终位置
- 构建结果：从后向前遍历原数组，根据 count 数组将元素放入正确位置
- 写回原数组（可选）：将结果复制回原数组
简单示例
输入数组：[1, 6, 3, 6, 1, 6]
统计结果：
- 元素
1出现 2 次 - 元素
3出现 1 次 - 元素
6出现 3 次
排序结果：[1, 1, 3, 6, 6, 6]
时间复杂度/性能
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 计数排序 | O(n + k) | n 是数组长度，k 是元素值范围 |
| 最佳情况 | O(n + k) | 与数据分布无关 |
| 最坏情况 | O(n + k) | 与数据分布无关 |
| 空间占用 | O(n + k) | count 数组 + 结果数组 |
注意：当 k 接近 n 时，计数排序接近 O(n)；当 k >> n 时，空间效率会很低。
与类似概念对比
| 维度 | 计数排序 | 比较排序（快排/归并等） | 桶排序 |
|---|---|---|---|
| 排序类型 | 非比较排序 | 比较排序 | 混合（可分桶后比较） |
| 时间复杂度 | O(n + k) | O(n log n) | 取决于桶数量和合并方式 |
| 稳定性 | 原生不稳定，可改进 | 取决于实现 | 取决于桶内排序算法 |
| 适用数据类型 | 整数（范围不大） | 任意可比较类型 | 任意可映射到桶的类型 |
| 额外空间 | O(k) | O(1) ~ O(n) | O(k) 用于桶 |
| 与桶排序关系 | 是桶排序的特例（k=n） | - | 通用框架 |
常见实现
简单版本（固定范围）
适用于元素值范围已知且较小的场景（如 LeetCode 75 颜色分类）：
// 只有 0, 1, 2 三种元素
int[] count = new int[3];
for (int element : nums) {
count[element]++;
}
// 按顺序填充
int index = 0;
for (int element = 0; element < 3; element++) {
for (int i = 0; i < count[element]; i++) {
nums[index++] = element;
}
}
通用版本关键点
- 负数处理：通过偏移量
num - min将最小值映射到 0 - 稳定性保证：使用前缀和 + 从后向前遍历
- 大值范围问题：当 max - min 很大时，count 数组会太大
注意事项
- 只能处理整数类型（或可以映射到整数的类型）
- 元素值范围过大时空间效率低（如排序 [1, 1000000] 需要 count 数组大小为 1000000）
- 原生实现是不稳定排序，如需稳定需要额外步骤
- 适合作为**基数排序（Radix Sort）**的子过程
应用场景
- 元素值范围有限的整数排序（如年龄、分数、状态码等）
- 作为基数排序的子过程
- LeetCode 75 颜色分类等特定场景
- 统计频率分布后按顺序输出