中 · 桶计数

计数排序

你用冒泡排序比较过每一对。这一道从头到尾不比任何两个数 —— 这不是取巧,而是一笔不同的交易:用内存和一个已知的值域,换速度。

一句话答案每个值都在 0 到 100 之间，所以用 101 格的数组统计出现次数，再按顺序把值打印回来 —— O(n + 101) 而不是 O(n log n)。

题目

输入: 第一行一个整数 n(1 ≤ n ≤ 1000)。第二行 n 个空格隔开的整数,每个都在 0 到 100 之间。

输出: 把同样的数按从小到大输出,单个空格隔开。

样例:

输入输出
5
5 3 8 1 9		1 3 5 8 9
4
7 7 2 2		2 2 7 7
3
0 100 50		0 50 100

值域 0–100 不是细节,而是前提。计数排序能成立,唯一的原因是你负担得起「每个可能的值一个计数器」。如果值域到十亿,你就需要十亿个计数器。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 你已经用过计数数组了

「数字出现次数」那道题做的就是这件事:让下标就是那个值,元素是它出现的次数。排序,只是把这个数组从左往右读一遍。

提示 2 — 两层循环,一层都不比较

外层 v 从 0 到 100。内层跑 cnt[v] 次,每次打印 v。某个值出现四次就打印四次;从没出现过,内层就是零次 —— 连 if 都不需要。

提示 3 — 那个在「互不相同」时看着对的 bug

「每个值只打印一次」(无视次数)在输入互不相同时答案完全正确 —— 所以它能过第一个样例,却在一出现重复时立刻挂掉。在相信自己的代码之前,先用 7 7 2 2 试一下。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt[101] = {0};

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    for (int v = 0; v <= 100; v++) {
        for (int k = 0; k < cnt[v]; k++) cout << v << " ";
    }
    cout << endl;
    return 0;
}

计数排序是 O(n + k),k 是值域 —— 比任何比较排序都快,而比较排序无法突破 O(n log n)。这不违反那个下界:下界只约束那些通过比较来了解数据的算法,而你是通过值本身了解的。真实系统里到处都是它:按年龄、分数、像素值、字节值排序。下一题是整套题里第一个真正的递归:汉诺塔。

深度解析

为什么这样做对

让下标就是值、元素是出现次数,排序就变成把这个数组从左往右读一遍。

代价

O(n + k),k 是值域。比任何比较排序都快 —— 因为 O(n log n) 那个下界只约束<em>通过比较</em>来了解数据的算法,而你是通过值本身了解的。

常见错法

  • 每个值只打印一次、无视次数:输入互不相同时完全正确,一出现重复立刻挂掉。
  • 忘记把计数数组清零(int cnt[101] = {0};),就会在随机初值上继续累加。

下一步

整套题里第一个真正的递归:汉诺塔。

记住这两句

  • 下标就是值,元素就是次数 —— 排序变成读数。
  • 它快的前提是值域小。这是前提,不是细节。
🐞 这段是错的 —— 点开,亲手让它挂一次

每个值只打印一次 —— 只有在没有重复时才碰巧正确

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt[101] = {0};

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    for (int v = 0; v <= 100; v++) {
        if (cnt[v] > 0) cout << v << " ";
    }
    cout << endl;
    return 0;
}