十大经典排序(九)--桶排序

vlambda
2021-07-03

十大经典排序(九)--桶排序

桶排序思想：

桶排序用一句话来说就是划分多个范围相同的区间，将待排序元素分配到各个区间中，每个子区间进行自排序，最后合并各个自区间数据

它和计数排序十分类似，可以说是计数排序的一个升级版，不了解计数排序的可以看下这篇

在计数排序中我们知道，当待排序的元素最大值和最小值相差很大时，计数排序空间浪费巨大，而桶排序则能解决这个问题

桶排序的”桶“是什么概念？

桶代表的其实是一个区间范围，里面可以承载一个或多个元素，就像一个容器一样。桶排序的第一步就是创建桶，确定区间范围。

算法步骤：

创建桶（设置一个定量的数组当作空桶），确定桶的区间范围；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序（这里排序方法随意，可以使用桶排序进行套娃）；
从不是空的桶里把排好序的数据拼接起

这里找一张图方便大家理解：

紧接着咱们看代码实现

代码：

 1private static void sort(int[] arr) {
 2    if (arr == null || arr.length < 2) {
 3        return;
 4    }
 5    //确定最大值最小值
 6    int max = Integer.MIN_VALUE;
 7    int min = Integer.MAX_VALUE;
 8    for (int value : arr) {
 9        max = Math.max(value, max);
10        min = Math.min(value, min);
11    }
12    //创建桶的个数  这个设置桶的个数和原数组一样大小
13    int size = arr.length;
14    ArrayList<ArrayList<Integer>> lists = new ArrayList<>(size);
15
16    //确定每只桶的范围 这里加1 防止最大值溢出
17    int avg = (max - min) / size + 1;
18    for (int i = 0; i < size; i++) {
19        lists.add(new ArrayList<>());
20    }
21    int d = max - min;
22    for (int value : arr) {
23        //确定该元素放入哪个桶
24        int index = (value - min) / avg;
25        lists.get(index).add(value);
26    }
27    //对每个桶进行排序  这里采用Java原生API
28    for (ArrayList<Integer> list : lists) {
29        Collections.sort(list);
30    }
31    //倒回原数组
32    int i = 0;
33    for (List<Integer> list : lists) {
34        for (Integer num : list) {
35            arr[i++] = num;
36        }
37    }
38}