桶排序
桶排序（Bucket Sort）是一种非比较型的排序算法，适用于数据分布均匀且范围已知的情况。其核心思想是将待排序元素分配到有限数量的“桶”中，每个桶再单独排序（通常使用其他排序算法），最后按顺序合并所有桶的结果。桶排序的时间复杂度接近线性，但在最坏情况下可能退化。
算法原理
桶排序的工作流程分为以下三步：
1. 分桶：根据元素的值范围创建固定数量的桶，并将元素分配到对应的桶中。 2. 桶内排序：对每个非空桶内的元素进行排序（例如使用插入排序）。 3. 合并结果：按桶的顺序依次输出所有元素。
数学上，若输入数组为 ，元素范围为 ，桶数量为 ，则元素 分配的桶索引为： 解析失败 (语法错误): {\displaystyle \text{bucket\_index} = \left\lfloor \frac{A[i] - min}{max - min} \times (k - 1) \right\rfloor}
代码示例
以下是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)
输出：
输入数组: [0.42, 0.32, 0.87, 0.12, 0.52] 排序结果: [0.12, 0.32, 0.42, 0.52, 0.87]
复杂度分析
- 时间复杂度：
* 平均情况：，其中 为桶数量。 * 最坏情况：（当所有元素集中在少数桶中）。
- 空间复杂度：（需要额外存储桶）。
实际应用
桶排序常用于以下场景： 1. 浮点数排序：如示例中所示，均匀分布的浮点数适合分桶。 2. 外部排序：当数据量过大无法全部加载到内存时，可分块处理。 3. 分布式系统：将数据分散到多台机器上并行排序。
与其他排序算法的对比
- 优势：在数据分布均匀时效率极高，甚至可达线性时间。
- 劣势：对数据分布敏感，若分布不均可能导致性能退化。