桶排序

桶排序

桶排序（Bucket Sort）是一种基于分配的排序算法。它将元素分散到不同的桶中，然后对每个桶分别进行排序，最后将桶中的元素合并起来。

桶排序的原理

桶排序适用于均匀分布在一定范围内的数值。其主要思想是：

1. 创建若干桶：将要排序的数据分到若干个桶中。
2. 对每个桶内的数据进行排序：桶内的排序可以使用任意排序算法。
3. 合并所有桶中的数据：将排好序的桶中的数据合并，得到最终的有序数据。

桶排序的步骤

1. 创建桶：根据数据范围和桶的数量，创建若干个桶。
2. 分配数据：将数据分配到对应的桶中。
3. 桶内排序：对每个桶中的数据进行排序。
4. 合并数据：将所有桶中的数据按顺序合并，得到排序后的结果。

图示

示例

以下是一个桶排序的示例，假设我们有一个浮点数数组：[0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]。

第一步：创建桶

假设我们创建10个桶，每个桶对应范围是[0, 0.1)，[0.1, 0.2)，[0.2, 0.3)等。

第二步：分配数据

将每个数据分配到对应的桶中：

• 0.42 -> 桶4
• 0.32 -> 桶3
• 0.23 -> 桶2
• 0.52 -> 桶5
• 0.25 -> 桶2
• 0.47 -> 桶4
• 0.51 -> 桶5

第三步：桶内排序

对每个桶中的数据进行排序：

• 桶2: [0.23, 0.25]
• 桶3: [0.32]
• 桶4: [0.42, 0.47]
• 桶5: [0.51, 0.52]

第四步：合并数据

将所有桶中的数据合并：[0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]

复杂度分析

桶排序适用于处理体量很大的数据。例如，输入数据包含 100 万个元素，由于空间限制，系统内存无法一次性加载所有数据。此时，可以将数据分成 1000 个桶，然后分别对每个桶进行排序，最后将结果合并。

• 时间复杂度为 $O(n + k)$ ：假设元素在各个桶内平均分布，那么每个桶内的元素数量为 $\frac{n}{k}$ 。假设排序单个桶使用 $O(\frac{n}{k} \log\frac{n}{k})$ 时间，则排序所有桶使用 $O(n \log\frac{n}{k})$ 时间。当桶数量 $k$ 比较大时，时间复杂度则趋向于 $O(n)$ 。合并结果时需要遍历所有桶和元素，花费 $O(n + k)$ 时间。
• 自适应排序：在最差情况下，所有数据被分配到一个桶中，且排序该桶使用 $O(n^2)$ 时间。
• 空间复杂度为 $O(n + k)$、非原地排序：需要借助 $k$ 个桶和总共 $n$ 个元素的额外空间。
• 桶排序是否稳定取决于排序桶内元素的算法是否稳定。

时间复杂度

• 最佳情况：$O(n)$。
• 最坏情况：$O(n^2)$。
• 平均情况：$O(n+k)$。

空间复杂度

• 空间复杂度：$O(n \cdot k)$

如何实现平均分配

桶排序的时间复杂度理论上可以达到 $O(n)$ ，关键在于将元素均匀分配到各个桶中，因为实际数据往往不是均匀分布的。若将区间平均划分为 10 个，各个桶中的数据的数量差距会非常大。

为实现平均分配，我们可以先设定一条大致的分界线，将数据粗略地分到 3 个桶中。分配完毕后，再将数据较多的桶继续划分为 3 个桶，直至所有桶中的元素数量大致相等。

这种方法本质上是创建一棵递归树，目标是让叶节点的值尽可能平均。当然，不一定要每轮将数据划分为 3 个桶，具体划分方式可根据数据特点灵活选择。

如果我们提前知道数据的概率分布，则可以根据数据概率分布设置每个桶的价格分界线。值得注意的是，数据分布并不一定需要特意统计，也可以根据数据特点采用某种概率模型进行近似。

Java代码实现

/* 桶排序 */
void bucketSort(float[] nums) {
    // 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    int k = nums.length / 2;
    List<List<Float>> buckets = new ArrayList<>();
    for (int i = 0; i < k; i++) {
        buckets.add(new ArrayList<>());
    }
    // 1. 将数组元素分配到各个桶中
    for (float num : nums) {
        // 输入数据范围为 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
        int i = (int) (num * k);
        // 将 num 添加进桶 i
        buckets.get(i).add(num);
    }
    // 2. 对各个桶执行排序
    for (List<Float> bucket : buckets) {
        // 使用内置排序函数，也可以替换成其他排序算法
        Collections.sort(bucket);
    }
    // 3. 遍历桶合并结果
    int i = 0;
    for (List<Float> bucket : buckets) {
        for (float num : bucket) {
            nums[i++] = num;
        }
    }
}