队列（排序）
题目
我排着队拿着爱的号码牌。
"追我的人从这里可以排到巴黎"，小R在网上冲浪时总会有一些新的发现："你说，如果有这么多人追我，我肯定得让他们每个人都取个号。"
小J贫到："那你是不是还要让他们按大小排个序。"
小R："那当然了，我还要让负数排在前面！重复的就让他们随便站着吧！"
小R已经停不下幻想了，决定在计算机上先模拟一下，想邀请你和他一同完成。 小R幻想有 n 个人拿着号码牌在排队，这些号码牌有正有负，不过绝对值都在 10000 以内， 她希望你能够把他们按照从小到大进行排序。
输入：共 2 行。第 1 行，一个整数 n，表示有多少个人拿着号码牌；第 2 行，n 个整数 a₁, a₂, …, aₙ，表示每个人号码牌上的数字。
输出：共 1 行，输出 n 个整数，表示按照从小到大排序后每个人手上的号码牌。
数据范围：对于 40% 的数据，n ≤ 1000；对于 60% 的数据，n ≤ 100000；对于 100% 的数据，n ≤ 10000000、|aᵢ| ≤ 10000。其中 50% 的数据中，所有号码牌均为非负整数。
样例：
输入 8 0 20 60 -20 20 60 0 10 → 输出 -20 0 0 10 20 20 60 60
思路
n 最大 1000 万，用 std::sort 是 O(n log n)，约 2 亿次操作，加上 I/O 很可能 TLE。
但题目给了一个隐藏条件：值域只有 [-10000, 10000]，共 20001 个不同值。
这正是计数排序的适用场景：开一个大小 20001 的桶数组 cnt[]，
读入每个数 x 时令 cnt[x + 10000]++（偏移 10000 避免负数下标）。
读完后按下标从小到大遍历桶，每个桶输出对应次数的值，天然有序，重复元素也自动处理。
整体复杂度 O(n + k)，k = 20001，远快于比较排序。
#include<bits/stdc++.h>
using namespace std;
int cnt[20001]; // 桶数组，下标 0~20000 对应值 -10000~10000
int main(){
int n;
scanf("%d", &n);
for(int c = 0; c < n; c++){
int x;
scanf("%d", &x);
cnt[x + 10000]++; // +10000 偏移，将负数下标变为非负，往桶里扔一个球
}
bool first = true; // 用于控制输出格式，避免开头多一个空格
for(int c1 = 0; c1 <= 20000; c1++){ // 从小到大扫所有桶
for(int c2 = 0; c2 < cnt[c1]; c2++){ // 这个桶有几个球就输出几次
if(!first) printf(" ");
printf("%d", c1 - 10000); // -10000 还原真实值
first = false;
}
}
printf("\n");
return 0;
}复杂度分析
- 时间复杂度：O(n + k)，k = 20001，线性。
- 空间复杂度：O(k)，固定大小桶数组，与 n 无关。
看到 n 很大就想快排，但看到值域有限才是真正的突破口。计数排序不需要比较，天然处理重复，是值域受限时的利器。
另外 n = 10⁷ 时 cin 会 TLE，大数据量一律 scanf/printf。