8.4　非比较排序：计数排序与基数排序

学习目标：学完本节，你能

• 说清计数排序为什么能突破 $O(n \log n)$ 下界；
• 手写计数排序，并说清"稳定版"为什么要从后往前遍历；
• 用基数排序处理大值域的数据，并说清它为什么依赖稳定性；
• 说出它们的前提条件 —— 什么情况下不能用。

先修：7.4（下界）、7.2（稳定性）。 固定术语：计数排序、基数排序、值域、桶。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、直觉：不比较，直接数

7.4 节证明了：任何比较排序至少需要 $\log_2(n!)$ 次比较，也就是 $\Omega(n \log n)$。

但这个下界有一个前提 —— 你的算法必须"通过比较来获取信息"。

如果不比较呢？

给一群学生按成绩排序。成绩是 0 到 100 的整数。

你不需要比较任何两个学生的成绩 —— 你只需要数一下： "60 分的有 2 个、78 分的有 3 个、85 分的有 4 个……" 然后按分数从低到高，把对应数量的学生依次放回去。

这就是计数排序。它一次比较都没做。

为什么能突破下界？ 因为它没有"猜" —— 它直接"看"了每个元素的值，然后算出它该在哪。信息不是通过比较"问"出来的，而是直接读出来的。

这就是 7.4 节说的"跳出比较模型"：

不是找到了更聪明的比较方式，而是根本不用比较。

二、计数排序

/// <summary>朴素计数排序（不保证稳定）。</summary>
static void CountingSort(int[] a, int maxValue, ref long ops)
{
    var count = new int[maxValue + 1];

    foreach (int x in a) { count[x]++; ops++; }          // 统计每个值出现几次

    int idx = 0;
    for (int v = 0; v <= maxValue; v++)                  // 按值的顺序从小到大输出
        for (int k = 0; k < count[v]; k++)
        {
            a[idx++] = v;
            ops++;
        }
}

就这么简单。三步：

1. 开一个数组 count，大小是"值域的最大值 + 1"
2. 遍历原数组，count[a[i]]++ —— 统计每个值出现几次
3. 按值的顺序（0, 1, 2, ...）依次输出对应次数

实测：

  原始成绩: [85, 92, 78, 85, 95, 78, 92, 85, 60, 100, 78, 85]
  排序后  : [60, 78, 78, 78, 85, 85, 85, 85, 92, 92, 95, 100]
  操作次数: 24（统计 12 次 + 输出 12 次）

复杂度：$O(n + k)$，其中 $k$ 是值域大小（$maxValue + 1$）。

• $n$ 部分：遍历原数组统计
• $k$ 部分：遍历整个值域输出

三、前提条件：值域必须小

$O(n + k)$ 里的 $k$ 是关键。如果 $k$ 远大于 $n$，这个算法就废了。

具体看：

实测最后一行：

  场景 3：如果非要用计数排序排 0~999,999,999 的数呢？
    需要开一个 10 亿长度的 int 数组 = 3 GB 内存
    而实际只有 1,000,000 个元素 —— 内存利用率 0.1%
    -> 完全不可行。这就是计数排序的前提条件为什么重要。

记住这条判断标准：

只有 $k = O(n)$ 时，计数排序才真正优于比较排序。

如果 $k \gg n$（比如值域是 $2^{32}$ 而只有几万个元素），计数排序不仅不快，而且会直接把内存撑爆。

值域大怎么办？下一节的基数排序解决了这个问题。

四、稳定版计数排序（基数排序的基础）

朴素版的计数排序有个问题：它不能保证稳定。

为什么？看第 3 步：a[idx++] = v —— 它只是按值输出，完全不管原来谁在前谁在后。

要让它稳定，需要换一种放置方式：

