计数排序

假定输入的数组是A[1...n], A.length=n
COUNTING-SORT(A,B,k)
let C[0,k] be a new array
for i=0 to k
C[i]=0
for j=1 to A.length
C[A[j]] = C[A[j]] + 1
for i=1 to k
C[i]=C[i]+C[i-1]
for j=A.length downto 1
B[C[A[j]]] = A[j]
C[A[j]]--
  1. 扫描序列A，以A中的每个元素的值为索引，把出现的个数填入C中。此时C[i]可以表示A中值为i的元素的个数。
  2. 然后，通过加总运算得到有多少个输入元素的值是小于或等于i的。
  3. 最终排序好输出数组B
比喻：
要对某次数学考试，全班同学的分数进行排名。我可以先统计，考0分的有几个，考1分的有几个，考...分的有几个。
我们假设C[i]表示考i分的有几个，这样通过循环C[i] = C[i] + C[i-1]，其实就是算出 分数小于等于i的人数有C[i]个。