计数排序(Counting Sort)

与比较排序注重于元素之间的比较不同，计数排序专注于找准自己的位置，而不关心
自己比谁小，比谁大。其核心在于，对于任意一个属于数组A的元素x，统计出在A中有
多少个元素小于等于x,以确定x的位置。例如，有10个元素小于等于a那么a就应该排在
第11位。

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

计数排序是一种线性时间非比较类排序，典型的以空间换时间的策略

算法模型：

假设对数组A[n]进行排序,A[n]中任意一元素x∈[0，k)。我们需要两个辅助数组，一个为C[k],我们用来记录统计信息，另一个为B[n],用来储存排序结果。

1. 用下标i迭代数组A，用C[i]记录A中等于i的元素个数。
2. 迭代数组C，用C[i]记录小于等于i的元素的个数。
3. 根据B中的统计信息，将A中的元素放到B中合适的位置。

实现过程

第一步，如图所示，用下标i迭代数组A，用C[i]记录A中等于i的元素个数。

第二步，迭代数组C，用C[i]记录小于等于i的元素的个数。

简单思路就是C[i] = C[i]+C[i-1]

最后一步，根据整理后的数组C，将A中的元素放到B中合适的位置。

思路就是迭代A，将A[i]放入B[i]中，C[i]统计A[i]出现的次数，循环结束后，依次将C[i]统计得到的个数下落到C[i]中，得到排序结果

img