Python全系列 教程
3567个小节阅读:5931k
目录
鸿蒙应用开发
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