Appearance
计数排序
不比较也能排序
比较排序的理论下界是 O(n log n)，计数排序通过不比较元素大小来突破这个下界。核心思路：对每个元素 x，统计比 x 小的元素有多少个，就能直接确定 x 在排序结果中的位置。
408 考研大纲虽然不单独列出计数排序，但 2013、2015、2018、2021 年真题都考过，而且它是基数排序每趟分配的底层实现，理解计数排序才能真正理解基数排序。
核心思想
计数排序的核心特点：
- 非比较排序：不比较元素大小，而是统计每个值出现的频率
- 空间换时间：需要额外的计数数组和输出数组
- 要求元素取值范围有限：适合整数且取值范围 k 不太大的场景
算法步骤
设待排序数组 A[0..n-1]，元素取值范围为 [0, k]。
- 计数：创建计数数组 C[0..k]，扫描 A，统计每个值出现的次数
- 累加：对 C 做前缀和——C[i] 表示值 ≤ i 的元素总个数
- 输出：从后往前扫描 A，根据 C 确定每个元素的最终位置，放入输出数组 B
c
// 计数排序
// A: 输入数组，B: 输出数组，n: 元素个数，k: 最大值
void CountingSort(int A[], int B[], int n, int k) {
int C[k + 1];
memset(C, 0, sizeof(C));
// 第 1 步：计数
for (int i = 0; i < n; i++)
C[A[i]]++;
// 第 2 步：累加（前缀和）
for (int i = 1; i <= k; i++)
C[i] += C[i - 1];
// 第 3 步：从后往前扫描，保证稳定性
for (int i = n - 1; i >= 0; i--) {
B[C[A[i]] - 1] = A[i]; // C[A[i]]-1 就是 A[i] 的最终下标
C[A[i]]--; // 处理完后计数减 1
}
}排序过程详解
以数组 A = {2, 5, 3, 0, 2, 3, 0, 3} 为例（n=8, k=5）：
第 1 步——计数：
| 值 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| C[i] | 2 | 0 | 2 | 3 | 0 | 1 |
第 2 步——前缀和累加：
| 值 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| C[i] | 2 | 2 | 4 | 7 | 7 | 8 |
含义：C[3]=7 表示值 ≤ 3 的元素共 7 个，因此最后一个值为 3 的元素应放在下标 6 的位置。
第 3 步——从后往前放置：
| 扫描 A[i] | A[i] 的值 | C[A[i]] | 放入 B 的下标 | C[A[i]] 减 1 |
|---|---|---|---|---|
| A[7]=3 | 3 | 7 | B[6]=3 | C[3]=6 |
| A[6]=0 | 0 | 2 | B[1]=0 | C[0]=1 |
| A[5]=3 | 3 | 6 | B[5]=3 | C[3]=5 |
| A[4]=2 | 2 | 4 | B[3]=2 | C[2]=3 |
| A[3]=0 | 0 | 1 | B[0]=0 | C[0]=0 |
| A[2]=3 | 3 | 5 | B[4]=3 | C[3]=4 |
| A[1]=5 | 5 | 8 | B[7]=5 | C[5]=7 |
| A[0]=2 | 2 | 3 | B[2]=2 | C[2]=2 |
结果：B = {0, 0, 2, 2, 3, 3, 3, 5}
复杂度分析
设 n 为元素个数，k 为元素取值范围。
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间 | O(n + k) | 与数据初始顺序无关 |
| 最坏时间 | O(n + k) | 与数据初始顺序无关 |
| 平均时间 | O(n + k) | 当 k = O(n) 时为线性 O(n) |
| 空间复杂度 | O(n + k) | 计数数组 O(k) + 输出数组 O(n) |
| 稳定性 | 稳定 | 从后往前扫描保证相同值的相对顺序不变 |
适用条件：元素取值范围 k 不能太大。当 k 远大于 n 时（比如对 10 个很大的整数排序），计数排序的空间和时间都会退化。
考研高频考点
- ⭐ 计数排序是非比较排序，时间复杂度 O(n+k)（选择题）
- ⭐ 计数排序是稳定的（判断题/选择题）
- ⭐ 为什么第 3 步要从后往前扫描——保证稳定性（简答/选择）
- 计数排序与基数排序的关系：基数排序每趟分配的底层就是计数排序
- 计数排序的空间复杂度 O(n+k)，需要计数数组和输出数组
- 适用场景：元素为整数且取值范围不大
易错：计数排序的稳定性依赖于第 3 步从后往前扫描。如果从前往后扫描，相同值的元素会被反序放置，排序变为不稳定。这也是为什么基数排序要求内层排序必须稳定。
易错：计数排序只适合顺序存储。因为需要根据计数值直接定位下标，链式存储无法随机存取。