P4656 随机数排序（入门）

解题思路

第一步，读懂题目。 小童生成了 n 个 1 到 100 之间的随机数，要按从大到小的顺序输出。注意重复的数字必须保留，不能去重，这和"去重排序"的题不一样。

第二步，想到"桶排序"。 因为数字范围很小（只有 1 到 100），我们可以用"桶排序"（也叫计数排序），不需要把所有数先存下来再排序。开一个数组 numCnt，numCnt[v] 表示数字 v 出现了几次。

第三步，读入时计数。 读入时，遇到数字 cur 就把 numCnt[cur] 加 1，这一步同时完成了"读入"和"统计"两件事。

第四步，从大到小输出。 输出时，从 100 开始往下数到 1，如果 numCnt[v]=k，说明数字 v 出现了 k 次，就连续输出 k 个 v。因为我们是按 v=100、99、……、1 的顺序输出的，所以输出的顺序自然就是从大到小。

第五步，用样例验证。 拿样例 1 4 2 3 1 1 来说：1 出现了 3 次，2、3、4 各出现 1 次。从大到小输出就是先输出 4，再输出 3，再输出 2，最后连着输出三个 1，得到 4 3 2 1 1 1。

第六步，明白桶排序快的道理。 桶排序最大的好处是：n 再大也不用怕，因为只需要扫一遍输入，然后用 100 个桶记录每个数字出现的次数就够了，不需要把整个序列存下来。随机数的范围只有 1 到 100，如果用一般的比较排序，需要 O(n log n) 的时间；而桶排序只要扫一遍输入、再输出一遍，是 O(n) 的线性时间，快得多。如果题目要求从小到大输出，只需把循环改成从 1 到 100 正着输出即可，思路完全一样。排序算法不是越复杂越好，要根据数据的特点选择最合适的方法，这才是真正的高手思维。

参考代码

// P4656 随机数排序：数字范围只有 1~100，用桶（计数）排序从大到小输出
#include <iostream>
using namespace std;

int numCnt[101];   // 桶：numCnt[v] 记录数字 v 出现的次数

int main() {
    int n;
    cin >> n;                          // 读入随机数的个数
    for (int i = 0; i < n; i++) {      // 逐个读入每个随机数
        int cur;
        cin >> cur;
        numCnt[cur]++;                 // 数字 cur 的出现次数加一
    }
    bool firstOut = true;              // 标记是否已输出过数（用来控制空格）
    for (int v = 100; v >= 1; v--) {   // 从大到小检查每个数字
        for (int i = 0; i < numCnt[v]; i++) {   // 出现几次就输出几个
            if (!firstOut) cout << " ";         // 数之间用空格隔开
            cout << v;
            firstOut = false;
        }
    }
    cout << endl;
    return 0;
}

复杂度分析

读入时遍历 n 个数，O(n)；输出时每个数都被输出一次，也是 O(n)。再加上对 100 个桶的检查，总时间 O(n+100)。空间 O(100)，是常数。这是所有排序算法里最快的一类，非常适合数字范围小的题目。