小编点评

**博客地址:** https://www.cnblogs.com/zylyehuo/# -*- coding: utf-8 -*-# O(n) O(kn)# NB O(nlogn) **算法介绍:** 算法的目的是对一个数字列表进行降序排序。降序排序是指将数字列表中数字按从小到大排序。 **步骤:** 1. **找出最大值:** 算法首先找到输入列表中的最大值作为排序标准。 2. **初始化桶存储器:** 创建一个大小为 10 的数组，其中每个元素代表一个桶，用于存储和分组数字。 3. **将数字分配到桶中:** 遍历输入列表，对每个数字计算其十进制值。将该值与桶对应的位置插入相应的桶中。 4. **合并桶：** 将所有桶中的数字合并回输入列表中。 5. **重新排序列表:** 最后，将输入列表重新排序以实现降序排序。 **时间复杂度:** * 时间复杂度为 O(n)，其中 n 是输入列表的大小。这是因为算法中循环遍历输入列表，并为每个数字找到其桶位置。 * 时间复杂度为 O(kn)，其中 k 是桶的大小。这是因为算法中创建和初始化桶需要 O(k) 的时间。 **其他说明:** * 算法使用了 bucket sort 的思想，该是一种将数字分组并排序的技术。 * 每个桶可以存储最多 10 个数字。 * 算法使用随机排序算法对输入列表进行排序。

正文

博客地址：https://www.cnblogs.com/zylyehuo/

# -*- coding: utf-8 -*-

# O(n) O(kn)
# NB O(nlogn)
import random


def radix_sort(li):
    max_num = max(li)  # 最大值 9->1, 99->2, 888->3, 10000->5
    it = 0
    while 10 ** it <= max_num:
        buckets = [[] for _ in range(10)]
        for var in li:
            # 987 it=1  987//10->98 98%10->8;    it=2  987//100->9 9%10=9
            digit = (var // 10 ** it) % 10
            buckets[digit].append(var)
        # 分桶完成
        li.clear()
        for buc in buckets:
            li.extend(buc)
        # 把数重新写回li
        it += 1


li = [random.randint(0, 10) for _ in range(10)]
random.shuffle(li)
print(li)

radix_sort(li)
print(li)