首页 / 算法 / 常见排序算法-基数排序、计数排序
常见排序算法-基数排序、计数排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了常见排序算法-基数排序、计数排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1238字,纯文字阅读大概需要2分钟。
内容图文
![常见排序算法-基数排序、计数排序](/upload/InfoBanner/zyjiaocheng/1304/0d7a3e0b272845dc9995bbde28c67716.jpg)
基数排序(桶排序):
设置若干个箱子,将关键字为k的记录放入第k个箱子中,然后按序号将非空的连接。而数字是有范围的,若待排元素均由0-9这十个数字组成,则只需设置十个箱子,相继按个、十、百...进行排序
平均,最坏时间复杂度 O(k*(n+m)) k是关键字的个数,如个位、十位分别就是关键字;n是元素的个数,m是桶的个数。最好时间复杂度 O(n+m),一次分配就搞定!
import math def radix_sort(lists, radix=10): k = int(math.ceil(math.log(max(lists), radix))) #找到最高位的数字。这的确是个好办法 bucket = [[] for i in range(radix)] #bucket是一个有十个空列表元素的列表 for i in range(k): for j in lists: bucket[j//(10**i)%10].append(j) #从高到低依次找出该数每一位的数值 del lists[:] for z in bucket: if len(z): lists += z #等效于lists.append(z[0]) del z[:] return lists
计数排序
基本思想:用待排序的数作为计数数组的下标,统计每个数字的个数。然后依次输出,即可得到有序序列。
适用范围:数据量大范围小
def countSort(arr): # 1.计算数列的最大值与最小值,从而得到计数数组的长度 length=max(arr)-min(arr)+1 busket=[0 for i in range(length)] sortarr=[0 for i in range(len(arr))] #2.busket统计数组用来统计数组个数 for i in arr: busket[i-min(arr)]+=1 #3.统计数组变形,后面元素等于前面元素之和 sum1=0 for j in range(length): sum1+=busket[j] busket[j]=sum1 #4.倒序遍历原始数组,从统计数组找到正确位置,输出结果数组 for k in arr[::-1]: sortarr[busket[k-min(arr)]-1]=k busket[k-min(arr)]-=1 return sortarr if __name__==‘__main__‘: a=[4,3,2,5,1,3] sort_a=countSort(a) print(sort_a)
小结:基数和计数排序都不是基于比较交换的算法,属于线性时间复杂度,但需要一定的辅助空间。对排序的元素也有要求,适合量大数据范围有限的数据,如公司员工的年龄。
原文:https://www.cnblogs.com/wanrongshu/p/12731240.html
内容总结
以上是互联网集市为您收集整理的常见排序算法-基数排序、计数排序全部内容,希望文章能够帮你解决常见排序算法-基数排序、计数排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。