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

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

举例说明

假设待排序数列如下:[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)

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/271