算法七：计数排序（O(n+k)）

 

计数排序假设n个输入元素中每一个都是介于0到k之间的整数，此处k为某个整数。当k=O(n)时，计数排序的运行时间为O(n)（其实是O(n+k)）。

计数排序的思想就是：对每一个元素x，确定出小于x的元素的个数，从而根据这个信息直接把元素x放在输出的位置上。

 

假定A[1..n]为输入，B[1..n]为输出，C[1..k]为临时存储区：

counting_sort(A, B, C)

1   for i in 0 to k

2           do C[i] = 0

3   for j in 1 to length[A]

4           do C[A[j]] ++                //C[i]包含等于i的元素的个数

5   for i in 1 to k 

6           do C[i] += C[i-1]          //C[i]包含小于等于i的元素的个数

7   for j in length[A] to 1

8           do B[C[A[j]]] = A[j]

9                 C[A[j]] --

 

计数排序有个重要的性质就是它是稳定的：具有相同值的元素再输出数组中的相对次序与它们在输入数组中次序是相同的。