当前位置：首页 > news >正文

python 桶排序（Bucket Sort）

news 2025/8/6 9:23:55

桶排序（Bucket Sort）

桶排序是一种分布式排序算法，适用于对均匀分布的数据进行排序。它的基本思想是：将数据分到有限数量的桶中，每个桶分别排序，最后将所有桶中的数据合并。

桶排序的步骤：

划分桶：根据数据的范围，将数据分配到若干个桶中。
排序每个桶：对每个桶中的数据进行排序（可以使用其他排序算法，如插入排序）。
合并桶：将所有桶中的数据按顺序合并，得到排序后的结果。

时间复杂度：

最坏情况：O(n²) —— 当所有数据都分配到同一个桶中时。
最好情况：O(n + k) —— 当数据均匀分布时，其中 k 是桶的数量。
平均情况：O(n + k)

空间复杂度：

O(n + k) —— 需要额外的空间来存储桶和排序结果。

Python 实现

def bucket_sort(arr):if len(arr) == 0:return arr# 找到数组中的最大值和最小值max_val = max(arr)min_val = min(arr)# 确定桶的数量和范围bucket_size = 5  # 每个桶的大小bucket_count = (max_val - min_val) // bucket_size + 1buckets = [[] for _ in range(bucket_count)]# 将数据分配到桶中for num in arr:index = (num - min_val) // bucket_sizebuckets[index].append(num)# 对每个桶进行排序sorted_arr = []for bucket in buckets:sorted_arr.extend(sorted(bucket))  # 使用内置排序函数return sorted_arr# 示例使用
arr = [29, 25, 3, 49, 9, 37, 21, 43]
sorted_arr = bucket_sort(arr)
print("排序后的数组:", sorted_arr)

输出结果

排序后的数组: [3, 9, 21, 25, 29, 37, 43, 49]

桶排序的详细过程

以数组 [29, 25, 3, 49, 9, 37, 21, 43] 为例：

划分桶：
- 最大值 49，最小值 3，桶大小 5。
- 桶数量：(49 - 3) // 5 + 1 = 10。
- 分配结果：
  - 桶 0: [3]
  - 桶 1: []
  - 桶 2: [9]
  - 桶 3: []
  - 桶 4: [21, 25]
  - 桶 5: [29]
  - 桶 6: []
  - 桶 7: [37]
  - 桶 8: [43]
  - 桶 9: [49]
排序每个桶：
- 每个桶已经有序。
合并桶：
- 合并结果：[3, 9, 21, 25, 29, 37, 43, 49]

桶排序的优缺点

优点：

在数据均匀分布的情况下，性能优异。
是稳定的排序算法（取决于子排序算法）。

缺点：

数据分布不均匀时，性能可能下降。
需要额外的存储空间。

桶排序的适用场景

数据均匀分布。
数据范围已知。
需要稳定排序的场景。

优化桶排序

动态调整桶大小：
- 根据数据分布动态调整桶的大小和数量。
使用高效子排序算法：
- 对每个桶使用高效的排序算法（如快速排序）。

优化后的桶排序实现

def bucket_sort_optimized(arr):if len(arr) == 0:return arrmax_val = max(arr)min_val = min(arr)# 动态调整桶大小bucket_size = max(1, (max_val - min_val) // len(arr))bucket_count = (max_val - min_val) // bucket_size + 1buckets = [[] for _ in range(bucket_count)]for num in arr:index = (num - min_val) // bucket_sizebuckets[index].append(num)sorted_arr = []for bucket in buckets:sorted_arr.extend(sorted(bucket))  # 使用内置排序函数return sorted_arr# 示例使用
arr = [29, 25, 3, 49, 9, 37, 21, 43]
sorted_arr = bucket_sort_optimized(arr)
print("优化后的排序数组:", sorted_arr)