博采众长：桶排序

一句话总结

桶排序算法的核心思想分三步：

1、将待排序数组中的元素使用映射函数分配到若干个「桶」中。

2、对每个桶中的元素进行排序。

3、最后将这些排好序的桶进行合并，得到排序结果。

桶排序算法可能并不常见，但我个人感觉它的思想非常有意思，因为你可以在它的算法思想中同时看到前面讲的 归并排序 和 计数排序 的影子。

如果你按顺序学习了前面的所有算法，就会感慨这些算法之间千丝万缕的联系。看看这一代代计算机大佬，就为了「排序」这一个需求，真所谓八仙过海各显神通，精妙的想法层出不穷，我们作为后辈，何不好好品味一下呢？

桶排序的关键点

言归正传，桶排序的思路真的很简单，就是先把待排序数组中的元素分配到若干个桶中，对每个桶中的元素分别进行排序，最后再把这些桶中的元素按顺序合并起来。

这个思路是不是有点像 归并排序？都是把大的数组分成小的数组进行排序，最后再合并起来。不过桶排序更加灵活，三个核心步骤中每一步都可以变化：

1、如何将待排序元素分配到桶中？你需要决定桶的数量，并提供一个映射函数。

2、如何对每个桶中的元素进行排序？理论上可以使用任意排序算法，或者模拟 归并排序 的思路，对每个桶递归地运行桶排序。

3、如何将排好序的桶合并起来？后面的章节会讲 合并多个有序链表/数组 的通用算法，但那个算法会用到 二叉堆结构，且复杂度为 O(n∗logk)，这里显然不适用：

如果我都用上二叉堆了，还搞什么桶排序，直接上 堆排序 不就完事了，是吧？所以这一步合并操作的时间复杂度不能超过 O(n)，要做到这一点，就要合理设计分配元素的映射函数。

关于这三个问题，我想首先探讨其中第二个问题。不知道你有没有想过，为什么要把待排序数组分成若干个桶，然后再对每个桶进行排序？这样排序，和直接对整个待排序数组排序相比，真的有区别吗？

答案是，如果暂时不考虑合并有序桶的算法复杂度，那么分开排序当然要比整体排序效率高。

当然，上述分析都没有考虑合并有序桶的时间复杂度，不过只要能在 O(n) 的时间内进行合并，那么桶排序的总时间复杂度依然是小于 O(n²) 的。

下面我将来探讨如何把待排序元素分配到桶中，以及如何合并有序桶，最后给出桶排序的几种代码实现。

桶排序的实现

桶排序可以自选对每个桶的排序函数，一般的选择是 插入排序，因为插入排序属于比较简单的稳定排序算法，而且在几个 O(n²) 的基本排序算法中，插入排序的综合能力较强。

还有一种做法是对每个桶递归地运行桶排序，最终也能把所有元素排好序。这个算法的问题是会消耗较多的空间复杂度，因为你要递归建桶，同一个元素可能存储到了多个桶中，相当于重复存储，会消耗额外的空间。

这两种代码实现我都会给出，供你参考。不过在此之前，先要研究如何将待排序元素分配到桶中。

将元素分配到 k 个桶中 根据前面的分析，桶的数量 k 会影响桶排序的时间复杂度，所以我们可以把桶的数量 k 作为一个参数传入桶排序函数中。

void bucketSort(int[] nums, int k) {}

如何将待排序元素分配到 k 个桶中呢？

你可能会说，之前的文章 环形数组技巧、 哈希表原理 都遇到过类似的问题，把无限大的整数映射到有限的索引区间中，用的都是求模（余数）的技巧呀。

现在有 n 个待排序元素，想分配到 k 个桶中，直接求模不就行了？

for (int i = 0; i < nums.length; i++) {
    int bucketIndex = nums[i] % k;
    // 将 nums[i] 分配到第 bucketIndex 个桶中
}

实际上这样不行。

不要忘了前面的分析，你这里选择的映射函数，直接决定了合并有序桶的时间复杂。如果你使用求模这种方式进行映射，那么合并有序桶的时间复杂度就会超过 O(n)。

为什么呢？我举个简单的例子你就明白了。假设现在待排序数组 nums 中有 0~99 这一百个数字，乱序排列，现在要把它们分配到 k=10 个桶中，给你下面两种分配方法：

第一种，就是求模的方式。nums[i] % 10 = 0 的元素都分配到第一个桶中，nums[i] % 10 = 1 的元素都分配到第二个桶中，以此类推。

第二种，用除法（向下取整）。nums[i] / 10 = 0 的元素都分配到第一个桶中，nums[i] / 10 = 1 的元素都分配到第二个桶中，以此类推。

请你仔细参究，到底这两种方法有没有优劣之分？

答案是第二种用除法的方式更好。

对于第一种求模的方式，第一个桶排序好之后是 0, 10, 20, ...，第二个桶排序好之后是 1, 11, 21, ...，第三个桶排序好之后是 2, 12, 22, 32, ...，以此类推。

最后你只能用 合并多个有序链表/数组 的通用算法，借助二叉堆来合并这些有序数组，时间复杂度是 O(n∗logk)。

再看第二种除法的方式，第一个桶排序好之后是 0, 1, 2, ...，第二个桶排序好之后是 10, 11, 12, ...，第三个桶排序好之后是 20, 21, 22, ...，以此类推。

这样的话，你只需要把这十个有序数组依次连接，就能得到一个有序数组，时间复杂度是 O(n)。

综上，求模的方法不可行，我们需要用除法向下取整的方式来将元素分配到桶中。

