1、算法步骤

a. 初始化i为0，表示个位排序；n为1，表示最小的位数置1；max_num为待排序数组中的最大值。

b. 计算最大值的位数n。

c. 在每一位上，构建一个桶的字典，每个桶用于存放对应位数的数字。

d. 对待排序数组中的每个元素，根据其在当前位的数字，将其加入到相应位数的桶中。

e. 将桶中的元素依次取出，放回到原数组中，完成对当前位的排序。

f. 重复以上步骤，直到所有位数都进行过排序。

2、动图演示

3、代码

def RadixSort(lst):
    # 初始为个位排序
    i = 0
    # 最小的位数置1（包含0）
    n = 1
    # 得到带排序数据中最大数
    max_num = max(lst)
    # 得到最大数是几位数
    while max_num > 10**n:
        n += 1
    while i < n:
        # 用字典构建桶
        bucket = {}
        for x in range(10):
            # 将每个桶置空
            bucket.setdefault(x, [])
        # 对每一位进行排序
        for x in lst:
            # 得到每位的基数
            radix = int((x / (10**i)) % 10)
            # 将对应的数组元素加入到相应位基数的桶中
            bucket[radix].append(x)
        j = 0
        for k in range(10):
            # 若桶不为空
            if len(bucket[k]) != 0:
                # 将该桶中每个元素
                for y in bucket[k]:
                    # 放回到数据中
                    lst[j] = y
                    j += 1
        i += 1
    return lst

打赏 支付宝打赏 微信打赏