信息学竞赛 C++ 教材

Appearance

第 42 章 不比较的排序——计数排序与基数排序 ​

🏗️ 前情回顾：前几章学的排序——冒泡、选择、插入、归并、快排——都靠"比较"来决定元素的先后。它们的下界是 O(n log n)。但你有没有想过：如果数据有特殊性质，能不能更快？答案是能——计数排序和基数排序在特定条件下可以达到 O(n)，突破了比较排序的理论下限。它们不是"比"出来的，而是"算"出来的。

🎯 本章目标 ​

学完这一章，你能：

  • 理解计数排序的"桶"思想——用下标直接映射值
  • 手写计数排序，知道它适合什么数据
  • 理解基数排序——按位排序，从低位到高位
  • 分析 O(n) 排序的适用条件和局限性
  • 了解桶排序的基本概念
  • 学会根据数据特征选择合适的排序算法

📖 故事引入 ​

假设你要给全班 50 个人按"0 到 100 分的考试成绩"排序。你当然可以用 sort()，一瞬间搞定。

但如果你换一种更"物理"的思路：在黑板前摆上 101 个盒子，标着 0 分、1 分、2 分……100 分。你挨个念成绩，念到 85 分就把那个人的名字扔进 85 号盒子。全部念完后，从 100 号盒子开始一个个往外掏——分数从高到低，自然排好了。

你用了多少时间？念 50 个人的成绩：O(n)。从 101 个盒子里掏：O(数据范围)。总时间 O(n + 数据范围)。

这就是计数排序——不比较，不交换，直接"归类"。

🧱 知识讲解 ​

42.1 计数排序（Counting Sort） ​

核心思想：统计每个值出现了多少次，然后根据计数"还原"出有序序列。

使用条件：数据范围（最大值 - 最小值）不能太大。如果 n = 10⁵ 但数值范围是 1 到 10⁶，计数排序空间和时间都可接受。但如果数值范围是 1 到 10⁹，数组开不出来，就不能用。

步骤：

  1. 统计：遍历数组，cnt[a[i]]++
  2. 前缀和：cnt[i] += cnt[i-1]（确定每个值的最终位置）
  3. 放置：从后往前遍历，放入结果数组

C++ 实现（值域 0 ~ MAXV）：

cpp
const int MAXV = 100000;  // 最大可能值
int cnt[MAXV + 1];

void countingSort(int a[], int n) {
    // 1. 清空计数数组
    memset(cnt, 0, sizeof(cnt));

    // 2. 统计每个值出现次数
    for (int i = 0; i < n; i++)
        cnt[a[i]]++;

    // 3. 根据计数还原
    int idx = 0;
    for (int v = 0; v <= MAXV; v++) {
        while (cnt[v] > 0) {
            a[idx++] = v;
            cnt[v]--;
        }
    }
}

🎯 复杂度：O(n + MAXV)。如果 MAXV 和 n 同级别，就是 O(n)。空间 O(MAXV)。稳定（如果从后往前放置）。

用前缀和实现稳定版（保证相等元素相对顺序不变）：

cpp
void countingSortStable(int a[], int n, int output[]) {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; i++) cnt[a[i]]++;
    for (int i = 1; i <= MAXV; i++) cnt[i] += cnt[i-1];  // 前缀和
    for (int i = n - 1; i >= 0; i--) {                   // 从后往前
        output[cnt[a[i]] - 1] = a[i];
        cnt[a[i]]--;
    }
}

42.2 计数排序的局限性 ​

计数排序看起来很美——O(n)！但它有苛刻的前置条件：

  1. 值域必须小：如果有数值是 10⁹，你开不出 cnt[1000000010]。如果值域很大但数据很少，计数排序反而不如 sort()。
  2. 只能排整数（或可映射为整数的东西）：无法直接排浮点数、string。
  3. 空间和值域绑定：O(MAXV) 的空间在 MAXV 很大时不可接受。

📝 小技巧：如果数据范围在 [L, R] 之间且 R-L 不太大，可以把值偏移：cnt[a[i] - L]++，下标从 0 开始，节省空间。

42.3 基数排序（Radix Sort） ​

计数排序不能处理大范围数据，那有没有办法既利用"计数"的 O(n) 优势，又能排大数？

有——基数排序。思路是把大数"拆成每一位"，对每一位分别用计数排序。

