计数排序

计数排序不是基于比较的排序。假设n个输入元素中的每一个都是介于0到k之间的整数，当k=O(n)时，计数排序的运行时间是线性的。
计数的基本思想是对每一个元素x，确定出小于x的元素个数。据此可以把x直接放到最终输出数组的位置上。

counting-sort(A, B, k)   
for i = 0 to k  
    do C[i] = 0  
for j = 1 to length[A]  
    do C[A[j]] = C[A[j]] + 1  
//C[i]包含等于i的元素的个数  
for i = 1 to k  
    do C[i] = C[i] + C[i - 1]  
//C[i]包含小于或等于i的元素个数  
for j = length[A] to 1  
    do B[C[A[j]]] = A[j]  
       C[A[j]] = C[A[j]] - 1