桶排序 BucketSort

桶排序

桶排序是将数组分散到有限的桶中，然后每个桶再分别排序，而每个桶的排序又可以使用其他排序方式进行排序，可以是桶排序也可以是其他排序。一句话就是: 划分多个范围相同的区间，每个子区间自排序最后合并。

桶的大小可以随便定，其实我们完全可以把桶固定在一 个数量，根据数组的大小来确定，也可以自己定，比如3个或者5个7个等，桶的大小确 定之后，下步就需要把数组中的值一一存放到桶里，小的值就会放到前面的桶里，大 的值就会放到后面的桶里，中间的值就会放到中间的桶里，然后再分别对每个桶进行单 独排序，最后再把所有桶的数据都合并到一起就会得到排序好的数组。

例子 : 一个数组{29,25,21,3,9,49,37,43}

元素分布在桶中：

元素在每个桶中排序：

?视频解析 :

这里给个视频 :??基础算法-217-排序算法-桶排序-改进_哔哩哔哩_bilibili

案例代码 :

    public static void main(String[] args) {
        //分10个桶
        int[] arr = {10, 78, 65, 32, 21, 89, 13, 54, 7, 3};
        sort(arr);
    }

    public static void sort(int[] arr) {
        List<List<Integer>> list = new ArrayList<>(10);

        //创建每个桶
        for (int i = 0; i < 10; i++) {
            list.add(new ArrayList<>());
        }
        //往桶里添加元素
        for (int i = 0; i < arr.length; i++) {
            list.get(arr[i] / 10).add(arr[i]);
        }
        
        int n = 0;
        for (int i = 0; i < 10; i++) {
            //排序
            List<Integer> integers = list.get(i).stream().sorted().collect(Collectors.toList());
            for (Integer integer : integers) {
                arr[n++] = integer;
            }
        }
        
        //打印
        for (int i= 0;i < arr.length;i++){
            System.out.print(arr[i] + " ");
        }
    }

代码 :

    public static void main(String[] args) {
        //int[] arr = {10, 78, 65, 32, 21, 89, 13, 54, 7, 3};
        //sort(arr);
        int[] brr = {0, 1, 7, 8, 9, 10};
        Tsort(brr,3);
    }
    
    //range桶中存放的元素个数
    public static void Tsort(int[] arr, int range) {
        //最大值 最小值
        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 count = (max - min) / range + 1;
        List<List<Integer>> list = new ArrayList<>(count);
        for (int i = 0; i < count; i++) {
            list.add(new ArrayList<>());
        }
        //存放数据
        for (int i = 0; i < arr.length; i++) {
            list.get((arr[i] - min) / range).add(arr[i]);
        }

        //存到数组中
        int n = 0;
        for (int i = 0; i < count; i++) {
            List<Integer> integers = list.get(i).stream().sorted().collect(Collectors.toList());
            for (Integer integer : integers) {
                arr[n++] = integer;
            }
        }

        //打印
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }