计数排序 Counting Sort
非比较排序 · 用空间换线性时间
什么是计数排序
前面的排序都靠两两比较决定顺序，理论下限是 O(n log n)。计数排序换了个思路：根本不比较——如果知道数据都是小范围内的整数，那就数一数每个值出现了几次，再按值从小到大把它们「倒」回去，天然就有序了。用「统计 + 回填」代替「比较 + 交换」，时间可以做到线性。
它怎么做
为值域里每个可能的值准备一个「桶」（计数格）。第一遍扫描：读到值 v，就给桶 v 计数 +1（一个格子 = 出现一次，「萝卜一个坑」）。第二遍：按桶从小到大，桶里有几个就往结果里写几个。点「下一步」看 [3, 1, 4, 1, 6, 2, 3, 6, 4, 1]：下方计数桶轨按「值」排开（1~6），读一个数对应桶就高亮 +1；留意值 5 从没出现，是个空桶。
01
02
1
3
04
05
06
读 a[0]=3 → 桶「3」+1（现 1 颗）
1function countingSort(a: number[]): number[] {
2 const min = Math.min(...a), max = Math.max(...a);
3 const count = new Array(max - min + 1).fill(0);
4 for (let i = 0; i < a.length; i++) count[a[i] - min]++;
5 let w = 0;
6 for (let v = 0; v < count.length; v++) {
7 while (count[v] > 0) {
8 a[w++] = v + min;
9 count[v]--;
10 }
11 }
12 return a;
13}
n10
min1
max6
k6
阶段计数
i0
v-
w-
1 / 27
复杂度与适用
时间 O(n + k)（n 个元素 + k 个桶）、额外空间 O(k)、稳定。它只适用于取值范围 k 不太大的整数（或可映射为整数的键）——k 远大于 n 时（如排 10 个 32 位整数）就得不偿失。它是「非比较线性排序」三件套的基础，也是基数排序每一位所用的子过程。
值域太大怎么办？基数排序按位分批计数（每位只需 10 个桶），把大值域拆成几轮小计数。
值分布不均怎么办？桶排序按值域段分桶、桶内再排序。
三者同属非比较线性排序，桶的「粒度」不同。
值分布不均怎么办？桶排序按值域段分桶、桶内再排序。
三者同属非比较线性排序，桶的「粒度」不同。
计数是线性排序的起点：往上一层是基数排序（按位计数）、桶排序（按段分桶）——对照三页，能看清「用什么当桶」这条主线。