S3 计数排序与手写排序（25 分钟补丁）

这是什么： 当"数值的范围"很小的时候，不用比较也能排序——直接拿数值当数组下标去数个数。以及三种必须会手写的基础排序。

为什么现在补： L02 只教了调用 sort。但 CSP-J 有两类题 sort 救不了你：CSP-J 2020 T2 直播获奖（P7072）用 sort 会超时，CSP-J 2025 T1 拼数（P14357）数据量 10⁶。而手写排序是 NOI 大纲入门级明文要求的（2.1.4-6），CSP-J 2021 T2 的题目名字就叫"插入排序"。

前置： L04 的数组、L02 的 sort。

一、最小可用模板

1.1 计数排序（桶排序）：拿数值当下标

核心只有一句话：开一个数组 cnt，cnt[v] 表示数值 v 出现了几次。

#include <bits/stdc++.h>
using namespace std;

int cnt[605];      // 值域是 0~600，所以开 601 个就够，留点余量

int main() {
    int a[8] = {5, 3, 5, 1, 3, 3, 0, 5};

    for (int i = 0; i < 8; i++) {
        cnt[a[i]]++;               // 第一步：数个数
    }

    for (int v = 0; v <= 600; v++) {   // 第二步：从小到大，出现几次就打印几次
        for (int k = 0; k < cnt[v]; k++) {
            cout << v << " ";
        }
    }
    cout << endl;                  // 0 1 3 3 3 5 5 5
    return 0;
}

📝 计数排序的时间是 O(n + 值域)，和"比较"完全无关。 值域只有 600 而 n 有 10 万时，它比 sort 的 O(n log n) 快得多；更重要的是，它支持"边加边查"——每来一个新数字只要 cnt[v]++，不用把整个数组重排一遍。这正是直播获奖那道题的命门。

1.2 计数数组的三种用法

同一个 cnt 数组，换个读法就是三种工具：

#include <bits/stdc++.h>
using namespace std;

int cnt[10];

int main() {
    string s = "9a2b100";

    // 用法一：数每个数字出现几次
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] >= '0' && s[i] <= '9') cnt[s[i] - '0']++;
    }

    // 用法二：从大到小拼出最大的数（CSP-J 2025 T1 就是这个）
    for (int v = 9; v >= 0; v--) {
        for (int k = 0; k < cnt[v]; k++) cout << v;
    }
    cout << endl;                  // 92100

    // 用法三：数一共有几种不同的数字（去重计数）
    int kinds = 0;
    for (int v = 0; v <= 9; v++) {
        if (cnt[v] > 0) kinds++;
    }
    cout << kinds << endl;         // 4  （9、2、1、0 四种）
    return 0;
}

📝 "有几种不同的"就是 cnt[v] > 0 的个数。 CSP-J 2024 T1 扑克牌（P11227）问"还差几张凑齐 52 张"，答案就是 52 - 不同牌的种数。

1.3 三种手写排序

sort 平时够用，但题目直接考排序过程时得会写。三种都是 O(n²)，n ≤ 5000 时随便用。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 6;
    int a[6] = {5, 2, 9, 1, 5, 6};

    // 冒泡排序：相邻两个比，大的往后冒
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
        }
    }
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;                  // 1 2 5 5 6 9
    return 0;
}
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 6;
    int a[6] = {5, 2, 9, 1, 5, 6};

    // 选择排序：每轮从没排好的部分挑一个最小的，换到最前面
    for (int i = 0; i < n - 1; i++) {
        int mn = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[mn]) mn = j;
        }
        swap(a[i], a[mn]);
    }
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;                  // 1 2 5 5 6 9
    return 0;
}
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 6;
    int a[6] = {5, 2, 9, 1, 5, 6};

    // 插入排序：把 a[i] 往左边已排好的部分里插到合适位置
    for (int i = 1; i < n; i++) {
        for (int j = i; j >= 1; j--) {
            if (a[j] < a[j - 1]) swap(a[j], a[j - 1]);
            else break;            // 左边已经比它小了，不用再往前挪
        }
    }
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;                  // 1 2 5 5 6 9
    return 0;
}

📝 插入排序只在 a[j] < a[j-1]（严格小于）时才交换，所以它是稳定的——两个相等的元素永远不会被交换，原来的先后顺序保得住。这条性质就是 CSP-J 2021 T2 的钥匙，详见 S2_排序的稳定性与原下标技巧.md。

📝 swap(x, y) 是 bits/stdc++.h 自带的，直接用，不用自己写三行交换。

二、两个坑

⚠️ 坑 1：桶数组的大小要按"值域"开，不是按 n 开。

int n;  cin >> n;          // n = 100000
int cnt[100005];           // 你以为够了
// 分数最大 600 → cnt[600] 没问题
// 但如果值最大能到 10^6，这个数组就越界了

📝 cnt 的下标是"数值"，所以长度必须 ≥ 最大可能的数值 + 1，和有多少个数完全无关。看题时先找"每个数最大是多少"，不是"有多少个数"。

⚠️ 坑 2：值域太大时不能用桶。

值能到 10⁹ 的话，int cnt[1000000005] 开不出来（内存爆炸）。桶排序换来速度的代价就是内存。

📝 判断标准很简单：值域 ≤ 10⁶ 左右可以开桶，再大就老实用 sort。 直播获奖里那句"分数是不超过 600 的非负整数"就是出题人在告诉你可以开桶。

三、配套真题

三道题都在练同一个 cnt 数组的不同读法：

思路提示见 S8_真题分级提示.md，代码自己写。

四、30 秒自测

  1. 有 10 万个数，每个数在 0~600 之间。用 sort 和用计数排序，各是多少复杂度？
  2. cnt 数组该开多大，取决于什么？
  3. 三种手写排序里，哪一种是稳定的？为什么？
答案
  1. sort 是 O(n log n) ≈ 10⁵ × 17；计数排序是 O(n + 值域) = 10⁵ + 600。差距在单次排序上不算大——真正的差距在于计数排序支持"来一个数字更新一次"，而 sort 每次都得整个重排一遍。
  2. 取决于值域（最大可能的数值），和数字个数 n 无关。
  3. 插入排序（写成严格小于才交换时）。相等的两个元素不会触发交换，原有先后顺序保持不变。

以后学： 归并排序、快速排序、堆排序都是 O(n log n) 的，属于提高级（大纲 2.2.4），本次冲刺用 sort 代替即可。