桶排序

桶排序的思想是：

  • 将区间划分为 n 个相同大小的子区间，每个子区间称为一个桶
  • 遍历数组，将每个数字装入桶中
  • 对每个桶内的数字单独排序，这里需要采用其他排序算法，如插入、归并、快排等
  • 最后按照顺序将所有桶内的数字合并起来
    桶排序在实际工作中的应用较少，不仅因为它需要借助于其他排序算法，还因为桶排序算法基于一个假设：所有输入数据都服从均匀分布，也就是说输入数据应该尽可能地均匀分布在每个桶中。只有这个假设成立时，桶排序运行效率才比较高。

在最差的情况下，所有数据都会被装入同一个桶中，此时桶排序算法只会徒增一轮遍历。

使用桶排序算法时，我们需要考虑两个因素：

  • 设置多少个桶比较合适
  • 桶采用哪种数据结构

这两个因素会直接影响到桶排序的内存和效率。

  • 桶的数量：桶的数量过少，会导致单个桶内的数字过多，桶排序的时间复杂度就会在很大程度上受桶内排序算法的影响。桶的数量过多，占用的内存就会较大，并且会出现较多的空桶，影响遍历桶的效率。具体设置多少个桶需要根据实际情况决定。

  • 桶的数据结构：如果将桶的数据结构设置为数组，那么每个桶的长度必须设置为待排序数组的长度，因为我们需要做好最坏的打算，即所有的数字都被装入了同一个桶中，所以这种方案的空间复杂度会很高。
    那么是不是将桶的数据结构设置为链表就更好呢？使用链表有一个好处，即所有桶的总长度刚好等于待排序数组的长度，不会造成内存浪费。但使用链表也会有一些问题，我们待会一一分析。

接下来我们就分别学习一下这两种数据结构实现的桶排序算法。

以数组作为桶

