桶排序

概述

桶排序（Bucket Sort）是一种将元素分散到多个“桶”中，再对每个桶单独排序，最后合并结果的排序算法。它属于非比较排序，时间复杂度可达$O(n)$，但需要满足特定条件（如数据均匀分布）。其核心思想是：

1. 将数据分到有限数量的桶中。
2. 对每个桶内的数据排序（通常使用其他排序算法）。
3. 按顺序合并所有桶的结果。

算法步骤

桶排序的具体步骤如下：

1. 确定桶的数量：根据数据范围和分布选择桶的数量（如$k$个桶）。
2. 分配元素到桶中：通过映射函数将元素放入对应的桶。
3. 排序每个桶：使用插入排序等简单算法对非空桶排序。
4. 合并桶：按桶的顺序依次输出元素。

伪代码示例

def bucket_sort(arr, bucket_size=5):
    if len(arr) == 0:
        return arr
    
    # 1. 确定数据范围
    min_val, max_val = min(arr), max(arr)
    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]
    
    # 2. 分配元素到桶中
    for num in arr:
        index = (num - min_val) // bucket_size
        buckets[index].append(num)
    
    # 3. 对每个桶排序并合并
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(sorted(bucket))  # 使用内置排序
    return sorted_arr

复杂度分析

桶排序的时间与空间复杂度

场景	时间复杂度	空间复杂度
最优情况（均匀分布）	$O(n+k)$	$O(n+k)$
最差情况（全部元素落入一个桶）	$O(n^2)$	$O(n)$

其中：

• $n$：元素数量。
• $k$：桶的数量。

实际案例

示例输入与输出

输入数组：[0.42, 0.32, 0.87, 0.15, 0.92]
步骤：

1. 创建5个桶（范围：0-0.2, 0.2-0.4, ..., 0.8-1.0）。
2. 分配元素：[[0.15], [0.32, 0.42], [], [0.87], [0.92]]。
3. 对每个桶排序（本例中仅第二个桶需要排序）。
4. 合并结果：[0.15, 0.32, 0.42, 0.87, 0.92]。

应用场景

1. 浮点数排序：当数据均匀分布在固定范围内时效率极高。 2. 外部排序：处理大数据集时，可将数据分到磁盘上的多个桶中。 3. 分布式系统：将数据分散到不同节点处理。

与其他排序算法对比

• 对比快速排序：桶排序在数据分布均匀时更快，但依赖额外空间。
• 对比计数排序：桶排序适用于更大范围的数据，计数排序要求整数且范围小。

优化与变体

• 动态桶数量：根据数据分布调整桶的数量。
• 混合排序：对大桶递归使用桶排序或切换为其他算法。

可视化示例

graph TD A[输入数组: 0.42, 0.32, 0.87, 0.15, 0.92] --> B[分桶] B --> C1[桶1: 0.15] B --> C2[桶2: 0.32, 0.42] B --> C3[桶3: 空] B --> C4[桶4: 0.87] B --> C5[桶5: 0.92] C1 --> D[排序各桶] C2 --> D C4 --> D C5 --> D D --> E[合并结果: 0.15, 0.32, 0.42, 0.87, 0.92]

注意事项

• 数据分布敏感：若数据集中少数桶中，性能退化为$O(n^2)$。
• 空间开销：需要额外存储桶和中间结果。
• 桶内排序算法选择：影响最终性能（如插入排序适合小规模数据）。