数据结构与算法（第二季）：基数排序（Radix Sort）

基数排序（Radix Sort）

一、概念

• 基数排序非常适合于整数排序，尤其是非负整数。
• 执行流程：依次对个位数，十位数，百位数，千位数，万位数...进行排序（从低到高位）。
• 没有十位数或没有百位数的，当作0处理。

image

• 个位数，十位数，百位数的取值范围都是固定的0-9，可以使用计数排序对它们进行排序。

二、代码实现

1、常规实现

• 基数排序：

image

• 计数排序：

image

• 最好，最坏，平均时间复杂度：O(d * (n + k))，d是最大值的位数，k是进制。属于稳定排序。
• 空间复杂度：O(n + k)，k是进制。

2、另一种思路

• 首先获取一个数组，将这个数组依据其个位数大小，存放在一个二维数组中。

image

• 按顺序将二维数组中的值存放在新的数组中。

image

• 其结果相当于对个位数进行了一次排序。
• 重复上面的操作，对数组元素的十位数，百位数进行排序。

image image

• 总使用空间：10 * n，n代表元素个数。
• 该方法空间复杂度更高，是O(kn + k)，时间复杂度是O(dn)。
• 代码实现如下：

image