CSDN话题挑战赛第2期
参赛话题：学习笔记
执行流程图
根据数组的最大值与最小值申请一些桶
将数组的元素放入到桶中，并保证桶里是有序的
最后合并每一个桶
代码实现
def bucketSort(nums,size=5):
#根据数组的最大值和最小值确定申请的桶的数量
maxVal=max(nums) #数组的最大值
minVal=min(nums) #数组的最小值
bucketCount=(maxVal-minVal)//5+1 #桶的数量
buckets=[[] for _ in range(bucketCount)] #申请桶
for num in nums:
idx=(num-minVal)//size #得到num在那个桶中，索引为idx
n=len(buckets[idx]) #求出当前桶中元素个数
i=0
#找到第一个比num要大的元素
while i<n and buckets[idx][i]<=num:
i+=1
buckets[idx].insert(i,num)
print(buckets)
#合并桶
nums.clear()
for bucket in buckets:
nums.extend(bucket) #将每个桶中的元素放到nums中
test=[9,3,1,2,7,5,11,22,23,24,35,55]
bucketSort(test)
print(test)
执行结果：
[[1, 2, 3, 5], [7, 9], [11], [], [22, 23, 24], [], [35], [], [], [], [55]]
[1, 2, 3, 5, 7, 9, 11, 22, 23, 24, 35, 55]
时间复杂度为O(n)
使用空间比较大
稳定性：稳定
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/123193.html
