数据结构与算法——桶排序

比眉伴天荒 2024-04-05 07:07 118阅读 0赞

CSDN话题挑战赛第2期
参赛话题：学习笔记

执行流程图

根据数组的最大值与最小值申请一些桶
将数组的元素放入到桶中，并保证桶里是有序的
最后合并每一个桶

在这里插入图片描述

代码实现

  1. def bucketSort(nums,size=5):
  2.     #根据数组的最大值和最小值确定申请的桶的数量
  3.     maxVal=max(nums)    #数组的最大值
  4.     minVal=min(nums)    #数组的最小值
  5.     bucketCount=(maxVal-minVal)//5+1    #桶的数量
  7.     buckets=[[] for _ in range(bucketCount)]    #申请桶
  9.     for num in nums:
  10.         idx=(num-minVal)//size          #得到num在那个桶中，索引为idx
  11.         n=len(buckets[idx])     #求出当前桶中元素个数
  12.         i=0
  13.         #找到第一个比num要大的元素
  14.         while i<n and buckets[idx][i]<=num:
  15.             i+=1
  16.         buckets[idx].insert(i,num)
  17.     print(buckets)
  18.     #合并桶
  19.     nums.clear()
  20.     for bucket in buckets:
  21.         nums.extend(bucket)     #将每个桶中的元素放到nums中
  24. test=[9,3,1,2,7,5,11,22,23,24,35,55]
  25. bucketSort(test)
  26. 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)
使用空间比较大
稳定性：稳定

在这里插入图片描述

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，118人围观）

还没有评论，来说两句吧...

相关阅读