排序算法七：计数排序

一、计数排序

其基本思想为：假设n个输入的元素中的每一个都是在0到k之间的一个整数，对于每一个输入元素x，确定小于x的元素个数，直接把x放在它输出的数组中的位置上。例如有17个元素小于x，则x就应该在数组的第18个位置上。当有几个元素相同时，这一方案就要略作修改，不能都放在同一个位置上。

计数排序需要提供两个辅助数组用来计数，一个用来保存已经排好序的元素，一个用来保存每个元素在数组中出现的次数。计数排序是不稳定的排序算法，时间复杂度(n)，空间复杂度是O(n + k)，其中k是排序数组元素的范围。

例如以下数组A：

在通过计数后，得到的辅助数组C为：

对于元素1而言，它前面有两个0，因此排序后它的位置在第三个，即下标为2的位置上，但是它的数量为0，就不应该给他排序。而元素2是有的，它的位置应该是0的数量和1的数量（如果有元素1的话）之和的后面一位，在这里是第3位，下标为2。这里类似斐波那契数列：每个元素都等于前面两个的和。

因此，有必要对辅助数组C做处理，设置其所在的位置为前面所有元素数量之和，这样就不用每次都重新计算前面的数量了（参考斐波那契数列计算）：

要注意的是，对于2这个元素来说，它出现了两次，如果不做特殊处理，它们处的位置都是第四个位置。要想办法把两个2分别放到自己合适的位置上去。可以采取的办法是从后往前排序，每排完一个数字，当前数字的值减一。

图例：

第一步，A的最后一个元素是3，得到C[3]的值为7，把3先放到第7个位置，并把C[3]的值减一：

第二步，现在A的最后一个元素（未排序的）是0，得到C[0]为2，放到第二个位置，C[0]减一：

第三步，重复以上步骤，直到A中所有的元素都排序完毕：

此时，整个数组就是有序的了。

二、计数排序的代码实现