计数排序

计数排序假设n个输入元素中的每一个都是介于0到k之间的整数,此处k为某个整数。当k=O(n)时,计数排序的运行时间为O(n)。线性复杂度。计数排序不是比较排序算法。稳定算法。

算法思想:对每一个输入元素x,确定出小于x的元素个数。有这个信息后,就可以把x直接放到它在最终输出数组的位置上。
假定输入数组A[1..n],length[A]=n,则存放排序结果的数组B[1..n],临时存储区C[0..k]。 Continue reading