计数排序（Counting Sort）
大家好，今天我们来聊一个非常有意思的排序算法——计数排序。
为什么说它有意思呢？因为之前我们聊过的排序算法，无论是冒泡、快排还是归并，它们都有一个共同的前提：必须比较两个元素的大小。而计算机科学里有一个铁律：基于比较的排序算法，时间复杂度下限是 O(n log n)。
但是计数排序不一样，它直接跳过了"比较"这一步，用一种巧妙的方式把时间复杂度干到了 O(n + k)，其中 k 是数据的范围。当 k 不大的时候，它就是 O(n)——线性时间！
听起来像开挂了？别急，咱们慢慢拆解。
生活场景类比
想象你是一个幼儿园老师，要给 30 个小朋友按年龄排序。年龄范围很小，就是 3 岁到 6 岁。
你不会让小朋友们两两比身高（那太慢了），而是直接准备 4 个箱子：
箱子[3岁] 箱子[4岁] 箱子[5岁] 箱子[6岁]然后你走一圈，看每个小朋友几岁，就丢进对应箱子里。走完一圈之后，你按顺序从箱子里把小朋友领出来——3 岁的先出来，4 岁的跟上，5 岁的，6 岁的。排序完成！
这个过程没有任何"比较"动作，只有"数数"和"放进去"。这就是计数排序的核心思想。
原理拆解
核心思路
计数排序的核心就三步：
- 计数：统计每个值出现了多少次
- 累加（可选）：把计数数组变成前缀和，用来确定每个元素的最终位置
- 反向填充：从后往前遍历原数组，把每个元素放到正确位置
我们用一个具体例子来走一遍：
原始数组: [4, 2, 2, 8, 3, 3, 1]
Step 1: 计数
值的范围: 1 ~ 8
计数数组: [0, 1, 2, 2, 1, 0, 0, 0, 1]
0 1 2 3 4 5 6 7 8 ← 索引代表值
↑ ↑ ↑ ↑ ↑ ↑
没有 1个 2个 2个 1个 没有 没有 没有 1个到这里，其实你已经可以排序了——直接按计数输出就行。但为了实现稳定排序（相同元素保持原始相对顺序），我们还需要第二步：
Step 2: 累加（前缀和）
计数数组: [0, 1, 3, 5, 6, 6, 6, 6, 7]
0 1 2 3 4 5 6 7 8
含义: 值 ≤ 该索引的元素共有几个Step 3: 反向遍历原数组，放入结果
原数组: [4, 2, 2, 8, 3, 3, 1]
↑
处理 4: 累加数组[4] = 6，所以 4 放到结果数组索引 5（6-1），然后累加数组[4] 减 1
结果: [_, _, _, _, _, 4, _, _]
累加: [0, 1, 3, 5, 5, 6, 6, 6, 7]
处理 2: 累加数组[2] = 3，放索引 2
结果: [_, _, 2, _, _, 4, _, _]
累加: [0, 1, 2, 5, 5, 6, 6, 6, 7]
处理 2: 累加数组[2] = 2，放索引 1
结果: [_, 2, 2, _, _, 4, _, _]
累加: [0, 1, 1, 5, 5, 6, 6, 6, 7]
处理 8: 累加数组[8] = 7，放索引 6
结果: [_, 2, 2, _, _, 4, _, 8]
累加: [0, 1, 1, 5, 5, 6, 6, 6, 6]
处理 3: 累加数组[3] = 5，放索引 4
结果: [_, 2, 2, _, 3, 4, _, 8]
累加: [0, 1, 1, 4, 5, 6, 6, 6, 6]
处理 3: 累加数组[3] = 4，放索引 3
结果: [_, 2, 2, 3, 3, 4, _, 8]
累加: [0, 1, 1, 3, 5, 6, 6, 6, 6]
处理 1: 累加数组[1] = 1，放索引 0
结果: [1, 2, 2, 3, 3, 4, _, 8]
累加: [0, 0, 1, 3, 5, 6, 6, 6, 6]
最终结果: [1, 2, 2, 3, 3, 4, 8] ✅为什么要反向遍历？因为累加数组代表的是"最后一个该值元素应该放的位置"。反向遍历保证了稳定性——相同值的元素，后出现的先放，这样先出现的就会排在前面。
代码实现
TypeScript
/**
* 计数排序 —— TypeScript 实现
* 适用场景：数据范围有限的非负整数排序
* 核心思想：用一个计数数组统计每个值出现的次数，然后反向填充结果
*/
function countingSort(arr: number[]): number[] {
if (arr.length <= 1) return [...arr];
// 找到最大值，确定计数数组的大小
const max = Math.max(...arr);
// Step 1: 计数 —— 统计每个值出现几次
const count = new Array(max + 1).fill(0);
for (const num of arr) {
count[num]++;
}
// Step 2: 累加 —— 把计数变成前缀和，表示"≤ 该值的元素有几个"
for (let i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// Step 3: 反向遍历原数组，把每个元素放到正确位置（保证稳定性）
const result = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--) {
const val = arr[i];
count[val]--; // 累加值减 1，就是这个元素应该放的索引
result[count[val]] = val;
}
return result;
}
// 使用示例
const data = [4, 2, 2, 8, 3, 3, 1];
console.log(countingSort(data)); // [1, 2, 2, 3, 3, 4, 8]
// 有负数？不行！计数排序只支持非负整数
// 处理方法见下方"处理负数"小节处理负数版本
实际开发中数据经常有负数，我们可以做一个小 trick——用最小值做偏移：
/**
* 计数排序（支持负数版本）
* 思路：用 min 做偏移量，把所有值映射到 [0, max - min] 的范围
*/
function countingSortWithNegatives(arr: number[]): number[] {
if (arr.length <= 1) return [...arr];
const min = Math.min(...arr);
const max = Math.max(...arr);
const range = max - min + 1; // 计数数组的大小
// 计数（用偏移量处理负数）
const count = new Array(range).fill(0);
for (const num of arr) {
count[num - min]++;
}
// 累加
for (let i = 1; i < range; i++) {
count[i] += count[i - 1];
}
// 反向填充
const result = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--) {
const idx = arr[i] - min;
count[idx]--;
result[count[idx]] = arr[i];
}
return result;
}
// 使用示例
console.log(countingSortWithNegatives([-3, 4, 1, -1, 0, 2, -2]));
// [-3, -2, -1, 0, 1, 2, 4]Python
from typing import List
def counting_sort(arr: List[int]) -> List[int]:
"""计数排序 —— Python 实现
适用场景：非负整数，数据范围不大
时间复杂度 O(n + k)，空间复杂度 O(k)
"""
if len(arr) <= 1:
return arr[:]
max_val = max(arr)
# 计数
count = [0] * (max_val + 1)
for num in arr:
count[num] += 1
# 累加
for i in range(1, max_val + 1):
count[i] += count[i - 1]
# 反向填充（保证稳定性）
result = [0] * len(arr)
for i in range(len(arr) - 1, -1, -1):
val = arr[i]
count[val] -= 1
result[count[val]] = val
return result
# 使用示例
print(counting_sort([4, 2, 2, 8, 3, 3, 1])) # [1, 2, 2, 3, 3, 4, 8]简化版（不追求稳定，纯计数输出）
如果你不需要稳定性，代码可以更简洁：
/**
* 简化版计数排序 —— 直接按计数输出
* 适用：纯粹要排序，不关心相同元素的相对顺序
*/
function countingSortSimple(arr: number[]): number[] {
if (arr.length <= 1) return [...arr];
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0);
// 计数
for (const num of arr) count[num]++;
// 直接输出
const result: number[] = [];
for (let i = 0; i <= max; i++) {
for (let j = 0; j < count[i]; j++) {
result.push(i);
}
}
return result;
}
console.log(countingSortSimple([4, 2, 2, 8, 3, 3, 1]));
// [1, 2, 2, 3, 3, 4, 8]复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 排序 | O(n + k) | O(n + k) |
其中 n 是元素个数，k 是数据的范围（max - min + 1）。
- 时间 O(n + k)：遍历一次数组 O(n)，遍历一次计数数组 O(k)，总共 O(n + k)
- 空间 O(n + k)：需要一个大小为 k 的计数数组 + 一个大小为 n 的结果数组
什么时候比快排快？
当 k = O(n) 时，计数排序是 O(n)，吊打快排的 O(n log n)
举例：
n = 100万, k = 1000
计数排序 ≈ 100万 + 1000 ≈ 100万次操作
快排 ≈ 100万 × 20 ≈ 2000万次操作但是！如果 k 特别大（比如 k = 10 亿），那计数排序就需要开一个 10 亿大小的数组，内存直接炸了。这时候还不如老实快排。
一个常见面试题：为什么计数排序能突破 O(n log n)？
这其实是一个很好的面试加分题，理解了你就真正理解了排序的本质。
基于比较的排序（快排、归并、堆排）每一步只能获取 1 bit 的信息（A > B 还是 A < B）。n 个元素有 n! 种排列，要确定是哪一种，至少需要 log₂(n!) 次比较，也就是 O(n log n)。
计数排序绕过了"比较"，它直接利用了"数据值本身就有意义"这个条件。它不是在问"谁大谁小"，而是在说"值为 3 的有几个"——这一步就跳出了信息论的下限。
简单来说：
比较排序：像玩"猜数字"游戏，每次只能问"大了还是小了？"
计数排序：像直接看到答案，数一数有几个 1、几个 2、几个 3...计数排序与基数排序的关系
计数排序单独使用时有个明显限制：数据范围 k 不能太大。但如果配合**基数排序（Radix Sort）**使用，就能处理大范围的整数。
基数排序的思路是：按位排序——先排个位，再排十位，再排百位... 而每一位（0~9）的范围很小，刚好适合用计数排序！
原始数据: [170, 45, 75, 90, 802, 24, 2, 66]
按个位排序（用计数排序）: [170, 90, 802, 2, 24, 45, 75, 66]
按十位排序（用计数排序）: [802, 2, 24, 45, 66, 170, 75, 90]
按百位排序（用计数排序）: [2, 24, 45, 66, 75, 90, 170, 802]
排序完成！总复杂度 O(d × (n + k))，d 是最大位数这就是为什么说计数排序是基数排序的"内核"——没有计数排序，基数排序就跑不起来。
业务场景
1. 年龄排序
人口数据按年龄排序。年龄范围 0~150，k 很小，计数排序完美适配。100 万条数据，瞬间排好。
2. 成绩排名
考试成绩 0~100 分，范围固定。用计数排序可以在 O(n + 101) 内完成排序，比任何比较排序都快。
3. 字符频率统计
统计一篇文章中每个字符出现的频率（ASCII 范围 0~127），本质上就是计数排序的"计数"步骤。很多面试题（如 LeetCode 的"根据字符出现频率排序"）底层就是计数排序。
4. 作为基数排序的子程序
如上所述，基数排序的每一趟都是对某一位做计数排序。这是计数排序最重要的"隐藏"应用。
适用条件与局限性
✅ 适用场景：
- 数据是非负整数（或能映射为非负整数）
- 数据范围 k 相对较小，k = O(n) 最理想
- 需要稳定排序
❌ 不适用场景：
- 数据范围太大（比如排序 100 个 32 位整数，k = 2³² ≈ 42 亿）
- 数据是浮点数或字符串（无法直接用值做索引）
- 内存受限（需要 O(n + k) 的额外空间）
小结
计数排序是一种非比较排序，核心思想是"数数"而不是"比较"：
计数 → 累加 → 反向填充| 特性 | 说明 |
|---|---|
| 时间复杂度 | O(n + k) |
| 空间复杂度 | O(n + k) |
| 稳定性 | ✅ 稳定（前提是反向填充） |
| 适用类型 | 非负整数、范围有限的数据 |
虽然单独使用计数排序的场景不算多（数据范围必须小），但它作为基数排序的核心组件，重要性不言而喻。面试中如果能讲清楚"为什么计数排序能突破 O(n log n)"，绝对是加分项 💪