Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序
本篇章节讲解Python数据结构与算法之常见的分配排序法。分享给大家供大家参考,具体如下: 箱排序(桶排序) 箱排序是根据关键字的取值范围1~m,预先建立m个箱子,箱排序要求关键字类型为有限类型,可能会有无限个箱子,实用价值不大,一般用于基数排序的中间过程。 桶排序是箱排序的实用化变种,其对数据集的范围,如[0,1) 进行划分为n个大小相同的子区间,每一个子区间为一个桶,然后将n非记录分配到各桶中。因为关键字序列是均匀分布在[0,1)上的,所以一般不会有很多记录落入同一个桶中。 以下的桶排序方法采用字典实现,所以对于整数类型,并不需要建立多余空间 def BuckSort(A): bucks = dict() # 桶 for i in A: bucks.setdefault(i,[]) # 每个桶默认为空列表 bucks[i].append(i) # 往对应的桶中添加元素 A_sort = [] for i in range(min(A),max(A)+1): if i in bucks: # 检查是否存在对应数字的桶 A_sort.extend(bucks[i]) # 合并桶中数据 return A_sort 基数排序 # 基数排序 # 输入:待排序数组s,keysize关键字位数,亦即装箱次数,radix基数 def RadixSort(s,keysize=4,radix=10): # 按关键字的第k分量进行分配 k = 4,3,2,1 def distribute(s,k): box = {r:[] for r in range(radix)} # 分配用的空箱子 for item in s: # 依次扫描s[],将其装箱 t = item t /= 10**(k-1) t %= 10 # 去关键字第k位 box[t].append(item) return box # 按分配结果重新排列数据 def collect(s,box): a = 0 for i in range(radix): s[a:a + len(box[i])] = box[i][:] # 将箱子中元素的合并,覆盖到原来的数组中 a += len(box[i]) # 增加偏移值 # 核心算法 for k in range(1,keysize+1): box = distribute(s,k) # 按基数分配 collect(s,box) # 按分配结果拼合 以下摘自:《数据结构与算法――理论与实践》 基数排序可以拓展为按多关键字排序,如对扑克牌按花色、按点数排序。 MSD: 先按k1排序分组,同一组的个元素,若关键字k1相等,再对各组按k2排序分成子组,依次类推,直到最次位kd对各子组排序后,再将各组链接起来。 LSD: 与MSD相反,先按kd排序,再对kd-1排序,依次类推。 PS:这里再为大家推荐一款关于排序的演示工具供大家参考: 在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具: 更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》 希望本文所述对大家Python程序设计有所帮助。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- 我可以将类方法和默认参数传递给另一个类方法
- python – 具有浮点形式输入的django整数模型字段
- python-2.7 – 升级到ubuntu-16.10后,Pip不起作用
- python – Cherrypy返回NotFound:(404,“未找到路径’/’
- 4.93Python数据类型之(8)集合
- 关于python中的for循环的问题
- python – TensorFlow中的硬限制/阈值激活功能
- 按字典顺序在Python 3中对嵌套的混合数据类型列表进行排序
- python – 在Tensorflow Object Detection API中打印类名和
- 爬取豆瓣的各分类书单以及近期热门电影和top250的电影