<转>线性排序算法：Counting Sort

计数排序的限制条件是：所排对象的各个元素都是介于0--k的，并且这个k不是无限的，是在有限的内存里能用数组表示的。

计数排序的基本思想是，当读到一个数时，如果能确定出比这个元素小的数的个数，那这个数应该排的位置自然就知道了。为了实现这个目标，计数排序引入了2个辅助数组，B和C。假设原数组是A，长度为n，数组B的长度也是n；假设每个元素的范围是0--k，那数组C的长度就是k。例如，已知我有一组数 2 5 3 0 2 3 0 3，所有数的范围都在0---5之间，那我们的数组C声明就应该是int C[6];

然后具体做法就是，遍历一遍A，读入一个数，就在对应C的位置+1，例如，读入一个数2，就让 C[2]++，这样，读完一遍以后就知道各个数出现了多少次。然后对C进行整理，得出比这个数小的有多少个(或者将这个数视为该数在排序后序列中应该存放的位置index，比如C[i] = 3,　则有3个数比A[i]小，A[i]应存在b[3]，即排序后的第4个位置上)，整理办法如下：

// assume C[0..k]

for i = 1 .. k do:

    C[i] = C[i-1] + C[i]

最后得出了各个数都有多少个比它小的个数以后，就可以进行最后的排序了：

遍历A，读入一个数x后就去C里找他应该放的位置，即C[x]的值就是他应该放的位置，放入B数组的该位置中，然后对应的C[x]-- (因为考虑到可能有重复的数)。

for i = 0 .. n do:

       x = A[i]

       index = C[x]

       B[index] = x

       C[x]--