目录Python全系列 教程
3567个小节阅读：5931.9k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本，未来主流的版本
人工智能 教程
顺势而为，AI创新未来
大厂算法 教程
算法，程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
桶排序(bucket sort)是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并
根据长度为n的数组，设置指定k个数量的数组当作空桶(每个桶代表指定范围)；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来
注意
数据尽量服从均匀分布
桶内排序可以使用多种方式：冒泡、插入、快速等等...
xxxxxxxxxx# 插入排序的算法def insertion_sort(arr): for i in range(1,len(arr)): # 循环子序列的时候，就要反着来！ for j in range(i,0,-1): # 如果后面一个数，大于前面的一个数，就交换位置 if arr[j]<arr[j-1]: arr[j],arr[j-1]=arr[j-1],arr[j] return arr# 桶排序def bucket_sort(nums, bucket_size = 5): maxVal, minVal = max(nums), min(nums) # 数据分为 bucketCount 组，这一个是根据每组的数量决定的 bucket_count = (maxVal - minVal) // bucket_size + 1 buckets = [[] for i in range(bucket_count)] # 二维桶 # 利用函数映射将各个数据放入对应的桶中 for num in nums: buckets[(num - minVal) // bucket_size].append(num) # 清空 nums nums.clear() # 对每一个二维桶中的元素进行排序 for bucket in buckets: insertion_sort(bucket) # 假设使用插入排序 nums.extend(bucket) # 将排序好的桶依次放入到 nums 中 return nums
if __name__ == '__main__': arr = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(arr) tmp = bucketSort(arr) print(tmp)桶排序适用于处理体量很大的数据。例如，输入数据包含 100 万个元素，由于空间限制，系统内存无法一次性加载所有数据。此时，可以将数据分成 1000 个桶，然后分别对每个桶进行排序，最后将结果合并。
时间复杂度 $ O(n+k) $ ：假设元素在各个桶内平均分布，那么每个桶内的元素数量为 $ \frac n k$。假设排序单个桶使用 $ O(\frac n k \log \frac n k) $ 时间，则排序所有桶使用 $ O( n \log \frac n k) $ 时间。当桶数量 $ k $ 比较大时，时间复杂度则趋向于 $ O(n) $。合并结果时需要遍历所有桶和元素，花费 $ O(n+k)$ 时间。
自适应排序：在最差情况下，所有数据被分配到一个桶中，且排序该桶使用 $ O(n^2) $ 时间。
空间复杂度 $ O( n+k ) $、非原地排序：需要借助 k 个桶和总共 n 个元素的额外空间。
桶排序是否稳定取决于排序桶内元素的算法是否稳定。
实时效果反馈
1. 关于桶排序算法，说法正确的是？
A 桶排序会分配新数组来存储每个元素出现的次数
B 桶排序必须使用计数排序辅助排序
C 桶排序分配的桶，每个存储元素最多为10个
D 桶排序的数据，均匀分布才会提高效率
答案
1=>D