🧮 桶排序 (Bucket Sort)

难度 / Difficulty: 中等 (Medium)
分类 / Category: 非比较排序 (Non-comparison Sort)
时间复杂度 / Time Complexity: O(n + k) 平均，O(n²) 最坏
空间复杂度 / Space Complexity: O(n + k)

📖 算法简介 / Introduction

桶排序是一种分布式排序算法，将数据分散到多个”桶”中，每个桶内单独排序，最后按顺序合并所有桶的结果。

Bucket sort is a distribution-based sorting algorithm that distributes elements into multiple buckets, sorts each bucket individually, then concatenates all buckets in order.

核心思想：分而治之 — 通过数据分布特征，将数据分散到不同的桶中，减少比较次数。

💡 算法原理 / Principle

1. 创建桶：根据数据范围创建 n 个桶（通常用数组或链表）
2. 分配数据：遍历原数组，根据数据值将其放入对应桶中（通常用映射函数 i = floor(n * value)）
3. 桶内排序：对每个非空桶使用合适的排序算法（常用插入排序）
4. 合并输出：按桶顺序依次取出所有元素，形成有序数组

关键点：桶的数量和映射函数的选择直接影响排序效果

📝 代码实现 / Implementation

def bucket_sort(arr, num_buckets=5):
    if len(arr) == 0:
        return arr
    
    # 1. 确定范围，创建桶
    min_val, max_val = min(arr), max(arr)
    range_val = max_val - min_val + 1
    bucket_size = max(1, range_val // num_buckets)
    buckets = [[] for _ in range(num_buckets)]
    
    # 2. 分配数据到桶中
    for val in arr:
        index = min((val - min_val) // bucket_size, num_buckets - 1)
        buckets[index].append(val)
    
    # 3. 桶内排序（使用插入排序）
    for bucket in buckets:
        bucket.sort()
    
    # 4. 合并所有桶
    result = []
    for bucket in buckets:
        result.extend(bucket)
    
    return result

✨ 示例 / Example

输入数组：[0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

Step 1: 创建 5 个桶，映射函数: bucket = floor(value * 5)

Step 2: 分配数据
桶0 [0.12, 0.17, 0.21, 0.23]
桶1 []
桶2 [0.26]
桶3 [0.39]
桶4 [0.68, 0.72, 0.78, 0.94]

Step 3: 桶内排序（已是顺序）

Step 4: 合并
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

🎯 适用场景 / Scenarios

• 均匀分布数据 — 数据在范围内均匀分布时效率高
• 浮点数排序 — 适合 [0, 1) 范围的浮点数
• 外部排序 — 数据量太大无法全部放入内存时
• 近似计数 — 统计分布在某个范围的数据

Uniformly distributed data, Floating point sorting, External sorting, Approximate counting.

⚠️ 优缺点 / Pros & Cons

🔄 与计数排序对比 / Comparison with Counting Sort