八大排序算法之基数排序(python实现)
【写在前面】
参考文章:
https://blog.csdn.net/nrsc272420199/article/details/82691596【给出的示例图,简单易懂,但是对于没一轮循环没有讲解的很清楚】
https://www.cnblogs.com/sfencs-hcy/p/10616446.html【代码实现+思路,值得借鉴】
【正文部分】
网上有很多关于基数排序的讲解,不过基于每个人的理解力不同,所以理解起来难易程度也有所不同。大家给出的博客、见解很多,不过我找了好久要么就是程序实现的思路,晦涩难懂,要么就是图示复杂难看(没有贬义,不是丑,是不容易看懂的意思),找了好久找到上面推荐的两篇博客,结合两个博主的例子写了这篇博客。好了,下面开始正式的讲解。
基数排序的原理就是按照将每个元素的从低到高的顺序依次取出各位上的元素,然后每次按照取出的元素进行归类和重整。直到所有的位数都排完。简单的将就是先拆分后整合。借鉴文章1给出的例子,原始数组如下所示:
第一趟排序,先取出各个元素的个位数字,并进行分组如下:
然后按照每组中的数字添加的顺序对数据进行整合,先进先出,得到新的数组如下,第一趟排序后完成的工作为将数组按照个位数由小到大的顺序进行了排序。
第二趟,对第一趟的结果按照十位数进行分组,结果如下:
同样的方法,将分组后的数组按照添加的顺序分别取出,得到新的数组如下:
第二趟排序后,数组按照十位数由小到大进行了排序,同时由于个位数已经进行了排序,因此将分组后的数组添加顺序取出时,十位数相同的较小的会排在前面,如31和38,43和49
第三趟,对第二趟的结果按照百位数进行分组,结果如下:
然后将分组后的数组按照索引的大小分别取出,得到新的数组如下:
第三趟排序后完成的工作是将数组按照百位数由小到大进行了排序,同时由于个位数和十位数都已经进行了排序,所以较小的数会排在前面,这样就完成了整个数组的排序.
由上面的过程可以知道如果最大数有n位,则需要n次(按照索引分组+按照索引大小取出数据)循环。所以程序中需要先找出最大数字和最大数字的位数。
具体实现:
def radix_sort(s):
"""基数排序"""
i = 0 # 记录当前正在排拿一位,最低位为1
max_num = max(s) # 最大值
j = len(str(max_num)) # 记录最大值的位数
while i < j:
bucket_list =[[] for _ in range(10)] #初始化桶数组
for x in s:
bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶数组
print(bucket_list)
s.clear()
for x in bucket_list: # 放回原序列
for y in x:
s.append(y)
i += 1 if __name__ == '__main__':
a = [334,5,67,345,7,345345,99,4,23,78,45,1,3453,23424]
radix_sort(a)
print(a)
输出结果:
[[], [1], [], [23, 3453], [334, 4, 23424], [5, 345, 345345, 45], [], [67, 7], [78], [99]]
[[1, 4, 5, 7], [], [23, 23424], [334], [345, 345345, 45], [3453], [67], [78], [], [99]]
[[1, 4, 5, 7, 23, 45, 67, 78, 99], [], [], [334, 345, 345345], [23424, 3453], [], [], [], [], []]
[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345], [], [], [23424, 3453], [], [345345], [], [], [], []]
[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453], [], [23424], [], [345345], [], [], [], [], []]
[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424], [], [], [345345], [], [], [], [], [], []]
[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424, 345345]
备注:这里贴出文章2中给出的参考代码,这里有一点原博主做的很好,在每一次循环的时候给了一个print函数,可以方便的看出每一轮循环中桶中的数据分布情况。
原博主在求最大值和最大值的位数的时候用了库函数来实现,方法很好,代码看起来很简洁,不过为了更易懂,或者有时候如果有限制不让用库函数的时候,直接给出一个自定义函数求取参数,另外对响应的代码作出了注释,代码如下所示:
def radix_sort(s):
"""基数排序代码实现"""
maxNum = s[0] # 求取的最大值
for x in s:
if maxNum < x:
maxNum = x
times = 0 # 循环实现的次数
while maxNum > 0:
maxNum = maxNum//10
times = times+1 i = 0 # 记录当前正在排拿一位,最低位为0
while i < times:
bucket_list = [[] for _ in range(10)] # 初始化桶数组为十个空列表
for each in s:
bucket_list[(each // (10**i)) % 10].append(each) # 根据当前所求的位的数值大小,找到对应的位置放入桶数组
s.clear()
for x in bucket_list: # for的嵌套,从桶中取出元素放回原序列
for y in x:
s.append(y)
i += 1 if __name__ == '__main__':
a = [334,5,67,345,7,345345,99,4,23,78,45,1,3453,234]
radix_sort(a)
print(a)
显然易见,没有了库函数的加持,代码显得很臃肿。。。。
【写在最后】
该文章是参考上面两个博主的博客写的,也加上了自己的看法和理解,如果有没讲到位的地方,可以去原博客查看。
博主支持原创,也尊重原创,如有侵权,联系博主删帖,转发注明出处。
最新文章
- sha512散列(C语言)
- Android LayoutInflater原理分析,带你一步步深入了解View(一)
- PHP 用html方式输出Excel文件时的数据格式设置
- [2013 Final] Colors
- ffmpeg安装的问题
- FPGA学习
- Python 批量创建同文件名的特定后缀文件
- CS 和 BS 的区别和优缺点
- hadoop实现共同出现的单词(Word co-occurrence)
- Linux编程之有限状态机FSM的理解与实现
- linux基本语法和常用运维命令
- bzoj3156防御准备 斜率优化dp
- iOS下JS与OC互相调用(一)--UIWebView 拦截URL
- C#一句话判断两个List<;T>;是否相等
- 【细语】C#之扩展方法原理及其使用
- 348. Design Tic-Tac-Toe设计井字游戏
- DIV内容超出长度显示省略号,鼠标移上自动显示全部内容(EasyUI DataGrid)
- 常见的ORACLE语句
- javascript 日常
- VMware 15 安装 MAC OS 10.13 原版(详细图文教程)
热门文章
- 基于Linux系统的网络服务——高速缓存DNS及企业级域名解析服务
- Disable_functions绕过整合
- dotnet C# 给结构体字段赋值非线程安全
- 【曹工杂谈】Maven和Tomcat能有啥联系呢,都穿打补丁的衣服吗
- Python - 面向对象编程 - self 参数
- Element UI:级联选择器Cascader_动态加载_多级请求不同接口(已知第一级调取第二级)
- JS014. toFixed( )调试踩坑 - 浏览器思维 点常量 &; 点运算符
- vue+element+echarts柱状图+列表
- 硕盟type-c转接头HDMI+VGA+USB3.0+PD3.0四合一多功能扩展坞
- 查看elasticsearch版本的方法