优化：声明时所有的数组都为空，当需要添加数字时，不断扩容，并加入新数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public static void bucketSort(int[] arr) {
    // 判空及防止数组越界
    if (arr == null || arr.length <= 1) return;
    // 找到最大值，最小值
    int max = arr[0];
    int min = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
        else if (arr[i] < min) min = arr[i];
    }
    // 确定取值范围
    int range = max - min;
    // 设置桶的数量，这里我们设置为 100 个，可以根据实际情况修改。
    int bucketAmount = 100;
    // 桶和桶之间的间距
    double gap = range * 1.0 / (bucketAmount - 1);
    // 用二维数组来装桶，第一个维度是桶的编号，第二个维度是桶中的数字。初始化长度为 0
    int[][] buckets = new int[bucketAmount][];
    // 装桶
    for (int value : arr) {
        // 找到 value 属于哪个桶
        int index = (int) ((value - min) / gap);
        buckets[index] = add(buckets[index], value);
    }
    int index = 0;
    // 对每个桶内的数字进行单独排序
    for (int i = 0; i < bucketAmount; i++) {
        if (buckets[i] == null || buckets[i].length == 0) continue;
        // 这里需要结合其他排序算法，例如：插入排序
        insertSort(buckets[i]);
        // 排序完成后将桶内的结果收集起来
        System.arraycopy(buckets[i], 0, arr, index, buckets[i].length);
        index += buckets[i].length;
    }
}
// 数组扩容
public static int[] add(int[] arr, int num) {
    if (arr == null) return new int[]{num};
    int[] newArr = Arrays.copyOf(arr, arr.length + 1);
    newArr[arr.length] = num;
    return newArr;
}
// 插入排序
public static void insertSort(int[] arr) {
    // 从第二个数开始，往前插入数字
    for (int i = 1; i < arr.length; i++) {
        int currentNumber = arr[i];
        int j = i - 1;
        // 寻找插入位置的过程中，不断地将比 currentNumber 大的数字向后挪
        while (j >= 0 && currentNumber < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 两种情况会跳出循环：1. 遇到一个小于或等于 currentNumber 的数字，跳出循环，currentNumber 就坐到它后面。
        // 2. 已经走到数列头部，仍然没有遇到小于或等于 currentNumber 的数字，也会跳出循环，此时 j 等于 -1，currentNumber 就坐到数列头部。
        arr[j + 1] = currentNumber;
    }
}

优化之后，以数组作为桶就不会造成太大的内存消耗了，并且我们不再需要 bucketLength 数组来记录桶的长度。

这里的扩容算法和 ArrayList 扩容很相似，先开辟一个更长的新数组，并将原数组拷贝过来，再加入新数字。但 ArrayList 扩容时，数组长度是先从 0 扩容到 10，后续再不断乘以 1.5 倍，这会造成一定的内存浪费。

无论是数组还是 ArrayList，扩容过程都比较耗时，所以这个优化属于用时间换空间。

以链表作为桶

以链表作为桶的桶排序和以数组作为桶的桶排序思路是类似的，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public static void bucketSort(int[] arr) {
    // 判空及防止数组越界
    if (arr == null || arr.length <= 1) return;
    // 找到最大值，最小值
    int max = arr[0];
    int min = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
        else if (arr[i] < min) min = arr[i];
    }
    // 确定取值范围
    int range = max - min;
    // 设置桶的数量，这里我们设置为 100 个，可以任意修改。
    int bucketAmount = 100;
    // 桶和桶之间的间距
    double gap = range * 1.0 / (bucketAmount - 1);
    HashMap<Integer, LinkedList<Integer>> buckets = new HashMap<>();
    // 装桶
    for (int value : arr) {
        // 找到 value 属于哪个桶
        int index = (int) ((value - min) / gap);
        if (!buckets.containsKey(index)) {
            buckets.put(index, new LinkedList<>());
        }
        buckets.get(index).add(value);
    }
    int index = 0;
    // 对每个桶内的数字进行单独排序
    for (int i = 0; i < bucketAmount; i++) {
        LinkedList<Integer> bucket = buckets.get(i);
        if (bucket == null) continue;
        // 这里需要结合其他排序算法，例如：插入排序
        insertSort(bucket);
        // 排序完成后将桶内的结果收集起来
        for (int num : bucket) {
            arr[index++] = num;
        }
    }
}
// 对链表插入排序
public static void insertSort(LinkedList<Integer> arr) {
    // 从第二个数开始，往前插入数字
    for (int i = 1; i < arr.size(); i++) {
        int currentNumber = arr.get(i);
        int j = i - 1;
        // 寻找插入位置的过程中，不断地将比 currentNumber 大的数字向后挪
        while (j >= 0 && currentNumber < arr.get(j)) {
            arr.set(j + 1, arr.get(j));
            j--;
        }
        // 两种情况会跳出循环：1. 遇到一个小于或等于 currentNumber 的数字，跳出循环，currentNumber 就坐到它后面。
        // 2. 已经走到数列头部，仍然没有遇到小于或等于 currentNumber 的数字，也会跳出循环，此时 j 等于 -1，currentNumber 就坐到数列头部。
        arr.set(j + 1, currentNumber);
    }
}

首先，我们仍然是找到数组中的最大值和最小值，确定出数据的取值范围，然后划分 100 个桶，计算出间距。并且把所有的数字都放入 LinkedList 链表中。装桶后，再对链表进行插入排序即可。

采用 LinkedList，装桶时不会有额外的空间浪费，但装桶后排序会比较耗时，因为访问 LinkedList 链表时，get 和 set 方法都需要从链表头部开始，逐个向后寻找结点，效率较低。

使用链表排序还有一个问题：由于链表中不能存储基本类型，所以我们不得不将链表类型声明为 LinkedList，int 和 Integer 互相转换的过程被称为 「装箱」和「拆箱」，这也会造成额外的性能消耗。

折中的方案：装桶时用链表，桶内排序用数组

