python实现计数排序与桶排序实例代码
作者:sfencs 时间:2023-12-28 11:32:37
计数排序
找到给定序列的最小值与最大值
创建一个长度为最大值-最小值+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计数排序与桶排序详解整合网站的支持!
来源:https://www.cnblogs.com/sfencs-hcy/p/10612422.html
标签:python,计数排序,桶排序
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
JavaScript实现获取select下拉框中第一个值的方法
2024-04-22 12:50:05
![](https://img.aspxhome.com/file/2023/7/136087_0s.png)
谈谈网页设计中的字体应用 (2) serif 和 sans-serif
2009-11-24 13:04:00
![](https://img.aspxhome.com/file/UploadPic/200911/24/202939796-35s.gif)
解决vue脚手架项目打包后路由视图不显示的问题
2024-04-27 16:06:31
Python基于Tkinter实现的垃圾分类答题软件代码
2023-09-09 02:20:24
![](https://img.aspxhome.com/file/2023/0/69490_0s.jpg)
pyCharm 实现关闭代码检查
2023-05-14 18:48:01
![](https://img.aspxhome.com/file/2023/0/123550_0s.jpg)
Python识别快递条形码及Tesseract-OCR使用详解
2022-10-20 01:32:32
![](https://img.aspxhome.com/file/2023/8/125888_0s.jpg)
Python回文字符串及回文数字判定功能示例
2022-05-09 21:59:30
已安装tensorflow-gpu,但keras无法使用GPU加速的解决
2021-08-15 12:17:42
![](https://img.aspxhome.com/file/2023/6/81736_0s.jpg)
深入理解vue中的slot与slot-scope
2024-05-05 09:07:18
![](https://img.aspxhome.com/file/2023/0/130850_0s.png)
实例:用 JavaScript 来操作字符串(一些字符串函数)
2023-06-30 10:02:21
使用pandas模块读取csv文件和excel表格,并用matplotlib画图的方法
2023-10-04 14:42:58
![](https://img.aspxhome.com/file/2023/1/115661_0s.jpg)
js实现浏览器倒计时跳转页面效果
2023-07-18 06:49:57
![](https://img.aspxhome.com/file/2023/5/55915_0s.jpg)
mysql 5.7.18 绿色版下载安装教程
2024-01-20 02:23:30
![](https://img.aspxhome.com/file/2023/0/126320_0s.jpg)
使用Python获取字典键对应值的两种方法
2022-08-04 05:25:16
![](https://img.aspxhome.com/file/2023/7/117267_0s.png)
python爬虫的数据库连接问题【推荐】
2024-01-19 18:26:41
![](https://img.aspxhome.com/file/2023/9/79809_0s.jpg)
带例子详解Sql中Union和Union ALL的区别
2024-01-23 01:45:00
![](https://img.aspxhome.com/file/2023/0/71800_0s.png)
Django中传递参数到URLconf的视图函数中的方法
2021-09-16 23:46:33
Bootstrap 模态对话框只加载一次 remote 数据的完美解决办法
2023-08-06 15:58:18
![](https://img.aspxhome.com/file/2023/0/55970_0s.png)
YOLOv5车牌识别实战教程(六)性能优化与部署
2022-04-26 12:40:54
![](https://img.aspxhome.com/file/2023/3/69573_0s.png)
请问在mssql“SQL事件探查器”里表格的标题,如CPU,Read,Write,Duration,SPID.........的解释
2024-01-20 23:48:30