同步发表于洛谷专栏。

怎么写出一个属于自己的排序算法呢？今天要带你写的是桶排序，顺便写一个在桶排序之上进行优化的排序算法——计数排序。

你在一个偶然的瞬间，发现一个可以不基于比较的排序算法。

我们从头开始遍历待排序数组，统计每个数字的出现次数，统计完毕后遍历计数数组，发现第 $i$ 个数字出现了 $j$ 次，那么就循环输出它 $j$ 次：

1
2
3
4
5
6
7
8
int a[maxn], b[maxn]; // 待排序数组和桶数组
for (int i = 1; i <= maxn; i++)
    b[a[i]]++;
for (int i = 1; i <= maxn; i++) // 遍历每一个数（注意不是数字）
{
    for (int j = 1; j <= b[i]; j++) // 输出出现了 j 次的 i
        cout << i << " ";
}

恭喜你已经有了桶排序的代码，但是大量学者发现一个问题，只能处理 $0 \le maxn \le 10^7$ 左右的数据，不然会运行时错误（负数）以及内存超限（大数）。

于是你开始优化它，事实上你发现桶数组只需要存储待排序数组中的最小值到最大值的个数，并不需要开到 $maxn$，所以你对其进行了优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int a[maxn], minx, maxx; // 待排序数组、待排序数组中的最小值和最大值
for (int i = 1; i <= maxn; i++)
{
    minx = min(minx, a[i]);
    maxx = max(maxx, a[i]);
}
int b[maxx - minxx + 1]; // 桶数组
for (int i = 1; i <= maxn; i++)
    b[a[i] - minx + 1]++;
for (int i = 1; i <= maxn; i++) // 遍历每一个数（注意不是数字）
{
    for (int j = 1; j <= b[i]; j++) // 输出出现了 j 次的 i
        cout << i << " ";
}

聪明的你决定把这个称作一个新的排序算法——计数排序。

但其实如果每个数（从 $0$ 到 $10^7$）都出现过一次，这个优化还是没有效果的。

事实上你可以尝试使用 STL 的 map 容器存储。

所以你打算尝试将前缀和算法加进来优化，敬请期待《怎么写出一个属于自己的排序算法——计数排序（下）》）。