桶排序（Bucket Sort）是一种非比较型排序算法，基于分治思想，通过将数据分配到多个“桶”中，逐个桶排序后合并结果实现整体有序。它的核心是“分而治之”，适合数据分布均匀且范围有限的场景。

桶排序的基本思路¶

1. 分桶：根据数据分布特点，将数据划分到若干个桶中。例如，若数据在0到1之间均匀分布，可将0到1的区间划分为n个等长的子区间（每个子区间对应一个桶，n为数据个数）。
2. 桶内排序：每个桶内元素数量较少，使用简单排序算法（如插入排序、内置排序函数）对桶内元素排序。
3. 合并桶：按桶的顺序依次取出元素，合并成最终有序数组。

适用场景¶

• 数据分布均匀：当数据在某一连续区间内均匀分布时（如0到1之间），桶排序时间复杂度接近线性（O(n)）。
• 范围有限：若数据范围明确（如整数0到1000），便于设置桶的数量和大小。
• 不适用：若数据分布不均匀（如大部分元素集中在少数桶中），可能退化为O(n²)，效率低于快速排序等算法。

Python实现步骤（以0-1区间浮点数为例）¶

1. 确定桶数量：设桶数等于数据长度n，每个桶负责的区间为1/n。
2. 创建桶：初始化n个空桶（列表的列表）。
3. 分配数据到桶：遍历数据，通过int(num * n)计算桶索引，将元素放入对应桶。
4. 桶内排序：对每个桶使用内置排序函数（如sort()）。
5. 合并桶：依次遍历所有桶，将元素合并成有序数组。

代码实现¶

def bucket_sort(arr):
    # 1. 处理空数组
    if not arr:
        return arr

    n = len(arr)
    # 2. 创建n个空桶
    buckets = [[] for _ in range(n)]

    # 3. 将数据分配到桶中（假设数据在0到1之间）
    for num in arr:
        # 计算桶索引：num * n 取整
        bucket_index = int(num * n)
        buckets[bucket_index].append(num)

    # 4. 对每个桶内元素排序并合并结果
    sorted_arr = []
    for bucket in buckets:
        bucket.sort()  # 桶内排序（内置排序高效）
        sorted_arr.extend(bucket)  # 合并桶内元素

    return sorted_arr

# 测试
if __name__ == "__main__":
    test_data = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
    sorted_data = bucket_sort(test_data)
    print("原始数据:", test_data)
    print("排序后:", sorted_data)

代码解释¶

• 桶数量：n = len(arr)，确保每个桶覆盖区间为1/n，避免数据溢出。
• 桶索引计算：int(num * n)将0-1之间的数映射到0到n-1的桶索引，例如num=0.3、n=7时，桶索引为0.3*7=2.1→2。
• 桶内排序：bucket.sort()直接使用内置排序，小数据量下效率极高。
• 合并结果：sorted_arr.extend(bucket)依次添加每个桶的元素，最终得到有序数组。

运行结果¶

原始数据: [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
排序后: [0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52]

注意事项¶

• 数据分布：若数据范围非0-1区间，需调整桶索引计算方式（如int((num - min_val) / bucket_size)）。
• 桶大小优化：桶数量应根据数据分布动态调整，避免部分桶元素过多（如极端值集中时，需增大桶数量）。

总结¶

桶排序通过“分桶-排序-合并”三步实现高效排序，适合数据均匀分布的场景。其核心是利用分治思想降低整体复杂度，代码简洁但需注意数据分布特性，避免性能退化。