计数排序与桶排序 知识点讲解

概念

想象你在整理一箱刚发下来的成绩单，分数范围只有 0 到 100 分。如果让你用普通的排序方法（比如冒泡排序或快速排序），你需要不断地拿两个分数比大小，哪怕分数已经排好了，算法可能还会继续比较，效率不高。

但如果我们换个思路：既然分数只有 0~100 这 101 种可能，为什么不开 101 个“抽屉”（桶），把每个分数直接扔进对应的抽屉里呢？比如把 85 分扔进第 85 个抽屉，把 92 分扔进第 92 个抽屉。扔完所有分数后，我们只需要从第 0 个抽屉开始，依次把里面的分数拿出来，就能得到从小到大的顺序。

这个过程不需要任何“比较”操作，只需要“计数”和“遍历”。这就是计数排序的核心思想：利用数据值域小的特点，用数组下标直接映射数据值，通过统计每个值出现的次数，最后按值域顺序还原数据。

触发清单（看到这些信号第一时间想到本知识点）

定义

计数排序不是通用的排序算法，它是专门针对值域较小的整数数据设计的。其核心逻辑是将数据的“值”直接作为数组的“下标”，通过统计每个下标位置出现的次数，实现排序或统计功能。

计数排序的三个步骤：

1. 统计：遍历数据，对每个值 v 执行 cnt[v]++。这一步的时间复杂度是 O(n)。

2. 还原：从最小值 min_v 到最大值 max_v 遍历计数数组，如果 cnt[v] > 0，则输出 v 共 cnt[v] 次。这一步的时间复杂度是 O(n + V)，其中 V 是值域大小。

3. 去重/标记：如果只需要去重，只需判断 cnt[v] > 0 即可。

和比较排序的对比：

为什么叫“桶”：把每个值想象成一个抽屉（桶），遍历数据时把元素“扔进”对应的抽屉，最后按抽屉编号从小到大倒出来。

稳定性：朴素计数排序的实现是稳定的（相同值的相对顺序不变）—— 因为我们是按原顺序统计、按值输出。这一点在多关键字排序里很重要（见下面的“基数排序”）。

技巧速查表（背下来）

原讲义配图

例题

题目描述

【自构造题】去重排序

给定一个长度为 n 的整数序列 a，其中每个元素的值都在 1 到 100 之间。请输出去重后的序列，按从小到大的顺序排列。

输入格式：

第一行一个整数 n。

第二行 n 个整数，表示序列 a。

输出格式：

输出去重后从小到大排列的整数，用空格分隔。

数据范围：

1 <= n <= 10^5，1 <= a[i] <= 100。

审题分析

1. 读题抓条件：

* 数据量 n 可以达到 10^5，如果用普通的 sort 是可行的（O(n log n)）。

* 但是，值域非常小，只有 1 到 100。这是一个极其强烈的信号：计数排序/桶排序是本题的“降维打击”方案。

* 要求去重且有序。

2. 定需求：

* 我们需要统计 1 到 100 每个数出现了几次。

* 然后按 1 到 100 的顺序，如果某个数出现过（次数大于 0），就输出一次。

3. 为什么能用本知识点：

* 计数排序的核心就是“值当下标”。这里值域 100 极小，开一个大小为 101 的数组完全没问题。

* 统计一遍 O(n)，输出一遍 O(V)，总复杂度 O(n + V)，远快于 sort 的 O(n log n)，且代码更简洁。

* 如果不用计数排序，用 sort 后 unique 也可以，但常数较大，且需要处理结构体或指针来保留原值（如果题目要求保留下标的话）。这里只要求值，桶更省事。

4. 如果不用会怎样：

* 如果值域很大（比如 1 到 10^9），开数组桶会爆内存，必须用 sort 或哈希表。

* 如果题目要求保留重复次数，桶就需要改成 int cnt[] 并展开输出。

解题思路

1. 定义一个整型数组 cnt，大小为 101，初始化为 0。

2. 读入 n 个整数，对于每个整数 x，执行 cnt[x]++。

3. 遍历 cnt 数组，从 1 到 100。如果 cnt[i] > 0，输出 i。

4. 输出时注意空格分隔，通常末尾可以有一个空格或者处理一下避免多余空格（题目一般不严格，或者用 printf("%d ", i) 即可）。

C++ 完整参考代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
 // 优化输入输出效率
 ios::sync_with_stdio(false);
 cin.tie(nullptr);

 int n;
 if (!(cin >> n)) return 0;

 // 值域 1~100，开 101 个桶，下标 0 不用
 int cnt[101] = {0};

 for (int i = 0; i < n; i++) {
 int x;
 cin >> x;
 cnt[x]++; // 统计 x 出现的次数
 }

 // 按值域从小到大遍历
 for (int v = 1; v <= 100; v++) {
 if (cnt[v] > 0) {
 cout << v << " "; // 输出一次即可（去重）
 }
 }
 cout << "\n";
 return 0;
}

代码解读

