不为成仙,只为在这红尘中等你回来。

您现在的位置是:网站首页>>算法与数据结构

基数排序

2020年11月7日 15:15 | 分类:算法与数据结构 | 标签: Python

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

  • 时间复杂度:O(kn)
  • 空间复杂度:O(k+n)
  • k 表示数字位数

基数排序图解

def radix_sort(lst):
    max_num = max(lst)
    it = 0  # 最大值 9->1, 99->2, 888->3, 10000->5
    while 10 ** it <= max_num:
        buckets = [[] for _ in range(10)]
        # 分桶
        for var in lst:
            digit = (var // 10 ** it) % 10
            buckets[digit].append(var)
        # 把数据写回列表
        lst.clear()
        for buc in buckets:
            lst.extend(buc)
        it += 1