/// <summary>稳定版计数排序 —— 基数排序的基础。</summary>
static int[] CountingSortStable(int[] a, int maxValue, ref long ops)
{
    var count = new int[maxValue + 1];

    foreach (int x in a) { count[x]++; ops++; }

    // 前缀和：count[i] 变成「小于等于 i 的元素有几个」
    for (int i = 1; i <= maxValue; i++) { count[i] += count[i - 1]; ops++; }

    var output = new int[a.Length];
    // 关键：从后往前遍历，把元素放到「它该在的最后一个位置」
    // 这样相等的元素会保持原来的相对顺序 —— 这就是稳定性的来源
    for (int i = a.Length - 1; i >= 0; i--)
    {
        output[--count[a[i]]] = a[i];
        ops++;
    }
    return output;
}

关键的两步：

第 1 步：把 count 转成前缀和。

统计次数:  count[1]=2, count[2]=1, count[3]=3
前缀和后:  count[1]=2, count[2]=3, count[3]=6

前缀和的含义变成了："值 $\le i$ 的元素一共有几个"。

所以值等于 3 的元素，应该放在下标 2、3、4 这三个位置（因为 $count[2]=3$，说明前 3 个位置留给 1 和 2）。

第 2 步：从后往前遍历，output[--count[a[i]]] = a[i]。

这一步是稳定性的关键：

• 从后往前遍历原数组
• 每放置一个元素，就把 count[值] 减一 —— 这样下一个同值的元素会放到前一个位置
• 因为是从后往前处理的，同值的元素里"原本靠后的"会先被处理，放进更靠后的位置

结果：同值元素的相对顺序被保持 ✓

实测验证（用 (值, 原始序号) 标记）：

  用 (值, 原始序号) 验证：
    原始: 3#0 1#1 3#2 2#3 1#4 3#5
    排序后: 1#1 1#4 2#3 3#0 3#2 3#5
    稳定性: 稳定 ✓（同值的 #序号 保持递增）

看 3#0 3#2 3#5 —— 三个值为 3 的元素，原始序号 0 < 2 < 5，排序后依然保持这个顺序 ✓

五、基数排序：按位拆分，逐位排序

值域太大，计数排序用不了。但我们有另一个思路：把大数拆成一位一位的。

比如 329 可以拆成 3、2、9 三位。每一位的范围只有 0~9 —— 计数数组只需要 10 个元素。

基数排序（LSD，从最低位开始）：

从个位开始，每一位做一次【稳定】的计数排序。做到最高位，整个数组就有序了。

为什么这样做是对的？

这就是 7.2 节讲的"从低位到高位排序"：

• 先按个位排，让"个位小的"排在前面
• 再按十位排（稳定），十位相同的会保持上次个位的顺序
• 再按百位排（稳定），百位相同的保持前两次的顺序

结果：按百位、十位、个位的优先级依次有序 —— 正是我们想要的。

实测（[329, 457, 657, 839, 436, 720, 355]）：

    按个位排序后: [720, 355, 436, 457, 657, 329, 839]
    按十位排序后: [720, 329, 436, 839, 355, 457, 657]
    按百位排序后: [329, 355, 436, 457, 657, 720, 839]

每一步都必须是稳定的 —— 否则"低位已经排好的顺序"会被破坏。

基数排序是"稳定性为什么重要"的最强论据。

7.2 节说"稳定性用于多关键字排序"，基数排序正是这个思想的极致应用：它不是两个关键字，而是 $d$ 个关键字（$d$ = 位数）。

实现：

static void RadixSort(int[] a, ref long ops)
{
    if (a.Length == 0) return;

    int max = a.Max();

    // exp 依次取 1, 10, 100, ... 代表当前处理的是哪一位
    for (int exp = 1; max / exp > 0; exp *= 10)
    {
        var count = new int[10];                 // 每一位只有 0~9 十种可能
        foreach (int x in a) { count[(x / exp) % 10]++; ops++; }

        for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; ops++; }

        var output = new int[a.Length];
        for (int i = a.Length - 1; i >= 0; i--)
        {
            output[--count[(a[i] / exp) % 10]] = a[i];
            ops++;
        }

        Array.Copy(output, a, a.Length);
    }
}

复杂度：$O(d \cdot n)$，其中 $d$ 是最大数的位数。

