• 售前

  • 售后

热门帖子
入门百科

python之基数排序的实现

[复制链接]
六翼天使494 显示全部楼层 发表于 2021-8-14 13:42:42 |阅读模式 打印 上一主题 下一主题
                                    算法思想

        插入\互换\选择\归并类的排序算法都须要通过比较关键字的巨细来完成排序.因为存在两两比较以是这一类的排序方法在最好环境下能到达的复杂度是O(n*logn),如快速排序\堆排序\归并排序.在一般环境下和最坏环境下复杂度更是到达O(n**2).
        为了低落复杂度,就有牛人想出了分配网络排序方法,稍后分析它的时间复杂度能到达O(n),
而基数排序就是一种范例的搜集分配网络排序方法.基数排序时一种借助于多关键字排序的思想对单关键字排序的方法.其基本思想是通过对排序记载进行多少趟(有几个关键字就几趟)"分配"与"网络"来实现排序.
        如:
       1. 对整数排序,创建编号0-9(10进制的基数)10个桶,用于装对应位为编号的记载.先将待排序序列分配按'个位'数字分配到10各桶中,然后将桶按从小到大的次序串接起来.
        2.将上一步的效果再按'十位''数字分配到10各桶中,然后将桶按从小到大的次序串接起来.
        3. 将上一步的效果再按'百位''数字分配到10各桶中,然后将桶按从小到大的次序串接起来.
        4.假如另有千位\万位.重复以上步调,直到完成最高位的分配与网络,排序竣事.
动图示例:(转自菜鸟教程:1.10 基数排序 | 菜鸟教程 (runoob.com))
 

算法实现

1.本实现借助队列的数据结构,以是先来定义一个队列
  1. # Bradley N. Miller, David L. Ranum
  2. # Introduction to Data Structures and Algorithms in Python
  3. # Copyright 2005
  4. #
  5. #queue.py
  6. class Queue:
  7.     def __init__(self):
  8.         self.items = []
  9.     def isEmpty(self):
  10.         return self.items == []
  11.     def enqueue(self, item):
  12.         self.items.insert(0,item)
  13.     def dequeue(self):
  14.         return self.items.pop()
  15.     def size(self):
  16.         return len(self.items)
复制代码
2.处置惩罚输入数据

将一个列表作为输入,将每一个记载处置惩罚为具有类似位数的字符串(用字符串类型时为了方便处置惩罚)
  1. def inDataProcess(lis):
  2.     max_lengh = max([len(lis[i]) for i in range(len(lis))])  # 查询记录中最长的字符串
  3.     return [x.zfill(max_lengh) for x in lis]  # 将每一个记录都通过添加前导0的方式转化为一样的长度
复制代码
3.基数排序主函数
  1. def radixSort(seq:list):
  2.     source_data = inDataProcess(seq)  # 输入处理
  3.     res = []  # 用于保存结果列表
  4.     big_queue = Queue()  # 用于转化的队列
  5.     for ele in source_data:
  6.         big_queue.enqueue(ele)
  7.     for i in range(len(source_data[0])-1,-1,-1):
  8.         buckets = []  # 用于保存每一趟的10各基数桶
  9.         for num  in range(10):  # 建立10个基数桶
  10.             bucket = Queue()
  11.             buckets.append(bucket)
  12.         # 在基数桶中插入数据
  13.         while not big_queue.isEmpty():
  14.             currentEle = big_queue.dequeue()  # 大队列中出队一个元素
  15.             index = int(currentEle[i])  # 根据元素对应位上的值添加进对应的基数桶中
  16.             buckets[index].enqueue(currentEle)
  17.         # 把基数桶串联起来
  18.         new_big_queue = Queue()
  19.         for bucket in buckets:
  20.             while not bucket.isEmpty():
  21.                 out = bucket.dequeue()
  22.                 new_big_queue.enqueue(out)
  23.                 # print(new_big_queue.size())
  24.         # 修改big_queue
  25.         big_queue = new_big_queue
  26.     # 将大队列中的元素保存到结果列表中
  27.     while not big_queue.isEmpty():
  28.         res.append(big_queue.dequeue().lstrip('0'))  # 利用lstrip('0')去掉前导0
  29.     return res
复制代码
4.测试及效果
  1. if __name__ == '__main__':
  2.     lis = [20,101,39,431,58,600,8,4,999,634,157,199,208,138,389,691,400,932,856,843,401,923]
  3.     lis = [str(i) for i in lis]
  4.     print(radixSort(lis))
  5.     ''' 结果>>>['4', '8', '20', '39', '58', '101', '138', '157', '199', '208', '389', '400', '401', '431', '600', '634', '691',
  6.     '843', '856', '923', '932', '999']'''
复制代码
算法分析
  1. 1)时间复杂度
  2. 对于n个记录(假设每个记录含d个关键字,每个关键字的取值范围为rd个值)进行链式基数排序时,每一趟分配的时间复杂度为O(n),每一趟收集的时间复杂度为O(rd),整个排序需进行d趟分配和收集,所以时间复杂度为O(d(n+rd))。
  3. (2)空间复杂度
  4. 所需辅助空间为2rd个队列指针,另外由于需用链表做存储结构,则相对于其他以顺序结构存储记录的排序方法而言,还增加了n个指针域的空间,所以空间复杂度为O(n+rd)。
复制代码
算法的特性
  1. (1)是稳定排序。
  2. (2)可用于链式结构,也可用于顺序结构。
  3. (3)时间复杂度可以突破基于关键字比较一类方法的下界O(nlog2n),达到O(n)。
  4. (4)基数排序使用条件有严格的要求:需要知道各级关键字的主次关系和各级关键字的取值范围。
复制代码

ref: 

1.严蔚敏等<<数据结构C语言版(第二版)>>
2.Bradley N. Miller, David L. Ranum <<Introduction to Data Structures and Algorithms in Python>>
到此这篇关于python之基数排序的实现的文章就介绍到这了,更多相关python之基数排序内容请搜索草根技能分享从前的文章或继承欣赏下面的相关文章希望各人以后多多支持草根技能分享!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作