计数排序（Counting Sort）
计数排序不比较元素大小，而是直接统计“每个值出现了多少次”，再把这些计数还原成有序结果。
定义
计数排序是一种非比较排序算法，使用一个额外的数组来统计每个元素出现的次数，然后根据统计结果将元素放回原数组的正确位置。
核心思路
- 找出待排序数组中的最大值和最小值
- 统计数组中每个值出现的次数，存入计数数组
- 对计数数组进行累加，确定每个值的最终位置
- 根据计数数组将元素放到正确位置
原数组: [4, 2, 2, 8, 3, 3, 1]
1. 统计次数（范围0-8）:
count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
0 1 2 3 4 5 6 7 8
2. 累加计数:
count = [0, 1, 3, 5, 6, 6, 6, 6, 7]
3. 放置元素:
result = [1, 2, 2, 3, 3, 4, 8]
为什么它能做到线性时间
因为它没有走比较排序那条路，而是直接利用值域信息：
- 先统计出现次数。
- 再把次数前缀化成“最终位置”。
- 最后按位置回填结果。
只要值域 k 不大，总体复杂度就是 O(n+k)。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n+k) | n是数组长度，k是数据范围 |
| 空间复杂度 | O(k) | 需要额外的计数数组 |
| 稳定性 | ✅ 稳定 | 从后向前填充保持稳定性 |
适用条件：
- 数据范围不能太大（k不能太大）
- 数据必须是非负整数（或可以映射为非负整数）
Go 代码
Go 实现
package main
import "fmt"
func countingSort(arr []int) []int {
if len(arr) == 0 {
return arr
}
// 找出最大值和最小值
minVal, maxVal := arr[0], arr[0]
for _, num := range arr {
if num < minVal {
minVal = num
}
if num > maxVal {
maxVal = num
}
}
rangeSize := maxVal - minVal + 1
count := make([]int, rangeSize)
// 统计次数
for _, num := range arr {
count[num-minVal]++
}
// 累加计数
for i := 1; i < rangeSize; i++ {
count[i] += count[i-1]
}
// 构建结果数组
result := make([]int, len(arr))
for i := len(arr) - 1; i >= 0; i-- {
index := arr[i] - minVal
result[count[index]-1] = arr[i]
count[index]--
}
return result
}
func main() {
arr := []int{4, 2, 2, 8, 3, 3, 1}
fmt.Println("原始数组:", arr)
sorted := countingSort(arr)
fmt.Println("排序后:", sorted)
}易错点
计数排序最容易错的地方，不是统计次数，而是“如何保持稳定性”。
- 想稳定，最后回填结果时要从右往左扫原数组。
- 处理负数时要先做偏移，例如用
num - minVal作为计数下标。 - 值域太大时，
O(k)空间会直接失控。 - 它适合的是“小范围整数”，不是“任意整数”。
算法变体
经典题目
基础应用
计数排序变体
应用题
- 根据字符出现频率排序 - LeetCode 451
- 前K个高频元素 - LeetCode 347
优缺点
优点
- ✅ 时间复杂度线性：O(n+k)，当k较小时非常快
- ✅ 稳定排序：保持相等元素的相对顺序
- ✅ 不需要比较操作
- ✅ 实现简单
缺点
- ❌ 空间复杂度高：需要O(k)额外空间
- ❌ 只适用于整数：或可映射为整数的数据
- ❌ 范围敏感：数据范围大时不适用
- ❌ 数据稀疏时浪费空间：如 [1, 1000000]
应用场景
- 小范围整数：数据范围小（如年龄、分数）
- 分布密集：数据分布密集，不稀疏
- 稳定性要求：需要稳定排序
- 作为子过程：基数排序的一部分
计数排序 vs 其他排序
| 特性 | 计数排序 | 快速排序 | 归并排序 |
|---|---|---|---|
| 时间复杂度 | O(n+k) | O(n log n) | O(n log n) |
| 空间复杂度 | O(k) | O(log n) | O(n) |
| 稳定性 | 稳定 | 不稳定 | 稳定 |
| 比较排序 | 否 | 是 | 是 |
| 适用数据 | 小范围整数 | 通用 | 通用 |
为什么计数排序能突破 O(n log n) 下界？
基于比较的排序算法下界是O(n log n)，但计数排序：
- 不基于比较：利用数据的特殊性质
- 空间换时间：用额外空间存储统计信息
- 受数据范围限制：只适用于小范围整数