P4641 按身高排序（基础）

解题思路

班上有 n 个同学，要按身高从低到高排队。身高只有 110 到 180 厘米这些可能的数值，范围非常小，所以我们用"计数排序"的方法：先准备 71 个小桶（一个数组 cnt[181]），编号 110 到 180，每个桶专门放"身高等于桶号的同学"。读入一个身高 h，就往第 h 号桶里丢一颗小石子（cnt[h] 加一），表示这个身高又出现了一次。

全部读完之后，从 110 号桶开始，从小到大挨个检查：如果 110 号桶里有 cnt[110] 颗石子，就把 110 输出 cnt[110] 次；接着看 111 号桶、112 号桶……一直检查到 180 号桶。这样输出的身高就一定是从小到大排列的。整个过程就像给扑克牌按点数分堆，分好堆再按顺序倒出来，天然就是有序的。

注意几个细节：第一，题目说身高的取值范围是 110~180，所以桶从 110 编号到 180，不要写成从 0 开始。第二，n 最多有 100000 人，用计数排序只要 O(n) 的时间，比两重循环的排序快得多。第三，输出时数字之间要用空格隔开，最后一个数字后面不能有多余的空格，所以用一个 first 标记来判断是不是第一个数字。这种"用桶统计次数、再按桶的编号输出"的办法，就是典型的计数排序，它非常适合数据范围小、数据量大的题目。

参考代码

// 使用计数排序把学生身高从低到高输出
#include <iostream>
using namespace std;

int main() {
    int n; // 学生人数
    cin >> n; // 读入学生人数
    int cnt[181] = {0}; // cnt[x]表示身高x出现的次数
    for (int i = 0; i < n; i++) { // 依次处理每位学生
        int h; // 当前学生的身高
        cin >> h; // 读入当前身高
        cnt[h]++; // 记录这个身高出现一次
    }
    bool first = true; // 判断是否已经输出过数字
    for (int h = 110; h <= 180; h++) { // 按身高从低到高检查
        for (int j = 0; j < cnt[h]; j++) { // 输出这个身高的所有学生
            if (!first) { // 不是第一个数字时先输出空格
                cout << ' '; // 输出数字之间的空格
            }
            cout << h; // 输出当前身高
            first = false; // 标记已经输出过数字
        }
    }
    cout << '\n'; // 输出换行
    return 0; // 程序结束
}

复杂度分析

程序先循环 n 次读入身高并计数，又循环 110 到 180 共 71 次输出，所以时间复杂度是 O(n)，当 n=100000 时依然飞快。程序只用了一个长度 181 的计数数组，空间是固定的常数级别，即 O(1)。