对 32 位整数，$d \le 10$ —— 所以是 $O(10n) = O(n)$ 量级。

六、实测：非比较排序有多快

=== 实验四：非比较排序 vs 快速排序（n = 1,000,000）===

  场景 1：值域 0~999（很小）
    计数排序:      1.0 ms（操作 2,000,000 次）
    快速排序:    469.3 ms（比较 513,696,932 次）
    计数排序快 447.4 倍，结果一致=True

  场景 2：值域 0~999,999,999（很大，10 位数）
    基数排序:     42.5 ms（操作 18,000,081 次）
    快速排序:     58.9 ms（比较 24,283,927 次）
    基数排序快 1.4 倍，结果一致=True

场景 1 的 447 倍差距是我做过的最极端的对比。但要诚实地解释它：

这个 447 倍里，有两个因素叠加：

1. 计数排序确实快 —— $O(n + k) = O(100万 + 1000)$，几乎是纯线性
2. 快排在这个数据上严重退化 —— 值域只有 1000，100 万个元素里大量重复（平均每个值出现 1000 次）

第 2 点正是 8.2 节讲的"大量重复元素导致快排退化"！

所以这不是一个"公平"的对比 —— 但也正因为如此，它真实地反映了这类数据的实际情况。

如果你要排序的数据天然有大量重复（比如用户状态、订单类型、评分），快排的表现会远低于你的预期。这时候要么用三路分区，要么用计数排序。

场景 2 更能反映"公平对比"：

• 值域 10 亿（离散、几乎没有重复）
• 基数排序 42.5 ms vs 快排 58.9 ms
• 基数排序快 1.4 倍

为什么没有场景 1 那么夸张？

因为基数排序要做 10 轮（10 位数，每轮一次完整的数组遍历 + 复制）。虽然每轮是 $O(n)$，但常数不小（要分配临时数组、复制数据）。

这就是基数排序的代价：它把 $O(n \log n)$ 的比较换成了 $d$ 轮的数组操作 —— 总操作数少了，但每次操作的常数大了。

七、三种非比较/比较排序的对比

选择流程：

要排序的数据是什么？
│
├─ 值域很小（比如 0~1000 的评分、状态码）
│    -> 计数排序，O(n + k)，快得离谱
│
├─ 值域很大但是整数，且位数不多（比如 32 位整数）
│    -> 基数排序，O(d·n)，比比较排序快
│
└─ 其他情况（字符串、浮点数、自定义对象、值域未知）
     -> 用比较排序（Array.Sort / OrderBy）

最后一条很重要：基数排序只适用于整数（或能映射成整数的键）。

排序字符串可以按字符位做基数排序，浮点数可以按其二进制表示做 —— 但这些实现都很复杂，收益也不一定大。

工程上的现实：绝大多数场景用 Array.Sort 就够了。只有在"值域小"或"整数且量大"这两个明确条件下，非比较排序才值得考虑。

八、练习

练习 8.4.1（手写计数排序） 对数组 [4, 1, 3, 4, 2, 1, 4, 3] 做计数排序： (a) 写出 count 数组（值域 0~4） (b) 写出前缀和后的 count (c) 写出稳定版排序的最终结果

练习 8.4.2（判断前提） 下面四组数据，哪些适合用计数排序？哪些适合基数排序？哪些都不适合？ (a) 100 万条用户年龄（0~120） (b) 100 万条订单金额（0 到 999999.99 元，两位小数） (c) 100 万条 UUID 字符串 (d) 1000 万条 32 位整数（分布在整个 int 范围）

练习 8.4.3（判断） 判断对错并说明理由： (a) 计数排序的复杂度是 $O(n)$，所以它总是比快排快。 (b) 基数排序的每一轮可以用任意排序算法。 (c) 计数排序能突破 7.4 节证明的 $O(n \log n)$ 下界，说明那个下界是错的。

练习 8.4.4（工程判断） 一个日志系统要统计"每个 HTTP 状态码出现了多少次"，日志有 10 亿条。 (a) 你会用什么方法？ (b) 为什么不用哈希表？ (c) 如果要知道"中位数状态码"，你的方案要改吗？

