桶排序

概述

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

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

算法步骤

桶排序的具体步骤如下：

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

伪代码示例

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]
步骤：

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

应用场景

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

与其他排序算法对比

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

优化与变体

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

可视化示例

注意事项

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