• int cnt[101] = {0};：初始化计数数组，大小为 101 是为了防止越界（值域是 1~100，下标 100 是合法的，但通常习惯开 MAXV+1）。
• for (int i = 0; i < n; i++) { cin >> x; cnt[x]++; }：这是计数排序的统计步骤。每读入一个数，就在对应的桶里加 1。这一步是 O(n)。
• for (int v = 1; v <= 100; v++) { if (cnt[v] > 0) cout << v << " "; }：这是还原步骤。因为我们是按 v 从小到大遍历的，所以输出的自然就是有序的。if (cnt[v] > 0) 保证了去重。这一步是 O(V)。

运行结果示例：

输入：

7
3 1 2 3 5 1 3

输出：

1 2 3 5 

（注：输出末尾有一个空格，符合一般评测机要求，若需严格无尾空格可加判断，但此处为演示清晰保留。）

例题复盘总结

归纳题：

• GESP202403 五级 成绩排序：值域固定 0~100，直接计数排序。
• GESP202509 四级 最长连续段：虽然涉及连续段，但核心是桶标记后扫描。
• NOIP 2006 普及组 明明的随机数：经典去重 + 排序，桶去重。
• NOIP 2007 提高组 统计数字：统计每个数出现次数，桶计数。
• CSP-J 2020 直播获奖：桶 + 反向累加求实时排名。

共性特征：

1. 值域小：所有题目都明确给出了较小的值域（如 0~100, 1~365, ASCII 码等）。

2. 统计/排序/去重：需求集中在统计频次、按值排序、去重或实时排名。

3. 在线/增量：部分题目（如直播获奖）要求每读入一个数就输出，桶的增量更新特性完美契合。

各自技巧：

• 去重：if(cnt[v]) 即可。
• 统计频次：cnt[v] 直接输出或找最大值。
• 实时排名：必须用反向累加（从高分往低分扫），累加到 >=k 即得分数线。
• 保留下标：若题目要求保留原顺序，需配合结构体或离散化。

审题模板（固定思考流程）：

1. 先看值域：题目有没有给出具体的数值范围？如果是 1e9 或浮点数，直接放弃桶。

2. 看需求：是排序？去重？统计？还是实时排名？

3. 看数据量：n 很大吗？如果 n 很大且值域很小，桶是绝对优势。

4. 看是否在线：是否需要每读入一个就输出？桶支持在线，sort 不支持。

5. 确认数组大小：值域 1..MAXV 必须开 MAXV+1，这是最容易越界的地方。

错误清单（特有）：

• 桶开小了（少一位）导致最大值越界。
• 值域大却硬用桶导致内存爆炸。
• 负数当下标导致数组越界（需整体偏移）。
• 以为桶排序“永远更快”，忽略了 V 远大于 n 时 sort 更优的情况。

写法总表

分工说明：触发清单用于识别何时该用桶（宏观决策）；技巧速查表用于具体怎么写（微观实现）；写法总表用于归纳不同需求下的变体（技法分层）。

常见错误

1. 桶开小了。值域是 1..MAXV 就要开 MAXV + 1。少开一位，当出现最大值时数组越界（有时不崩，但会改到别处的内存 —— 最危险的一类错误）。

2. 值域大却硬用桶。值域 1e9 开不了数组。这时要离散化或改用 sort。

3. 负数当下标。数组下标不能为负。有负数时要整体偏移（cnt[x + OFFSET]++）。

4. 以为桶排序“永远更快”。只有当值域 V 和 n 差不多大甚至更小时才划算。n = 100、值域 1e7 时，sort 比桶快得多。

5. 基数排序从高位开始排。必须低位先排（从个位开始），而且每一轮用的排序必须稳定 —— 顺序搞反结果就错。

自测

1. 计数排序的时间复杂度是多少？它比 sort 快在哪、又受什么限制？

2. 什么时候不能用计数排序？遇到“值域大但不同值少”该怎么办？

3. 写出“去重 + 升序输出”的桶写法（要求不用 sort）。

4. 桶的下标为什么不能是负数？怎么处理带负数的数据？

5. 基数排序为什么必须“从低位到高位”排？每一轮排序的稳定性为什么重要？

6. 值域是 1..365（天数），桶数组该开多大？

举一反三 · 审题流水线

拿到一道排序题，别急着写 sort。先让“审题流水线”跑一遍：

1. 值域扫描：题目有没有给出具体的数值范围？如果是 1e9 或浮点数，直接放弃桶。

2. 需求拆解：是排序？去重？统计？还是实时排名？

3. 数据量评估：n 很大吗？如果 n 很大且值域很小，桶是绝对优势。

4. 在线性检查：是否需要每读入一个就输出？桶支持在线，sort 不支持。

5. 数组大小确认：值域 1..MAXV 必须开 MAXV+1，这是最容易越界的地方。

6. 备选方案：如果值域大但不同值少，考虑离散化；如果只去重，考虑 set 或 sort+unique。

练手题

【练手题 1】统计数字

给定 n 个整数，每个整数在 0 到 9 之间。请统计每个数字出现的次数，并按数字从小到大输出。

输入：

5
1 2 2 3 1

输出：

1: 2
2: 2
3: 1

【练手题 2】实时分数线

有 n 个学生参加竞赛，满分 100。第 i 个学生成绩为 s_i。比赛规则是：前 w% 的学生获奖。请对每个成绩 s_i，输出该成绩对应的获奖分数线（即该成绩及以上的人数刚好达到 i*w/100 时的最小分数）。

输入：

3 50
80 90 70

输出：

80
90
90