练习 8.4.5（挑战·基数排序的优化） 标准的基数排序用 10 进制（每一位 0~9），要做 10 轮。 (a) 如果改用 256 进制（每次处理 1 个字节），需要几轮？ (b) 这样做的好处和坏处分别是什么？ (c) 实际实现中还会考虑什么？

九、练习答案

8.4.1

数组 [4, 1, 3, 4, 2, 1, 4, 3]，值域 0~4。

(a) 统计次数（初始 count 全为 0）：

count = [0, 2, 1, 2, 3]（下标 0~4）

验证：值 0 出现 0 次、值 1 出现 2 次、值 2 出现 1 次、值 3 出现 2 次、值 4 出现 3 次 —— 总计 8 个 ✓

(b) 前缀和：

count[0] = 0
count[1] = 0 + 2 = 2
count[2] = 2 + 1 = 3
count[3] = 3 + 2 = 5
count[4] = 5 + 3 = 8

count = [0, 2, 3, 5, 8]

含义：值 $\le 0$ 的有 0 个、值 $\le 1$ 的有 2 个、值 $\le 2$ 的有 3 个、值 $\le 3$ 的有 5 个、值 $\le 4$ 的有 8 个（全部）。

(c) 稳定版排序（从后往前遍历原数组）：

最终结果：[1, 1, 2, 3, 3, 4, 4, 4] ✓

注意第 1 步和第 5 步：原数组里下标 3 和下标 6 的值都是 4。

• 先处理下标 6（因为从后往前），它被放到下标 7
• 后处理下标 3，它被放到下标 6

所以"原本靠后的 4"放在了"更靠后的位置" —— 相对顺序保持 ✓

8.4.2

(a) 计数排序。 $n = 100$ 万，值域 $k = 121$。$k \ll n$，完美适配。

计数数组只需 121 个 int（不到 500 字节），而数据有 100 万条。极其高效。

(b) 计数排序（转成整数后）。 金额有两位小数，乘以 100 转成整数即可：值域 0 到 99999999（约 1 亿）。

但要注意：$k = 10^8$，$n = 10^6$ —— $k$ 是 $n$ 的 100 倍。

计数数组需要 $10^8 \times 4$ 字节 = 400 MB，而数据本身只有几 MB。不划算。

更好的选择是基数排序（按位拆分，每轮只需 10 个桶），或者直接用比较排序。

(c) 都不适合。 UUID 是 128 位的字符串，无法按位拆分做基数排序（会需要 $2^{128}$ 个桶），计数排序更是完全不可能。

用比较排序（Array.Sort 用的字符串比较）。或者如果只需要去重/查找，考虑哈希表。

(d) 基数排序。 32 位整数，分布在整个 int 范围。

计数排序不可行：$k = 2^{32} \approx 43$ 亿，需要 16 GB 内存。

基数排序可行：按 10 进制拆分需要 10 轮，按 256 进制拆分只需要 4 轮（见练习 8.4.5）。

但 1000 万条数据的基数排序要分配多个临时数组，内存开销也要考虑。实际中 Array.Sort 可能已经够快。

8.4.3

• (a) 错。 有两个问题：
  1. 复杂度是 $O(n + k)$ 而不是 $O(n)$ —— $k$ 是值域。$k$ 很大时它比快排慢得多（甚至内存溢出）。
  2. "总是比快排快"不成立 —— 只有 $k = O(n)$ 时才快。$k = 10^9$、$n = 10^4$ 时，计数排序要开 4 GB 数组，而快排几毫秒就排完了。
• (b) 错，而且这是基数排序的命门。 每一轮必须是【稳定】排序。

  否则低位排好的顺序会被破坏。 举个反例：如果按十位排序时不稳定，那些"十位相同、个位不同"的元素可能被打乱 —— 那么上一轮按个位排的成果就白费了。

  这就是为什么基数排序必须用"稳定版计数排序" —— 不能图省事用朴素版的。

