计数排序直觉

数好每个值出现几次（上一节的桶），排序就几乎白送了：从最小的值到最大的值，按桶里的次数把每个数依次输出，出来的自然就是从小到大有序的。这叫计数排序——它靠“数数”排序，全程不做任何比较。

int cnt[MAXV] = {0};
for (int i = 0; i < n; i++) cnt[a[i]]++;   // 统计
for (int v = 0; v < MAXV; v++)             // 按值从小到大
    for (int k = 0; k < cnt[v]; k++)       // 出现几次就输出几次
        cout << v << " ";

比如 cnt[2]=3，就把数字 $2$ 连续输出 $3$ 次。

设值域大小为 $V$，复杂度是 $O(n+V)$：当 $V$ 和 $n$ 差不多大时，这比 sort 的 $O(n\log n)$ 还快，是一种线性排序。

代价和桶计数一样：只适用于整数且值域不太大。值能到 $10^9$，或是小数、负数（负数要先做偏移）时就不好用，这时还是老实用 sort。