桶排序：修订间差异

可视化wikitext

2025年5月12日 (一) 00:27的最新版本

模板:Note

概述[编辑 | 编辑源代码]

桶排序（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})$ 。
空间开销：需要额外存储桶和中间结果。
桶内排序算法选择：影响最终性能（如插入排序适合小规模数据）。

@@ 第1行： / 第1行： @@
-{{DISPLAYTITLE:桶排序}}
+{{Note|本文介绍的是'''桶排序'''（Bucket Sort），一种分布式排序算法，适用于特定数据分布的场景。}}
-'''桶排序'''（Bucket Sort）是一种非比较型的[[排序算法]]，适用于数据分布均匀且范围已知的情况。其核心思想是将待排序元素分配到有限数量的“桶”中，每个桶再单独排序（通常使用其他排序算法），最后按顺序合并所有桶的结果。桶排序的时间复杂度接近线性，但在最坏情况下可能退化。
-== 算法原理 ==
+== 概述 ==
-桶排序的工作流程分为以下三步：
+'''桶排序'''（Bucket Sort）是一种将元素分散到多个“桶”中，再对每个桶单独排序，最后合并结果的排序算法。它属于'''非比较排序'''，时间复杂度可达<math>O(n)</math>，但需要满足特定条件（如数据均匀分布）。其核心思想是：
+# 将数据分到有限数量的桶中。
+# 对每个桶内的数据排序（通常使用其他排序算法）。
+# 按顺序合并所有桶的结果。
-. '''分桶'''：根据元素的值范围创建固定数量的桶，并将元素分配到对应的桶中。
+== 算法步骤 ==
-. '''桶内排序'''：对每个非空桶内的元素进行排序（例如使用插入排序）。
+桶排序的具体步骤如下：
-. '''合并结果'''：按桶的顺序依次输出所有元素。
+# '''确定桶的数量'''：根据数据范围和分布选择桶的数量（如<math>k</math>个桶）。
+# '''分配元素到桶中'''：通过映射函数将元素放入对应的桶。
+# '''排序每个桶'''：使用插入排序等简单算法对非空桶排序。
+# '''合并桶'''：按桶的顺序依次输出元素。
-数学上，若输入数组为 <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>
+<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>
-== 代码示例 ==
+== 复杂度分析 ==
-以下是Python实现的桶排序代码：
+{| class="wikitable"
+|+ 桶排序的时间与空间复杂度
+|-
+! 场景 !! 时间复杂度 !! 空间复杂度
+|-
+| 最优情况（均匀分布） || <math>O(n + k)</math> || <math>O(n + k)</math>
+|-
+| 最差情况（全部元素落入一个桶） || <math>O(n^2)</math> || <math>O(n)</math>
+|}
-<syntaxhighlight lang="python">
+其中：
-def bucket_sort(arr, bucket_size=5):
+* <math>n</math>：元素数量。
-    if len(arr) == 0:
+* <math>k</math>：桶的数量。
-        return arr
-    # 确定数据范围
+== 实际案例 ==
-    min_val, max_val = min(arr), max(arr)
+=== 示例输入与输出 ===
-    bucket_count = (max_val - min_val) // bucket_size + 1
+'''输入数组'''：<code>[0.42, 0.32, 0.87, 0.15, 0.92]</code><br/>
-    buckets = [[] for _ in range(bucket_count)]
+'''步骤'''：
+# 创建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>。
-    # 分桶
+=== 应用场景 ===
-    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]
+<mermaid>
-output_arr = bucket_sort(input_arr)
+graph TD
-print("输入数组:", input_arr)
+    A[输入数组: 0.42, 0.32, 0.87, 0.15, 0.92] --> B[分桶]
-print("排序结果:", output_arr)
+    B --> C1[桶1: 0.15]
-</syntaxhighlight>
+    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>
-'''输出：'''
+== 注意事项 ==
-<pre>
+* '''数据分布敏感'''：若数据集中少数桶中，性能退化为<math>O(n^2)</math>。
-输入数组: [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>（需要额外存储桶）。
-== 实际应用 ==
-桶排序常用于以下场景：
-. '''浮点数排序'''：如示例中所示，均匀分布的浮点数适合分桶。
-. '''外部排序'''：当数据量过大无法全部加载到内存时，可分块处理。
-. '''分布式系统'''：将数据分散到多台机器上并行排序。
-== 与其他排序算法的对比 ==
-* '''优势'''：在数据分布均匀时效率极高，甚至可达线性时间。
-* '''劣势'''：对数据分布敏感，若分布不均可能导致性能退化。
-== 可视化示例 ==
-<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>
-== 注意事项 ==
-. 桶的数量和大小需根据数据分布合理选择。
-. 若数据分布极度不均匀，建议改用[[基数排序]]或[[计数排序]]。
-{{Algorithms}}
 [[Category:计算机科学]]
-[[Category:数据结构与算法]]
+[[Category:面试技巧]]
 [[Category:排序算法]]