【动手学数据结构—基数排序（Python）】

基数排序

• 原理
• 代码实现

原理

代码实现

import random
def js_sort(li):
    max_num = max(li)
    it = 0  # max_num = 987 (三位数字，3次分桶) -> it=1 -> max_num=98 -> it=2 ->max_num=9 -> it=3 -> max_num=0
    while max_num != 0:
        buckets = [[] for _ in range(10)]  # 建立空的桶
        it += 1
        max_num = max_num // 10
        for value in li:
            last_num = (value // 10**it) % 10 # 如果it=0 代表最后一位分桶，iter=1代表十位分桶
            buckets[last_num].append(value)
        li.clear()  # 将li清楚 把桶里的数放进li里
        for bucket in buckets:
            li.extend(bucket)


Li = [random.randint(0, 300) for _ in range(16)]
print(Li)
js_sort(Li)
print(Li)