终于来到了八大排序的收尾之作~基数排序！之前补充了快排和堆排序的代码与总结，不要忘记补课哦~
基数排序（Radix Sort）
算法思想
基数排序的原理相对于其它方法来说，比较新颖有趣。它将数字按照位数(个十百)切分，然后按每个位数分别比较。对于数字长度不一致情况，将高位（前面）补零。该方法为最低位优先法LSD(Least sgnificant digital)。
举个例子：随机生成一个array: [23, 34, 38, 17, 16, 26, 12, 26, 14, 43]
从0-9，一共10个桶，首先，从左到右，按照个位把它们放到对应桶里：
0:
1:
2: 12
3: 23,43
4: 34,14
5:
6: 16,26,26
7: 17
8: 38
9: 然后把这些数字串起来：[12,23,43,34,14,16,26,26,17,38]
根据串起来后的顺序，按照十位把它们放到对应桶里：
0:
1: 12,14,16,17
2: 23,26,26
3: 34,38
4:43
5:
6:
7:
8:
9:然后把这些数字串起来：[12,14,16,17,23,26,26,34,38,43]
由于数字最大只到十位，所以到此完成排序。
动图示例来自网络。
算法步骤
LSD基数排序
- 统计数字最大位数，将不满最大位数的数字高位补0；
- 从最低位开始，根据位数数字，将对应元素分配至对应桶中；
- 从0-9，串起桶中数字，形成新序列；
- 位数前进一位，根据新序列继续排序，直到遍历结束最高位，结束。
代码实现
def Radix_Sort(array):
i = 0 # 当前位数
max_len = len(str(max(array)))
while i < max_len:
bucket_list =[[] for x in range(10)]
for x in array:
bucket_list[int(x / (10**i)) % 10].append(x) # 把数字放到对应桶
print(bucket_list)
array.clear()
for x in bucket_list: # 再串起来
for y in x:
array.append(y)
i += 1
改进思路
经典LSD默认基数为10，就是从个位十位依次往上数。但是当数字范围跨度很大得时候，会增大复杂度。这个时候可以选择较大的基数，效果更好。
总结
基数排序时间复杂度为
- 这个比较好理解，对每一趟排序，都需要遍历待排序序列每个数字，放到桶中。而一共需要经历k趟排序；
- 这也和选的基数大小有关。
基数排序空间复杂度为 ：
- 这里也比较好理解，创建了k个临时桶，用于存放n个元素。
由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
下期考虑补充一下计数排序和桶排序~ 然后更新一下排序算法合集，有兴趣的同学可以继续关注哦！下期再见！
