Python 实现桶排序详解

1. 核心原理

桶排序是一种非比较型排序算法，通过将数据分配到多个“桶”中，每个桶单独排序后再合并。其核心步骤包括：

• 分桶：根据元素的范围或分布，将数据分配到有限数量的桶中。
• 桶内排序：对每个非空桶内的数据进行排序（通常使用插入排序等简单算法）。
• 合并结果：按桶的顺序将数据合并回原数组。

关键特点：

• 适用于数据分布均匀且范围已知的场景。
• 时间复杂度依赖数据分布，理想情况下接近线性。
• 属于**“空间换时间”**的排序策略。

2. 时间复杂度与空间复杂度

维度	说明
最好情况	O(n)（数据均匀分布，每个桶元素数量均衡）
平均情况	O(n + k)，k为桶数量（若每个桶内用O(n²)排序，则为O(n + n²/k)）
最坏情况	O(n²)（所有数据集中在一个桶内）
空间复杂度	O(n + k)（需要额外存储桶和桶内数据）

3. 适用场景

推荐场景	不推荐场景
- 数据均匀分布	- 数据分布极度不均
- 数据范围已知	- 内存严格受限
- 外部排序（如大数据）	- 数据范围未知或动态变化
- 需要稳定排序	- 对空间效率要求高

4. 代码实现（Python）

以下是将范围 [0, 100) 的整数分为10个桶的示例：

def bucket_sort(arr, bucket_size=10):if len(arr) == 0:return arr# 1. 计算数据范围min_val, max_val = min(arr), max(arr)bucket_count = (max_val - min_val) // bucket_size + 1buckets = [[] for _ in range(bucket_count)]# 2. 分桶for num in arr:idx = (num - min_val) // bucket_sizebuckets[idx].append(num)# 3. 桶内排序（此处使用内置排序，实际可用插入排序）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]

5. 分桶过程示例

假设输入数组为 [29, 25, 3, 49, 9, 37, 21, 43]，最小值为3，最大值为49，桶大小为10：

1. 计算桶数量：(49 - 3) // 10 + 1 = 5个桶（范围分别为3-12, 13-22, 23-32, 33-42, 43-52）。
2. 分桶结果：
   • Bucket 0 (3-12): [3, 9]
   • Bucket 1 (13-22): [21]
   • Bucket 2 (23-32): [29, 25]
   • Bucket 3 (33-42): [37]
   • Bucket 4 (43-52): [49, 43]
3. 桶内排序：
   • Bucket 0 → [3, 9]
   • Bucket 1 → [21]
   • Bucket 2 → [25, 29]
   • Bucket 3 → [37]
   • Bucket 4 → [43, 49]
4. 合并结果：[3, 9, 21, 25, 29, 37, 43, 49]。

6. 优化策略

• 动态调整桶大小：根据数据分布自动调整桶的数量和范围。
• 混合排序算法：对小桶使用插入排序，对大桶递归使用桶排序。
• 处理重复元素：使用计数排序优化含大量重复值的数据。

7. 对比其他排序算法

维度	桶排序	快速排序	归并排序
排序类型	非比较排序	比较排序	比较排序
稳定性	是（若桶内排序稳定）	否	是
最佳场景	均匀分布数据	通用随机数据	链表/外部排序
空间开销	高（需额外桶空间）	低（递归栈）	高（合并需额外数组）

8. 总结

桶排序在数据均匀分布且范围已知时效率极高，但需权衡空间开销。适用于大规模数据、外部排序及特定场景（如浮点数排序）。实际应用中需结合数据特点调整分桶策略，以平衡时间与空间效率。