桶排序

1. 桶排序算法思想

>[!tip] 桶排序（Bucket Sort）基本思想： 将待排序数组中的元素分散到若干个「桶」中，然后对每个桶中的元素再进行单独排序。

前述几种排序算法都属于“基于比较的排序算法”，它们通过比较元素间的大小来实现排序。此类排序算法的时间复杂度无法超越 O(nlog⁡n) 。接下来，我们将探讨几种“非比较排序算法”，它们的时间复杂度可以达到线性阶。

桶排序（bucket sort）是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。

2.算法流程

1. 确定桶的数量：根据待排序数组的值域范围，将数组划分为 k 个桶，每个桶可以看做是一个范围区间。
2. 分配元素：遍历待排序数组元素，将每个元素根据大小分配到对应的桶中。
3. 对每个桶进行排序：对每个非空桶内的元素单独排序（使用插入排序、归并排序、快排排序等算法）。
4. 合并桶内元素：将排好序的各个桶中的元素按照区间顺序依次合并起来，形成一个完整的有序数组。

我们以[0.49,0.96,0.82,0.09,0.57,0.43,0.91,0.75,0.15,0.37]为例，演示一下桶排序算法的整个步骤。

代码如下所示： PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

>[!error] >下面代码索引越界，暂未找到原因

/* 桶排序 */
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;
        }
    }
}

3.算法特性

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

• 时间复杂度为 O(n+k) ：假设元素在各个桶内平均分布，那么每个桶内的元素数量为 n/k 。假设排序单个桶使用 O((nlog⁡n/k)/k) 时间，则排序所有桶使用 O(nlog⁡n/k) 时间。当桶数量 k 比较大时，时间复杂度则趋向于 O(n) 。合并结果时需要遍历所有桶和元素，花费 O(n+k) 时间。在最差情况下，所有数据被分配到一个桶中，且排序该桶使用 O(n^2) 时间。
• 空间复杂度为 O(n+k)、非原地排序：需要借助 k 个桶和总共 n 个元素的额外空间。
• 排序稳定性：桶排序的稳定性取决于桶内使用的排序算法。如果桶内使用稳定的排序算法（比如插入排序算法），并且在合并桶的过程中保持相等元素的相对顺序不变，则桶排序是一种 稳定排序算法。反之，则桶排序是一种 不稳定排序算法。

4.如何实现平均分配

桶排序的时间复杂度理论上可以达到 O(n) ，关键在于将元素均匀分配到各个桶中，因为实际数据往往不是均匀分布的。 例如，我们想要将淘宝上的所有商品按价格范围平均分配到 10 个桶中，但商品价格分布不均，低于 100 元的非常多，高于 1000 元的非常少。若将价格区间平均划分为 10 个，各个桶中的商品数量差距会非常大。

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

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

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

如下图所示，我们假设商品价格服从正态分布，这样就可以合理地设定价格区间，从而将商品平均分配到各个桶中。