桶排序（Bucket Sort）的进阶应用：对浮点数进行均匀分布排序

题目描述

给定一个包含 n 个浮点数的数组，每个元素的值均匀分布在 [0, 1) 区间内。要求设计一个基于桶排序的算法，以平均 O(n) 的时间复杂度对数组进行排序。

解题过程

1. 基本思路

桶排序的核心思想是将数据分布到多个“桶”中，每个桶内的数据单独排序，最后合并所有桶得到有序序列。对于均匀分布在 [0, 1) 的浮点数，可以将其值映射到桶的索引，利用均匀分布的特性使每个桶的大小相近。

2. 算法步骤

步骤一：初始化桶

• 创建 n 个空桶（通常用链表或动态数组实现）。
• 桶的索引从 0 到 n-1。

步骤二：分配元素到桶中

• 遍历每个浮点数 x ∈ [0, 1)。
• 计算桶索引：index = floor(x * n)。
• 将 x 插入到对应桶中。
  解释：
  因为 x 均匀分布在 [0, 1)，乘以 n 后均匀分布在 [0, n)。取整后索引均匀分布在 0 到 n-1，每个桶期望包含 1 个元素。

步骤三：对每个桶内部排序

• 对每个非空桶单独排序。
• 由于每个桶的期望大小为 O(1)，可使用插入排序（对小规模数据高效）。

步骤四：合并桶

• 按桶索引从小到大遍历，将桶内已排序的元素依次放入原数组。

3. 时间复杂度分析

• 分配阶段：遍历 n 个元素，每个元素 O(1) 时间插入桶 → O(n)。
• 排序阶段：设第 i 个桶有 n_i 个元素。
  • 对所有桶排序的总时间复杂度为：∑ O(n_i²)（插入排序最坏 O(n_i²)）。
  • 由于元素均匀分布，n_i 的期望为 1，方差小，可以证明 E[∑ n_i²] = O(n)（见补充）。
• 合并阶段：O(n)。
  → 平均时间复杂度为 O(n)。

4. 证明期望时间复杂度为 O(n)

• 设随机变量 n_i 为桶 i 的元素数量。
• 由均匀分布，每个元素独立且等概率落入 n 个桶，n_i 服从二项分布 B(n, 1/n)。
• 期望 E[n_i] = 1，方差 Var(n_i) = n * (1/n) * (1-1/n) = 1 - 1/n。
• 由公式 E[n_i²] = Var(n_i) + (E[n_i])² = (1 - 1/n) + 1² = 2 - 1/n。
• 总代价 E[∑ n_i²] = n * (2 - 1/n) = 2n - 1 = O(n)。

5. 边界情况处理

• 空桶：跳过即可。
• 元素为 1.0：由于 x ∈ [0, 1)，若包含 1.0，可特殊处理到最后一个桶。
• 非均匀分布：若分布不均匀，可能某些桶过大，导致最坏时间复杂度退化至 O(n²)。此时可考虑递归桶排序或改用其他算法。

6. 代码实现框架（伪代码）

function bucketSort(float[] A):
    n = A.length
    buckets = new List[n]  // 每个桶为动态数组
    for i = 0 to n-1:
        buckets[i] = new List()

    // 分配元素
    for each x in A:
        index = floor(x * n)
        buckets[index].append(x)

    // 排序每个桶（插入排序）
    for i = 0 to n-1:
        insertionSort(buckets[i])

    // 合并
    k = 0
    for i = 0 to n-1:
        for each x in buckets[i]:
            A[k++] = x

7. 扩展讨论

• 不均匀分布：可通过采样估计分布，调整桶的划分策略。
• 整数或其他范围：若数据在 [a, b) 区间，可线性映射到 [0, 1)。
• 稳定性：若桶内排序稳定，且分配时保持顺序，整体稳定。

总结

桶排序在数据均匀分布时能实现平均 O(n) 排序，核心在于利用分布特性使桶大小均衡。它通过“分治+小范围排序”减少比较次数，是线性时间排序的重要代表之一。