• (c) 错。 下界没有错，只是有前提。

  7.4 节的证明明确说了："任何比较排序至少需要 $\log_2(n!)$ 次比较"。

  计数排序不是比较排序 —— 它一次比较都没做，所以那条下界不适用于它。

  "前提不成立，结论就不适用" —— 这是 7.4 节反复强调的。

8.4.4

(a) 用计数排序（或者说，就是"计数"）。

HTTP 状态码的取值范围是有限的 —— 大致是 100~599，实际常用的只有十几个（200、301、404、500……）。

方案：

开一个 int[600] 的计数数组（或者用 Dictionary 存出现过的状态码）
遍历 10 亿条日志，count[statusCode]++
输出非零的项

复杂度：$O(n)$，一次遍历搞定。10 亿条数据只需要 10 亿次数组自增，而且内存只有几 KB。

(b) 哈希表也能做，但比计数数组差。

关键优势在于：状态码的数量几乎固定，而且很少。

用数组下标直接定位，是 $O(1)$ 里最快的那种 $O(1)$ —— 没有哈希计算、没有冲突处理、缓存友好（600 个 int 只占 2.4 KB，完全在 L1 缓存里）。

这就是"值域小"的威力：一旦值域确定且不大，数组下标就是最好的哈希函数。

这其实是 6.1 节讲的"直接寻址表" —— 它虽然适用范围窄，但在适用的时候是无可匹敌的。

(c) 要改。

中位数需要"按状态码排序后取中间那个"，这需要知道每个状态码的累计出现次数。

方案：

1. 用计数数组得到每个状态码的次数 count[code]
2. 对计数数组做前缀和：prefix[i] = 状态码 ≤ i 的日志总数
3. 找到最小的 $i$ 使得 prefix[i] >= n/2 —— 那个 $i$ 就是中位数状态码

复杂度：$O(n + k)$，其中 $k = 600$（值域），几乎还是 $O(n)$。

注意这里用到的正是"前缀和" —— 和 1.4 节的前缀和、以及本节稳定版计数排序里的前缀和是同一个技巧。

前缀和出现的地方太多了：区间求和、计数排序、找中位数、找分位数…… 它是把"$O(n)$ 的重复查询"变成"$O(1)$ 单次查询"的通用手段。

8.4.5

(a) 4 轮。

32 位整数 = 4 个字节。每轮处理 1 个字节（8 位，取值范围 0~255，正好 256 个桶）。

$$\lceil 32 / 8 \rceil = 4 \text{ 轮}$$

对比 10 进制：$\lceil 32 \log_{10} 2 \rceil = \lceil 9.63 \rceil = 10$ 轮。

从 10 轮降到 4 轮。

(b) 好处和坏处：

好处：轮数减少 60%，总操作量从 $10n$ 降到 $4n$。

坏处：

1. 每轮的计数数组更大（256 vs 10）。不过这通常不是问题 —— 1 KB 而已。
2. "清空计数数组"的成本变高。每轮开始前要 Array.Clear 一个 256 长度的数组 —— 虽然还是很小。
3. 位数提取要用位运算而不是除法。(x >> 8) & 0xFF 比 (x / 100) % 10 快得多 —— 这其实是好事。

综合来看，256 进制几乎全面优于 10 进制。

(c) 实际实现还要考虑：

1. 符号位处理。 int 有负数，直接按位拆分会把负号位当最高位处理，导致负数排在正数后面。标准做法是把符号位翻转一下（x ^ int.MinValue），让所有数变成"无符号的相对顺序"。
2. 内存分配。 每轮都要分配一个 $n$ 大小的临时数组。预分配一个、反复复用（和 8.1 节归并排序的优化是同一个道理）。
3. 缓存友好性。 256 个桶的分散写入比 10 个桶更"散" —— 桶越多，写入越随机。这是 256 进制唯一的实质劣势。
4. 阈值切换。 和快排一样，小数组可以切换成插入排序（基数排序在小数据上开销不划算）。
5. MSD vs LSD。 从最高位开始（MSD）可以提前终止（某一位的桶里只有一个元素时就不用继续了），但实现更复杂。LSD 更简单，所以更常用。

