编辑“︁桶排序”︁

{{DISPLAYTITLE:桶排序}}  
'''桶排序'''（Bucket Sort）是一种非比较型的[[排序算法]]，适用于数据分布均匀且范围已知的情况。其核心思想是将待排序元素分配到有限数量的“桶”中，每个桶再单独排序（通常使用其他排序算法），最后按顺序合并所有桶的结果。桶排序的时间复杂度接近线性，但在最坏情况下可能退化。

== 算法原理 ==  
桶排序的工作流程分为以下三步：  

1. '''分桶'''：根据元素的值范围创建固定数量的桶，并将元素分配到对应的桶中。  
2. '''桶内排序'''：对每个非空桶内的元素进行排序（例如使用插入排序）。  
3. '''合并结果'''：按桶的顺序依次输出所有元素。  

数学上，若输入数组为 <math>A</math>，元素范围为 <math>[min, max]</math>，桶数量为 <math>k</math>，则元素 <math>A[i]</math> 分配的桶索引为：  
<math>\text{bucket\_index} = \left\lfloor \frac{A[i] - min}{max - min} \times (k - 1) \right\rfloor</math>

== 代码示例 ==  
以下是Python实现的桶排序代码：  

<syntaxhighlight lang="python">  
def bucket_sort(arr, bucket_size=5):  
    if len(arr) == 0:  
        return arr  

    # 确定数据范围  
    min_val, max_val = min(arr), max(arr)  
    bucket_count = (max_val - min_val) // bucket_size + 1  
    buckets = [[] for _ in range(bucket_count)]  

    # 分桶  
    for num in arr:  
        index = (num - min_val) // bucket_size  
        buckets[index].append(num)  

    # 桶内排序并合并  
    sorted_arr = []  
    for bucket in buckets:  
        sorted_arr.extend(sorted(bucket))  # 使用内置排序  

    return sorted_arr  

# 示例输入与输出  
input_arr = [0.42, 0.32, 0.87, 0.12, 0.52]  
output_arr = bucket_sort(input_arr)  
print("输入数组:", input_arr)  
print("排序结果:", output_arr)  
</syntaxhighlight>  

'''输出：'''  
<pre>  
输入数组: [0.42, 0.32, 0.87, 0.12, 0.52]  
排序结果: [0.12, 0.32, 0.42, 0.52, 0.87]  
</pre>  

== 复杂度分析 ==  
* '''时间复杂度'''：  
  * 平均情况：<math>O(n + k)</math>，其中 <math>k</math> 为桶数量。  
  * 最坏情况：<math>O(n^2)</math>（当所有元素集中在少数桶中）。  
* '''空间复杂度'''：<math>O(n + k)</math>（需要额外存储桶）。  

== 实际应用 ==  
桶排序常用于以下场景：  
1. '''浮点数排序'''：如示例中所示，均匀分布的浮点数适合分桶。  
2. '''外部排序'''：当数据量过大无法全部加载到内存时，可分块处理。  
3. '''分布式系统'''：将数据分散到多台机器上并行排序。  

== 与其他排序算法的对比 ==  
* '''优势'''：在数据分布均匀时效率极高，甚至可达线性时间。  
* '''劣势'''：对数据分布敏感，若分布不均可能导致性能退化。  

== 可视化示例 ==  
<mermaid>  
graph TD  
    A[输入数组: 0.42, 0.32, 0.87, 0.12, 0.52] --> B[分桶]  
    B --> C1[桶0: 0.12]  
    B --> C2[桶1: 0.32, 0.42]  
    B --> C3[桶2: 0.52]  
    B --> C4[桶3: 0.87]  
    C1 --> D[排序每个桶]  
    C2 --> D  
    C3 --> D  
    C4 --> D  
    D --> E[合并结果: 0.12, 0.32, 0.42, 0.52, 0.87]  
</mermaid>  

== 注意事项 ==  
1. 桶的数量和大小需根据数据分布合理选择。  
2. 若数据分布极度不均匀，建议改用[[基数排序]]或[[计数排序]]。  

{{Algorithms}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:排序算法]]