Java 桶排序实现如何判断该放到哪个桶里

heasy3

发布于 2020-08-02 04:52:16

58600

代码可运行

文章被收录于专栏：用户7614879的专栏用户7614879的专栏

运行总次数：0

代码可运行

桶排序类似于计数排序所创建的统计数组，桶排序需要创建若干个桶来协助排序。

每一个桶代表一个区间范围，里面可以承载一个或多个元素。

再分别对每个桶里的元素进行排序最后对桶集合进行遍历输出的就是有序数组

体现了分治思想

 public void bucketSort(int[] array) {
        int size = array.length;
        int max = array[0], min = array[0];
        for (int i = 1; i < size; i++) {
            if (array[i] > max) max = array[i];
            if (array[i] < min) min = array[i];

        }
        int bucketNum = size;//桶的数量
        ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<>());
        }
        for (int i = 0; i < size; i++) {
            //放到哪个桶
            int num = (array[i] - min) * (bucketNum - 1) / (max - min);//重点
            bucketList.get(num).add(array[i]);
        }
        for (int i=0;i<bucketNum;i++){
            Collections.sort(bucketList.get(i));
        }
        int index = 0;
        for (int i=0;i<bucketNum;i++){
            System.out.println("桶"+i+"的元素数量：" + bucketList.get(i).size());
            for (int n:bucketList.get(i)){
                array[index++] = n;
            }
        }
    }