为了解决以上两种数据结构各自的痛点，我们可以采用一种折中的方案：装桶时使用 LinkedList，避免扩容问题，桶内排序时将链表转换为数组，再进行排序，避免 LinkedList 排序较慢的问题和大量 「装箱」和「拆箱」的性能消耗（整个链表中的 Integer 都只需要拆箱一次）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public static void bucketSort(int[] arr) {
    // 判空及防止数组越界
    if (arr == null || arr.length <= 1) return;
    // 找到最大值，最小值：O(n)
    int max = arr[0];
    int min = arr[0];
    for (int i = 1; i < arr.length; i++) {  
        if (arr[i] > max) max = arr[i];
        else if (arr[i] < min) min = arr[i];
    }
    // 确定取值范围
    int range = max - min;
    // 设置桶的数量，这里我们设置为 100 个，可以任意修改。
    int bucketAmount = 100;
    // 桶和桶之间的间距
    double gap = range * 1.0 / (bucketAmount - 1);
    HashMap<Integer, Queue<Integer>> buckets = new HashMap<>();
    // 装桶
    for (int value : arr) {
        // 找到 value 属于哪个桶：O(n)
        int index = (int) ((value - min) / gap);
        if (!buckets.containsKey(index)) {
            buckets.put(index, new LinkedList<>());
        }
        buckets.get(index).add(value);
    }
    int index = 0;
    // 对每个桶内的数字进行单独排序
    for (int i = 0; i < bucketAmount; i++) {
        Queue<Integer> bucket = buckets.get(i);
        if (bucket == null) continue;
        // 将链表转换为数组，提升排序性能
        int[] arrInBucket = bucket.stream().mapToInt(Integer::intValue).toArray();
        // 这里需要结合其他排序算法，例如：插入排序
        insertSort(arrInBucket);
        // 排序完成后将桶内的结果收集起来
        System.arraycopy(arrInBucket, 0, arr, index, arrInBucket.length);
        index += arrInBucket.length;
    }
}
// 插入排序
public static void insertSort(int[] arr) {
    // 从第二个数开始，往前插入数字
    for (int i = 1; i < arr.length; i++) {
        int currentNumber = arr[i];
        int j = i - 1;
        // 寻找插入位置的过程中，不断地将比 currentNumber 大的数字向后挪
        while (j >= 0 && currentNumber < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 两种情况会跳出循环：1. 遇到一个小于或等于 currentNumber 的数字，跳出循环，currentNumber 就坐到它后面。
        // 2. 已经走到数列头部，仍然没有遇到小于或等于 currentNumber 的数字，也会跳出循环，此时 j 等于 -1，currentNumber 就坐到数列头部。
        arr[j + 1] = currentNumber;
    }
}

桶排序的时间复杂度为 O(n)，需要注意的是，这里 n 的常数项是比较大的，意味着桶排序不一定比 O(nlogn) 级的排序算法快。

空间复杂度为 O(n)。

桶排序 VS (计数排序 || 基数排序)

桶排序也是一种线性时间复杂度的排序算法。许多文章中说计数排序和基数排序都是桶排序的一种特殊情况，但笔者认为这种说法不太准确。

桶排序 VS 计数排序：虽然计数排序也有划分子区间的操作，但是计数排序在统计了每个数字出现的次数后，主要是通过计算每个数字在排序完成后的数组中的最终位置来完成排序，并没有真正把数字装到桶中。而桶排序则是将所有数字装入了桶里，最后从桶里取出每个数字。桶排序的过程比较像我们在计数排序的文章中介绍的「伪计数排序 2.0 版本」。

桶排序 VS 基数排序：如果把基数排序看作桶排序，那么基数排序的过程就是不断地装桶，基数排序并没有桶内排序这一步。而桶排序主要分为两步：装桶和桶内排序，桶内排序时需要借助其他排序算法。

并且桶排序基于输入数据均匀分布的假设，计数排序和基数排序则没有这样的限制。

参考