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

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

[CSDN话题挑战赛第2期][CSDN_2]  
参赛话题：[学习笔记][Link 1]

--------------------

## 执行流程图 ##

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

![在这里插入图片描述][49091b582180416e96baa92e4c215064.png]

## 代码实现 ##

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)  
使用空间比较大  
稳定性：稳定**

![在这里插入图片描述][ad5092877fbc43e8a9bb4413cc4ec6d4.webp_pic_center]

![在这里插入图片描述][2dda6f7ba5a34751bf423aca67841600.gif_pic_center]

[CSDN_2]: https://marketing.csdn.net/p/7b6697fd9dd3795a268d1a6f2fe75012
[Link 1]: https://activity.csdn.net/creatActivity?id=10213
[49091b582180416e96baa92e4c215064.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/04/326d1a9717fe42bebc3d5c63c5d5f4f7.png
[ad5092877fbc43e8a9bb4413cc4ec6d4.webp_pic_center]: https://img-blog.csdnimg.cn/ad5092877fbc43e8a9bb4413cc4ec6d4.webp#pic_center
[2dda6f7ba5a34751bf423aca67841600.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/04/1cb79700e975436eaa41dc17c657c9f3.gif