算法：计数排序（CountingSort）、基数排序（RadixSort）

1. 计数排序（CountingSort）

1.1. 基本原理

计数排序是通过对待排序序列中的每种元素的个数进行计数，然后获得每个元素在排序后的位置的排序算法。即：对每一个输人元素 x，确定小于 x 的元素个数，然后就可以直接把 x 放到它在已排序数组中的位置上。

1.2. 代码示例

1.3. 特性分析

• 时间复杂度：O(n)；
• 空间复杂度：O(m);
• 当数列最大最小值差距过大时，并不适用计数排序。
• 当数列元素不是整数，并不适用计数排序。

2. 基数排序（RadixSort）

2.1. 基本原理

基数排序用于对多关键字域数据（例如：一副扑克牌，大小可以看做一个关键字域，花色也可以看做另一个关键字域）进行排序，每次对数据按一种关键字域进行排序，然后将该轮排序结果按该关键字的大小顺序堆放，依次进行其他关键字域的排序，最后实现序列的整体排序。

限制：基数排序需要一种稳定的排序算法作为子程序（例如：计数排序）。

2.2. 代码示例

2.3. 特性分析

• 时间复杂度：给定n个d位k进制数，使用计数排序（耗时：

）作为子程序，那么时间复杂度为：

，因此，当d为常数，

时，为线性代价；

• 算法稳定性：稳定；