核心思想：从最低位开始，逐位排序。每一位的排序是稳定的（这点至关重要！）。

过程（以 [170, 45, 75, 90, 802, 24, 2, 66] 为例）：

原始：     170  45  75  90  802  24  2  66
按个位排： 170  90 802  24  45  75  66   2   (只关心个位数)
按十位排： 802   2  24  45  66 170  75  90   (在保持个位有序基础上排十位)
按百位排：  2  24  45  66  75  90 170 802   (在保持低两位有序基础上排百位)

注意！第三次排完后，低两位的有序性被保留——因为每次排序都是稳定的。

C++ 实现（十进制，处理非负整数）：

cpp
// 对 a[] 中 n 个元素，按第 exp 位（1=个位,10=十位,100=百位...）做计数排序
void countSortByDigit(int a[], int n, int exp) {
    int output[n];
    int cnt[10] = {0};                  // 每位只有 0~9

    for (int i = 0; i < n; i++)
        cnt[(a[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        cnt[i] += cnt[i - 1];           // 前缀和

    for (int i = n - 1; i >= 0; i--) {  // 从后往前保证稳定
        int digit = (a[i] / exp) % 10;
        output[cnt[digit] - 1] = a[i];
        cnt[digit]--;
    }

    for (int i = 0; i < n; i++)         // 拷回原数组
        a[i] = output[i];
}

void radixSort(int a[], int n) {
    int maxVal = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] > maxVal) maxVal = a[i];

    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countSortByDigit(a, n, exp);
}

🎯 复杂度：O(d × n)，其中 d 是最大数的位数。对于 int（最多 10 位），d ≤ 10，所以几乎是 O(n)。空间 O(n + 10)。

类比：基数排序就像在图书馆整理按"出版年份（4 位数字）"编目的书。你不用比较每本书的年份大小，而是按个位排一轮、按十位排一轮、按百位排一轮、按千位排一轮——四轮下来，所有书就按年份顺序排好了。

42.4 桶排序（Bucket Sort）概念 ​

桶排序是计数排序的泛化版本：

  1. 把值域分成若干个"桶"（区间）
  2. 把每个元素放进对应的桶里
  3. 对每个桶内部单独排序（随便用什么排序，比如 sort()）
  4. 按桶的顺序依次输出

如果桶的个数和规模设计得当，平均也能达到 O(n)。桶排序在数据均匀分布时效果特别好。

📊 竞赛中，桶排序用得不多（因为 sort() 已经很好了），但它的"分桶"思想在别的题里反复出现——尤其是分块算法（M8 会接触）。

✋ 动手试试 ​

试试 1：输入 20 个 0~100 之间的整数，用计数排序排好输出。和 sort() 的结果对比，确认正确。

试试 2：手动模拟基数排序。取 [53, 14, 27, 38, 92, 11]，写出每轮（个位、十位）之后的结果。

试试 3：写一个程序，分别用计数排序和 sort() 对 10⁷ 个范围在 [0, 100] 的随机数排序，用 clock() 比速度。你猜谁更快？

⚠️ 容易犯的错 ​

错 1：计数排序数组开小了 ​

❌ 数据范围 0~1000，但只声明 cnt[100]

✅ 声明 cnt[1001]——留出最大值的位置，必要时先扫一遍找最大值

错 2：基数排序的中间排序不稳定 ​

❌ 基数排序里每一位的排序用了不稳定的方法——最后结果可能全乱了

✅ 每一轮必须用稳定的排序（如从后往前放置的计数排序）

错 3：忽略负数 ​

❌ 计数排序的数组下标不能为负

✅ 处理负数的方法：先找最小值 minVal，把每个元素减去 minVal 映射到非负范围。比如 [-5, 10] → 偏移 +5 → [0, 15]

错 4：盲目使用计数排序 ​

❌ "计数排序是 O(n)，肯定比 sort 快！"——数据范围 1~10⁹ 时直接爆内存

✅ 先判断数据范围！范围小时用计数，范围大时老老实实用 sort

📝 练习 ​

基础题 ​

1. 选择题

（1）计数排序的时间复杂度是：
A. O(n)   B. O(n log n)   C. O(n + MAXV)   D. O(n²)

（2）基数排序需要多少次稳定排序（对 int 类型）？
A. 1 次   B. 10 次   C. 32 次   D. 取决于最大值

（3）以下哪种数据最适合用计数排序？
A. 10⁵ 个 1~10⁹ 的随机数   B. 10⁶ 个 0~1000 的整数   C. 100 个字符串   D. 10⁴ 个浮点数

2. 填空题

（1）计数排序的核心数据结构是 _____ 数组。

（2）基数排序是从 _____ 位到 _____ 位进行的（填"低/高"）。

（3）桶排序中，每个桶内部可以用 _____ 排序。

提高题 ​

3. 编程题 — 成绩统计

输入 n 个学生的成绩（0 ≤ 成绩 ≤ 100，可能有重复）。用计数排序将成绩从小到大输出，同时输出每个分数段的人数：

  • 0~59：不及格
  • 60~79：良好
  • 80~100：优秀

4. 编程题 — 基数排序实现

输入 n 个非负整数（每个 ≤ 10⁹），用基数排序将它们升序排列并输出。要求完整实现 radixSort()，每轮用计数排序处理一位。

挑战题 ​

5. 编程题 — 字符串排序（基数排序思想）

输入 n 个长度相同的字符串（只含小写字母），用基数排序的思想将它们按字典序排列。

提示：每个字符可以看作 26 进制的一位（'a'=0, 'b'=1, ..., 'z'=25），从最后一个字符开始向前，逐位做计数排序（每轮 26 个桶）。

🧠 本章小结 ​

计数排序：
  统计每个值的出现次数 → 按值从小到大输出
  O(n + MAXV)，适用于值域较小的整数
  不是严格意义上的 O(n)：MAXV 大了就不行

基数排序：
  按位排序，低位到高位，每一位用稳定的计数排序
  O(d × n)，d 是位数
  解决了计数排序"值域大"的问题——值域 10⁹ 也只需要 10 轮

桶排序：
  把值域分成桶 → 元素入桶 → 桶内排序 → 合并
  数据均匀分布时平均 O(n)

记住：没有万能排序，每种排序都有它的"舒适区"
竞赛中：一般情况下直接用 sort()，遇到特定条件才考虑计数/基数

📝 配套练习 ​

共4题。计数排序条件：值域小→P1271(投票)/P1059(随机数)完美匹配。。★核心（课堂必做） ◆拓展（课后练习）

级别题号链接覆盖知识点
★ 核心luogu-P1271https://hydro.ac/p/luogu-P1271计数排序、桶统计
◆ 拓展luogu-P1923https://hydro.ac/p/luogu-P1923nth_element、第k小
◆ 拓展luogu-P1059https://hydro.ac/p/luogu-P1059计数排序版去重（值域小）
◆ 拓展luogu-P1090https://hydro.ac/p/luogu-P1090桶思想、合并果子

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 3 道◆拓展题，覆盖不同变式和细节。

配套练习 ​

共4题。计数排序条件：值域小→P1271(投票)/P1059(随机数)完美匹配。★核心（课堂必做） · ◆拓展（课后练习）

级别题号链接覆盖知识点
★ 核心luogu-P1271https://hydro.ac/p/luogu-P1271计数排序、桶统计
◆ 拓展luogu-P1923https://hydro.ac/p/luogu-P1923nth_element、第k小
◆ 拓展luogu-P1059https://hydro.ac/p/luogu-P1059计数排序版去重（值域小）
◆ 拓展luogu-P1090https://hydro.ac/p/luogu-P1090桶思想、合并果子

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 3 道◆拓展题，覆盖不同变式和细节。

自查清单：

  • [ ] 我能手写计数排序，理解 cnt 数组的作用
  • [ ] 我知道计数排序的适用条件（值域小、整数）
  • [ ] 我理解基数排序"按位排、低位优先"的原理
  • [ ] 我知道为什么基数排序的每一轮必须是稳定的
  • [ ] 我了解桶排序的基本概念
  • [ ] 我能根据题目数据特征选择计数/基数/sort

🚀 下章预告：M6 的最后一章来了！把前面学的冒泡、选择、插入、归并、快排、计数、基数，再加上 sort，融会贯通。我们做一张"排序全景对比表"，然后学一个重要的排序应用——逆序对。第 43 章，给你的排序工具箱做一次彻底的大盘点。