常见排序算法9——计数排序

计数排序（Counting Sort）是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序。

算法描述

计数排序是一种非比较性质的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。计数排序过程中不存在元素之间的比较和交换操作，根据元素本身的值，将每个元素出现的次数记录到辅助空间后，通过对辅助空间内数据的计算，即可确定每一个元素最终的位置。

作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

1）获取待排序列中的最小值min和最大值max

2）统计min - max之间所有值在待排序列中出现的次数

3）顺序输出min - max区间所有值，按次数输出多次，次数为0的则不输出

代码实现

PHP代码

算法复杂度与稳定性

时间复杂度：O(n+k)

空间复杂度：O(k)

稳定性：代码中所实现的计数排序是不稳定的，但可以对上述代码进行优化使其稳定