如果已知被排序的n个元素，值范围固定在在 "[0,k)"内]，那么计数排序是最好的选择，它具有线性复杂度。

这个约束有些过强，有些时候，可以将不满足这个条件的转化一下：
比如 [-k, k)映射]到[0, 2k)等]。
再比如1/p的小树映射到p k-p等等。

下面上算法，主要走两遍：
首先建立k个桶
(1)扫描n个元素，增加对应桶中的计数
(2)从小到大扫描k个桶，计数非零则减一，然后顺序、依次输出。

源代码：
#include <stdio.h>[......]

继续阅读