摘要
基数排序是把待排序数组按照位上的数值进行分类，我们知道阿拉伯数字由 0-9 组成，可以按照不同位进行分类，因为 0-9 是有序的，所以最后每一位都分类之后再按照 0-9 的顺序拾起来，就是一个有序数组了（我们这里只讨论大于等于 0 的整数数组，基数排序其实不是只能使用于整数）。
图示
图片来源：菜鸟教程
从图中可以看到，数组中最大数的位数，就是需要分类的次数。原理是每次分类都是把这位上值相同的数字集中在一起，然后通过比当前位高一位的值大小来确定顺序（因为高一位也会进行一次分类）。
实现:
def radix_sort(data):
"""data必须是不为空的数组，且数组内是数字，数字大于等于0"""
# 待排序数组中最大数的位数，比如 1024 则 max_bit_count = 4
max_bit_count = len(str(max(data)))
for i in range(max_bit_count): # 循环位数次
# 基数队列 对应 图示中下方的 0 - 9
radix_queue = [list() for _ in range(10)]
for d in data:
str_num = str(d) # 把数字转换成字符串
if len(str_num) > i: # 这两行是用来取当前位的数值
radix = int(str_num[len(str_num)-i-1])
else:
radix = 0 # 位数不够了，分到 0 类
radix_queue[radix].append(d) # 归到对应类
position = 0 # 待排序位置索引
for queue in radix_queue:
for val in queue:
data[position] = val
position += 1
return data在实际项目中，如果对效率有所要求，而不太关心空间的使用时，可以选择用基数排序，或者是基数排序的变种。
性能：
假设最大数是 99884，那么一定会循环 5 次O(n)，只考虑自然数的情况，基数只有 0-9 为 10 个。通过代码分析可以看到没有提前结束的情况，所以该算法的最好、最坏、平均时间复杂度均为
令 d 为最大数字的位数，r 为基数个数，那么时间复杂度是：
。