编辑“︁桶排序”︁

{{Note|本文介绍的是'''桶排序'''（Bucket Sort），一种分布式排序算法，适用于特定数据分布的场景。}}

== 概述 ==
'''桶排序'''（Bucket Sort）是一种将元素分散到多个“桶”中，再对每个桶单独排序，最后合并结果的排序算法。它属于'''非比较排序'''，时间复杂度可达<math>O(n)</math>，但需要满足特定条件（如数据均匀分布）。其核心思想是：
# 将数据分到有限数量的桶中。
# 对每个桶内的数据排序（通常使用其他排序算法）。
# 按顺序合并所有桶的结果。

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

=== 伪代码示例 ===
<syntaxhighlight lang="python">
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
</syntaxhighlight>

== 复杂度分析 ==
{| class="wikitable"
|+ 桶排序的时间与空间复杂度
|-
! 场景 !! 时间复杂度 !! 空间复杂度
|-
| 最优情况（均匀分布） || <math>O(n + k)</math> || <math>O(n + k)</math>
|-
| 最差情况（全部元素落入一个桶） || <math>O(n^2)</math> || <math>O(n)</math>
|}

其中：
* <math>n</math>：元素数量。
* <math>k</math>：桶的数量。

== 实际案例 ==
=== 示例输入与输出 ===
'''输入数组'''：<code>[0.42, 0.32, 0.87, 0.15, 0.92]</code><br/>
'''步骤'''：
# 创建5个桶（范围：0-0.2, 0.2-0.4, ..., 0.8-1.0）。
# 分配元素：<code>[[0.15], [0.32, 0.42], [], [0.87], [0.92]]</code>。
# 对每个桶排序（本例中仅第二个桶需要排序）。
# 合并结果：<code>[0.15, 0.32, 0.42, 0.87, 0.92]</code>。

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

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

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

== 可视化示例 ==
<mermaid>
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]
</mermaid>

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

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:排序算法]]