一个有意思的事实：很多标准库的基数排序实现会根据数据特征自动选择 —— 比如先检查值的范围，如果小就直接计数排序，大了才用基数排序。

这正是 8.5 节的主题：生产级的排序实现不是"用一个算法"，而是"根据数据特征在多个算法之间切换"。

十、常见错误

十一、本节总结

1. 计数排序一次比较都不做 —— 它直接"看"元素的值，所以不受 $O(n \log n)$ 下界约束（那条下界只针对比较排序）。
2. 复杂度 $O(n + k)$，$k$ 是值域大小。前提是 $k = O(n)$ —— 否则内存爆炸（实测 10 亿值域需要 3 GB）。
3. 稳定版必须用前缀和 + 从后往前放置。这两步合起来保证了同值元素的相对顺序。
4. 基数排序按位拆分，每一位做一次稳定排序。复杂度 $O(d \cdot n)$，$d$ 是位数。
5. 基数排序是"稳定性为什么重要"的最强论据 —— 它把 7.2 节的"多关键字排序"思想用到了极致。
6. 实测差距惊人：值域 1000 时计数排序比快排快 447 倍（但其中也含"快排对大量重复元素退化"的因素）；10 位数时基数排序快 1.4 倍。
7. 做统计时，数组下标往往比哈希表更好 —— HTTP 状态码计数就是例子：600 个 int 的数组完全在缓存里，没有哈希计算、没有冲突。
8. 实际收益递减：基数排序要做 $d$ 轮，每轮都要复制数组。只有数据量大、值域明确时才对比较排序有实质优势。

下一节衔接：到这里，本书讲的所有排序算法都齐了。但一个现实的问题是：面对具体需求，到底该选哪个？ 而且 —— 为什么 Array.Sort 比我们手写的快排快一倍？它到底做了什么？ 下一节回答这两个问题，并给出可以直接照抄的决策流程。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "8.4",
  "title": "非比较排序：计数排序与基数排序",
  "covered": [
    "计数排序的直觉（不比较，直接数）与突破下界的原理",
    "朴素计数排序实现与 O(n+k) 复杂度",
    "值域前提的实测（10 亿值域需 3GB 内存）",
    "稳定版计数排序（前缀和 + 从后往前放置）与稳定性验证",
    "基数排序的 LSD 实现与逐位演示",
    "「每一轮必须稳定」的原因与 7.2 节的呼应",
    "实测对比：计数排序 447 倍（含快排重复元素退化因素）",
    "基数排序 1.4 倍与「轮数换常数」的代价",
    "选择流程（值域小→计数；整数大值域→基数；其他→比较排序）",
    "256 进制 vs 10 进制的优化分析",
    "数组下标胜过哈希表的场景（状态码计数）"
  ],
  "unresolved": [
    "内省排序与选型决策留到 8.5",
    "前缀和已在 1.4 节讲过，此处呼应",
    "直接寻址表已在 6.1 讲过"
  ],
  "canonical_terms": {
    "计数排序": "统计每个值出现的次数，再按值顺序输出，O(n+k)",
    "基数排序": "按位拆分，每一位做一次稳定排序，O(d·n)",
    "值域": "数据取值范围的宽度，计数排序的 k"
  },
  "symbols_units": {
    "k": "值域大小（计数排序的计数数组长度）",
    "d": "最大数的位数（基数排序的轮数）"
  },
  "assumptions": [
    "读者已掌握 7.4 的下界与 7.2 的稳定性",
    "读者理解整数除法与取模运算"
  ],
  "word_count_actual": 3260,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch08/Sec84/",
    "计数/基数排序与快排的结果一致性、性能倍率均为实测",
    "稳定性验证用 (值, 原始序号) 元组实测通过",
    "练习 8.4.1 的计数排序推演已手工验算（8 步）",
    "术语写法与 glossary.md 一致"
  ],
  "next": "8.5 工程中如何选排序"
}