数据结构算法--8基数排序

@小森

发布于 2024-03-15 10:29:19

10100

代码可运行

文章被收录于专栏：xiaosenxiaosen

运行总次数：0

代码可运行

> 多关键字排序：现在有一个员工表，要求按照薪资排序，薪资相同的员工按照年龄排序

>> 先按照年龄排序，再按照薪资进行稳定的排序

> 例如：32，13，94，52，17，54，93排序，也可以看成多关键字排序

对于这样的数组，我们可以先按个位数分桶，保证是稳定的排序。

得到：32，52，13，93，94，54，17 *现在个位数的相对位置排好序了*

再按照十位数排序：

然后将每个桶里的数拿出来：

13，17，32，52，54，93，94 * 得到了最终的有序数组*

代码部分：

def radix_sort(li):
    max_num=max(li)
    it=0
    while 10**it <=max_num:
        buckets=[[] for _ in range(10)]
        for val in li:
            digit=(val//10**it)%10        # 每次都保证后几位的相对位置不变
            buckets[digit].append(val)
        # 分桶完成
        li.clear()
        for buc in buckets:
            li.extend(buc)
        # 把数重新写回li
        it+=1

import random
li=list(range(100))
random.shuffle(li)
radix_sort(li)
print(li)

可以看出基数排序的时间复杂度为：O(kn)

空间复杂度为：O(k+n)

k表示数字位数

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-12-28，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构