[算法]桶排序

介绍

桶排序是分治算法的应用.
桶排序实际上就是把要排序的容器中的数据,分别按照大小跨度
分散在若干个桶中,如果桶中有一个以上的数据,则单独的桶进行
排序,最后把每个桶从最小区间跨度-最大区间跨度遍历,即可得到
有序数组.

缺点

不适合数据分布不均匀的序列中.

思路

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class bucketSort {
    public static void main(String[] args) {
        int[] array = new int[] {20,73,1,9,100,103,8};

        int[] sortedArray = bucketSort(array);

        System.out.println(Arrays.toString(sortedArray));
        System.out.println(Arrays.toString(array));
    }

    public static int[] bucketSort(int[] arr) {
        //1.先找到桶中最大的值和最小的值
        int max = arr[0];
        int min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (min < arr[i]) {
                min = arr[i];
            }
            if (max > arr[i]) {
                max = arr[i];
            }
        }

        //2.求出差值,这两步先忽略为什么这么做,后面会告诉
        int diffValue = max - min;

        //3.初始化桶,有多少个元素我们初始化多少桶,桶我们使用Arraylist来模拟,我们先生成一个装桶的容器也使用Arraylist
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            //上面已经指定泛型,无需再次指定泛型
            bucketList.add(new ArrayList<>());
        }
        //4.把每个元素放入分别放入对应的桶中
        //但是我们需要先求出每个桶的区间,需要怎么求呢?
//        假设数组为{20,17,19,16}
       /*为了保证区间是在最大值和最小值之间,
       * 我们先使用最大值减去最小值,再除以数组长度
       * 既最大值-最小值/arr.length
       * 这样我们就得到了这样的四个桶区间,
       * 每个桶的区间跨度是20-16/arr.length=1
       * 但是我们只是求除了每个统之间的跨度,并没有求出在桶中的位置
       * 假如我们分了四个桶
       * 16-17
       * 17-18
       * 18-19
       * 19-20
       * 桶的索引是0-3
       * {20,17,19,16}
       *
       * 17应该在索引为1的桶中
       * 3代表是整个桶的整体,对应的是min到max的区间
       * 1代表min-17这一所以
       * 1/3=(16-17)/(16-20)
       * (元素[i]-元素[min])/(max-min)=元素在哪个桶/桶的最大数量(arr.length-1)
       * 元素在哪个桶=((元素[i]-元素[min])/(max-min))*桶的最大数量(arr.length-1)
       * 把结果强转成int即可
       * */
        for (int i = 0; i < arr.length; i++) {
            //找到在元素中的那个位置,并添加到相应的桶中
            int index = (int) ((arr[i] - min) * (arr.length - 1) / diffValue);
            bucketList.get(index).add(arr[i]);
        }

        //5.对每个元素大于1的桶进行排序
        for (ArrayList<Integer> integers : bucketList) {
            if (integers.size() > 1) {
                Collections.sort(integers);
            }
        }

        //6.定义新数组,把所有桶进行遍历,然后放入新数组中
        int[] newArr = new int[arr.length];
        int count = 0;
        for (int i = 0; i < bucketList.size(); i++) {
            for (int j = 0; j < bucketList.get(i).size(); j++) {
                newArr[count++] = bucketList.get(i).get(j);
            }
        }
        return newArr;
    }
}

参考自什么是桶排序`