基数排序（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
