文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

python之基数排序的实现

2024-04-02 19:55

关注

算法思想

        插入\交换\选择\归并类的排序算法都需要通过比较关键字的大小来完成排序.因为存在两两比较所以这一类的排序方法在最好情况下能达到的复杂度是O(n*logn),如快速排序\堆排序\归并排序.在一般情况下和最坏情况下复杂度更是达到O(n**2).

        为了降低复杂度,就有牛人想出了分配收集排序方法,稍后分析它的时间复杂度能到达O(n),

而基数排序就是一种典型的搜集分配收集排序方法.基数排序时一种借助于多关键字排序的思想对单关键字排序的方法.其基本思想是通过对排序记录进行若干趟(有几个关键字就几趟)"分配"与"收集"来实现排序.

        如:

       1. 对整数排序,建立编号0-9(10进制的基数)10个桶,用于装对应位为编号的记录.先将待排序序列分配按'个位'数字分配到10各桶中,然后将桶按从小到大的顺序串接起来.

        2.将上一步的结果再按'十位''数字分配到10各桶中,然后将桶按从小到大的顺序串接起来.

        3. 将上一步的结果再按'百位''数字分配到10各桶中,然后将桶按从小到大的顺序串接起来.

        4.如果还有千位\万位.重复以上步骤,直到完成最高位的分配与收集,排序结束.

动图示例:(转自菜鸟教程:1.10 基数排序 | 菜鸟教程 (runoob.com))

 

算法实现

1.本实现借助队列的数据结构,所以先来定义一个队列


# Bradley N. Miller, David L. Ranum
# Introduction to Data Structures and Algorithms in Python
# Copyright 2005
# 
#queue.py
 
class Queue:
    def __init__(self):
        self.items = []
 
    def isEmpty(self):
        return self.items == []
 
    def enqueue(self, item):
        self.items.insert(0,item)
 
    def dequeue(self):
        return self.items.pop()
 
    def size(self):
        return len(self.items)

2.处理输入数据

将一个列表作为输入,将每一个记录处理为具有相同位数的字符串(用字符串类型时为了方便处理)


def inDataProcess(lis):
    max_lengh = max([len(lis[i]) for i in range(len(lis))])  # 查询记录中最长的字符串
    return [x.zfill(max_lengh) for x in lis]  # 将每一个记录都通过添加前导0的方式转化为一样的长度

3.基数排序主函数


def radixSort(seq:list):
    source_data = inDataProcess(seq)  # 输入处理
    res = []  # 用于保存结果列表
    big_queue = Queue()  # 用于转化的队列
    for ele in source_data:
        big_queue.enqueue(ele)
 
    for i in range(len(source_data[0])-1,-1,-1):
        buckets = []  # 用于保存每一趟的10各基数桶
        for num  in range(10):  # 建立10个基数桶
            bucket = Queue()
            buckets.append(bucket)
        # 在基数桶中插入数据
        while not big_queue.isEmpty():
            currentEle = big_queue.dequeue()  # 大队列中出队一个元素
            index = int(currentEle[i])  # 根据元素对应位上的值添加进对应的基数桶中
            buckets[index].enqueue(currentEle)
 
        # 把基数桶串联起来
        new_big_queue = Queue()
        for bucket in buckets:
            while not bucket.isEmpty():
                out = bucket.dequeue()
                new_big_queue.enqueue(out)
                # print(new_big_queue.size())
        # 修改big_queue
        big_queue = new_big_queue
    # 将大队列中的元素保存到结果列表中
    while not big_queue.isEmpty():
        res.append(big_queue.dequeue().lstrip('0'))  # 利用lstrip('0')去掉前导0
    return res

4.测试及结果


if __name__ == '__main__':
 
    lis = [20,101,39,431,58,600,8,4,999,634,157,199,208,138,389,691,400,932,856,843,401,923]
    lis = [str(i) for i in lis]
    print(radixSort(lis))
    ''' 结果>>>['4', '8', '20', '39', '58', '101', '138', '157', '199', '208', '389', '400', '401', '431', '600', '634', '691',
    '843', '856', '923', '932', '999']'''

算法分析

1)时间复杂度
对于n个记录(假设每个记录含d个关键字,每个关键字的取值范围为rd个值)进行链式基数排序时,每一趟分配的时间复杂度为O(n),每一趟收集的时间复杂度为O(rd),整个排序需进行d趟分配和收集,所以时间复杂度为O(d(n+rd))。
(2)空间复杂度
所需辅助空间为2rd个队列指针,另外由于需用链表做存储结构,则相对于其他以顺序结构存储记录的排序方法而言,还增加了n个指针域的空间,所以空间复杂度为O(n+rd)。

算法的特征

(1)是稳定排序。
(2)可用于链式结构,也可用于顺序结构。
(3)时间复杂度可以突破基于关键字比较一类方法的下界O(nlog2n),达到O(n)。
(4)基数排序使用条件有严格的要求:需要知道各级关键字的主次关系和各级关键字的取值范围。


ref: 

1.严蔚敏等<<数据结构C语言版(第二版)>>

2.Bradley N. Miller, David L. Ranum <<Introduction to Data Structures and Algorithms in Python>>

到此这篇关于python之基数排序的实现的文章就介绍到这了,更多相关python之基数排序内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