算法技术手册 – 排序 – 计数排序

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

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

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

源代码:

Leave a Reply

Your email address will not be published.