黑松山资源网 Design By www.paidiu.com
计数排序
- 找到给定序列的最小值与最大值
- 创建一个长度为最大值-最小值+1的数组,初始化都为0
- 然后遍历原序列,并为数组中索引为当前值-最小值的值+1
- 此时数组中已经记录好每个值的数量,自然也就是有序的了
例如:
计数排序实现
下面为列表的计数排序
def count_sort(s): """计数排序""" # 找到最大最小值 min_num = min(s) max_num = max(s) # 计数列表 count_list = [0]*(max_num-min_num+1) # 计数 for i in s: count_list[i-min_num] += 1 s.clear() # 填回 for ind,i in enumerate(count_list): while i != 0: s.append(ind+min_num) i -= 1 if __name__ == '__main__': a = [3,6,8,4,2,6,7,3] count_sort(a) print(a)
计数排序的缺点
当数值中有非整数时,计数数组的索引无法分配
桶排序
桶排序原理:
- 桶排序与计数排序类似,但可以解决非整数的排序
- 桶排序相当于把计数数组划分为按顺序的几个部分
- 每一部分叫做一个桶,它来存放处于该范围内的数
- 然后再对每个桶内部进行排序,可以使用其他排序方法如快速排序
- 最后整个桶数组就是排列好的数据,再将其返回给原序列
举例:
桶排序实现
这里选择桶的数量为序列元素个数+1,范围分别是5等分与最大值,和上面那个图一样。
具体问题应该按照具体情况进行桶划分
这里桶内部排序直接调用了sorted
def bucket_sort(s): """桶排序""" min_num = min(s) max_num = max(s) # 桶的大小 bucket_range = (max_num-min_num) / len(s) # 桶数组 count_list = [ [] for i in range(len(s) + 1)] # 向桶数组填数 for i in s: count_list[int((i-min_num)//bucket_range)].append(i) s.clear() # 回填,这里桶内部排序直接调用了sorted for i in count_list: for j in sorted(i): s.append(j) if __name__ == '__main__': a = [3.2,6,8,4,2,6,7,3] bucket_sort(a) print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]
总结
计数排序与桶排序都是以牺牲空间换时间,虽然很快,但由于可能产生大量的空位置导致内存增大,尤其是计数排序。
桶排序中尽量使每个桶中的元素个数均匀分布最好
以上所述是小编给大家介绍的python计数排序与桶排序详解整合,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对网站的支持!
黑松山资源网 Design By www.paidiu.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
黑松山资源网 Design By www.paidiu.com
暂无评论...
更新日志
2024年10月07日
2024年10月07日
- 班得瑞原装进口《第五张新世纪专辑:迷雾森林+EP》1CD[APE/CUE分轨][334.2MB]
- 田震.1997-顺其自然(日版)【红星生产社】【WAV+CUE】
- 小虫.1996-想得太美【滚石】【WAV+CUE】
- 谢采妘.2016-邓丽君名曲专辑【丰荣】【WAV+CUE】
- 张含韵.2007-一人一梦【天中文化】【WAV+CUE】
- 蟑螂乐队.1999-帮个忙【福茂】【WAV+CUE】
- 张宇.2001-替身【EMI百代】【WAV+CUE】
- 班得瑞原装进口《第六张新世纪专辑:日光海岸》1CD[APE/CUE分轨][339.5MB]
- 班得瑞原装进口《第七张新世纪专辑:梦花园》1CD[APE/CUE分轨][331.4MB]
- 班得瑞原装进口《第八张新世纪专辑:琉璃湖畔》1CD[APE/CUE分轨][286.4MB]
- 魏如萱.2011-在哪里(EP)【添翼创越】【WAV+CUE】
- 群星.1981-新金曲奖·青年创作园地12合辑(喜玛拉雅复刻版)【歌林】【WAV+CUE】
- 麦洁文.1989-新曲与精丫新艺宝】【WAV+CUE】
- SNH48《薄荷糖 (Mint Candy)》[320K/MP3][33.72MB]
- SNH48《薄荷糖 (Mint Candy)》[FLAC/分轨][78.59MB]