那么除法中的除数如何确定呢？首先还是要使用 计数排序 中的技巧，将数组中的元素转换为从 0 开始的非负整数，然后根据桶的个数 k 就能推导出除数了。

具体看代码吧，下面将分别给出使用插入排序和递归桶排序的代码实现。

使用插入排序的桶排序

下面的 insertSort 函数是直接从 插入排序 中复制过来，你可以主要理解一下 bucketSort 函数的实现：

// 使用插入排序的桶排序算法
void bucketSort(int[] nums, int bucketCount) {
    // 找到最大和最小元素
    // 用来计算索引偏移量和除数
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int num : nums) {
        min = Math.min(min, num);
        max = Math.max(max, num);
    }

    int offset = -min;

    // 计算理论上每个桶需要装的元素个数
    int bucketSize = (max - min) / bucketCount + 1;

    // 初始化桶
    ArrayList<Integer>[] buckets = new ArrayList[bucketCount];
    for (int i = 0; i < bucketCount; i++) {
        buckets[i] = new ArrayList<>();
    }

    // 将元素分配到桶中
    for (int num : nums) {
        // 用除法向下取整的方式计算桶的索引
        int index = (num + offset) / bucketSize;
        buckets[index].add(num);
    }

    // 对每个桶中的元素进行排序
    for (int i = 0; i < bucketCount; i++) {
        insertSort(buckets[i]);
    }

    // 合并有序桶
    int index = 0;
    for (int i = 0; i < bucketCount; i++) {
        for (int num : buckets[i]) {
            nums[index++] = num;
        }
    }
}

// 插入排序算法，详见前文「插入排序」
void insertSort(ArrayList<Integer> nums) {
    int sortedIndex = 0;
    while (sortedIndex < nums.size()) {
        for (int i = sortedIndex; i > 0; i--) {
            if (nums.get(i) < nums.get(i - 1)) {
                int tmp = nums.get(i);
                nums.set(i, nums.get(i - 1));
                nums.set(i - 1, tmp);
            } else {
                break;
            }
        }
        sortedIndex++;
    }
}

只要把上述堆排序算法稍加修改，即可完成力扣第 912 题「排序数组」。桶的数量设置越多，算法的执行时间就会越短，你可以结合力扣给出的运行时间，调整桶的数量 bucketCount 多次提交试试看。

使用递归的桶排序

只要将上述代码中的 insertSort(buckets[i]) 改成 bucketSort(buckets[i], bucketCount)，就可以实现递归桶排序。

不过需要注意，递归桶排序的关键在于 base case，即递归的结束条件：当我们发现所有元素都已经有序时，应该结束递归，否则会进入无限递归导致堆栈溢出。

所以这个算法的开头还需要一个额外的 for 循环遍历桶中的元素判断是否已经有序:

// 使用递归的桶排序算法
void bucketSort(ArrayList<Integer> nums, int bucketCount) {
    // 判断是否所有元素都已经有序
    boolean sorted = true;
    for (int i = 1; i < nums.size(); i++) {
        if (nums.get(i) < nums.get(i - 1)) {
            sorted = false;
            break;
        }
    }
    if (sorted) {
        // 所有元素都已经有序，结束递归
        return;
    }
    // 找到最大和最小元素
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int num : nums) {
        min = Math.min(min, num);
        max = Math.max(max, num);
    }

    int offset = -min;

    // 计算理论上每个桶需要装的元素个数
    int bucketSize = (max - min) / bucketCount + 1;

    // 初始化桶
    ArrayList<Integer>[] buckets = new ArrayList[bucketCount];
    for (int i = 0; i < bucketCount; i++) {
        buckets[i] = new ArrayList<>();
    }

    // 将元素分配到桶中
    for (int num : nums) {
        int index = (num + offset) / bucketSize;
        buckets[index].add(num);
    }

    // 对每个桶中的元素进行排序
    for (int i = 0; i < bucketCount; i++) {
        bucketSort(buckets[i], bucketCount);
    }

    // 合并有序桶
    int index = 0;
    for (int i = 0; i < bucketCount; i++) {
        for (int num : buckets[i]) {
            nums.set(index++, num);
        }
    }
}

排序的稳定性

桶排序的稳定性主要取决于对每个桶的排序算法，上面给出的两种实现都是稳定排序。

首先，分配元素到 k 个桶的过程中，我们是按顺序遍历 nums 数组的，所有相同元素必然会被分配到同一个桶中，且在桶中的相对顺序不会改变。

最后一步合并多个桶的过程中，我们是按顺序遍历桶中的元素，所以排序稳定性主要取决于对每个桶的排序算法。

如果对每个桶中的元素使用插入排序，因为插入排序是稳定排序，所以排序过程中相同元素的相对顺序也不会改变。因此整个桶排序算法是稳定的。

如果对当前桶递归地使用桶排序，那么当前桶的元素分配到新的桶中时，相同元素的相对顺序也不会改变，以此类推，最终的排序结果也没有改变相同元素的相对位置，所以排序结果也是稳定的。

如果你使用了其他排序算法，比如选择排序，那么桶排序的稳定性就无法保证了。

时空复杂度分析

桶排序的时间复杂度主要取决于对每个桶的排序算法，推导起来比较复杂，需要一些数学知识，这里就不详细展开了，你可以先记住：

上面两种实现，空间复杂度是 O(n+k)，均摊时间复杂度是 O(n+k)，最坏时间复杂度是 O(n²) （假想所有元素都被分配到同一个桶中，此时就等于插入排序，当然这种情况一般不会出现）。