python 实现·十大排序算法之桶排序 (Bucket Sort)

用户头像
南风以南
关注
发布于: 2020 年 05 月 30 日
python实现·十大排序算法之桶排序(Bucket Sort)

简介



桶排序(Bucket Sort),也叫箱排序,其主要思想是:将待排序集合中处于同一个值域的元素存入同一个桶中,也就是根据元素值特性将集合拆分为多个区域,则拆分后形成的多个桶,从值域上看是处于有序状态的。对每个桶中元素进行排序,则所有桶中元素构成的集合是已排序的。

桶排序是计数排序的扩展版本,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素。桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效。

算法实现步骤



  1. 根据待排序集合中最大元素和最小元素的差值范围和映射规则,确定申请的桶个数;

  2. 遍历排序序列,将每个元素放到对应的桶里去;

  3. 对不是空的桶进行排序;

  4. 按顺序访问桶,将桶中的元素依次放回到原序列中对应的位置,完成排序。

Python 代码实现



# bucket_sort 代码实现
from typing import List
def bucket_sort(arr:List[int]):
"""桶排序"""
min_num = min(arr)
max_num = max(arr)
# 桶的大小
bucket_range = (max_num-min_num) / len(arr)
# 桶数组
count_list = [ [] for i in range(len(arr) + 1)]
# 向桶数组填数
for i in arr:
count_list[int((i-min_num)//bucket_range)].append(i)
arr.clear()
# 回填,这里桶内部排序直接调用了sorted
for i in count_list:
for j in sorted(i):
arr.append(j)



# 测试数据
if __name__ == '__main__':
import random
random.seed(54)
arr = [random.randint(0,100) for _ in range(10)]
print("原始数据:", arr)
bucket_sort(arr)
print("桶排序结果:", arr)



# 输出结果
原始数据: [17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
桶排序结果: [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]

动画演示

算法分析

  • 时间复杂度

最好情况:输入序列是已排好序,那么插入排序的时间复杂度在,即最好情况下时间复杂度为

最坏情况:对于待排序序列大小为 ,共分为 个桶,需进行次循环,将每个元素装入对应的桶中;次循环,对每个桶中的数据进行排序(平均每个桶有个元素)。

若采用快速排序算法进行排序,单次排序的平均时间复杂度为,最坏时间复杂度为。而桶排序的过程是以链表形式插入的,所以整个桶排序的时间复杂度为:

时,时间复杂度最低为 ;当时,时间复杂度最高为。所以最坏时间复杂度为:

平均情况:平均时间复杂度为

  • 空间复杂度

桶排序过程中需要创建个桶的额外空间,以及个元素的额外空间,所以桶排序的空间复杂度为

  • 稳定性

桶排序的稳定性取决于桶内排序使用的算法,如果是队列,可以保证相同的元素取出和放回的相对位置不变,即排序是稳定的,而如果用栈来实现,则排序一定是不稳定的。由于桶排序可以做到稳定,所以桶排序是稳定的排序算法。

  • 综合评价

联系我们



个人博客网站:http://www.bling2.cn/

Github地址:https://github.com/lb971216008/Use-Python-to-Achieve

知乎专栏:https://zhuanlan.zhihu.com/Use-Python-to-Achieve

小专栏:https://xiaozhuanlan.com/Use-Python-to-Achieve

博客园:https://www.cnblogs.com/Use-Python-to-Achieve



发布于: 2020 年 05 月 30 日 阅读数: 48
用户头像

南风以南

关注

南风以南 2018.11.12 加入

石油开发系研究生

评论

发布
暂无评论
python实现·十大排序算法之桶排序(Bucket Sort)