基数排序算法

基数排序算法，是在上一个算法桶排序算法的基础上，衍生出的一种改进算法。桶排序算法中，如果数据是稀疏的，或者集中在某几个小范围内，其算法优势会退化。而基数排序算法，正好可以弥补这一缺陷。

实现思路：依次比较各个元素中的个位数字、十位数字和百位数字，每次根据比较结果对所有元素进行升序排序，最终就可以得到一个升序序列。

举例说明

假设待排序数列如下：[121, 432, 562, 23, 1, 45, 788]

1）个位排序，可以看做按个位数，将数据放入 0-9 十个桶内；

[121, 1, 432, 562, 23, 45, 788]

2）十位排序，不够的补0

[1, 121, 23, 432, 45, 562, 788]

3) 百位排序

[1, 23, 45, 121, 432, 562, 788]

代码示例

def radix_sort(arr):
    max_num = max(arr)  # 找到最大的数
    for i in range(0, len(str(max_num))):
        # 创建10个桶
        buckets = [[] for i in range(10)]
        for j in arr:
            idx = j // 10**i % 10
            buckets[idx].append(j)
        arr.clear()
        # 桶解包并覆盖原arr
        arr.extend([b for bucket in buckets for b in bucket])

lst = [121, 432, 562, 23, 1, 45, 788]
radix_sort(lst)