计算排序基本信息

Counting sort 是一个整数排序算法，用于根据对象的键进行排序的对象集合。

脚步

1. 构造一个工作阵列 ç 具有大小等于输入数组范围A。
2. 通过 A 迭代，根据 x 出现在 A 中的次数分配 C [x] 。 **
3. 将 C 转换为一个数组，其中 C [x]通过遍历数组指向值的数量≤x，为每个 C [x]指定其先前值和 C 之前的所有值之和。
4. 向后遍历A，将每个值到一个新排序后的数组B记录在索引处 Ç 。对于给定的 A [x]，通过将 B [ C [ A [x]]]分配给 A [x]来完成，并且在原始未排序的数组中存在重复值的情况下递减 C [ A [x]]。

计数排序的示例

http://i.stack.imgur.com/ccdTK.jpg

辅助空间： O(n+k)
时间复杂度： 最坏情况：O(n+k)，最佳情况：O(n)，平均情况 O(n+k)