计数排序：
如果n个待排序元素，每个元素的值都在0~k之间，k为某个整数。
当k=O(n)时，计数排序的运行时间为Θ(n)
基本思想：
对于每一个输入元素x，确定出小于等于x的元素数量m，数量m就是元素x在最终输出数组上的位置。（当有几个元素相同时，方案还有略作修改，因为不能把它们放在同一个位置上）。如：有9个元素小于x，数量9也包含x在内，x在最终已排序数组上的位置为9。
CountingSort(A, B, k)
1 let C[0..k] be a new array
2 for i ← 0 to k
3 do C[i] ← 0
4 for j ← 1 to A.length
5 do C[A[j]] ← C[A[j]] + 1
6 //此时，C[i] 包含 等于i 的元素的数量
7 for i ← 1 to k
8 do C[i] ← C[i] + C[i - 1]
9 //此时，C[i] 包含 小于等于i 的元素的数量
10 for j ← A.length downto 1
11 do B[C[A[j]]] ← A[j] //C[A[j]] 为小于等于A[j]的元素的数量
12 C[A[j]] ← C[A[j]] - 1
3 do C[i] ← 0
4 for j ← 1 to A.length
5 do C[A[j]] ← C[A[j]] + 1
6 //此时，C[i] 包含 等于i 的元素的数量
7 for i ← 1 to k
8 do C[i] ← C[i] + C[i - 1]
9 //此时，C[i] 包含 小于等于i 的元素的数量
10 for j ← A.length downto 1
11 do B[C[A[j]]] ← A[j] //C[A[j]] 为小于等于A[j]的元素的数量
12 C[A[j]] ← C[A[j]] - 1
分析：
输入数组为A，输出数组为B，数组A中元素的范围为[0,k]。
算法最后一步，每当将一个值A[j]放入数组B时，都要减小C[A[j]]的值，这样，下一个其值等于A[j]的元素直接进入数组B中A[j]的前一个位置。
运行时间：
当k=O(n)时，我们常常采用计数排序，这时运行时间为Θ(n)
计数排序的一个重要性质就是它是稳定的：具有相同值得元素在输出数组中的位置 与 它们在输入数组中的位置相同。