2021-03-08 排序算法之桶排序

思路

网上一张比较清楚的图

image.png

1. 创建桶。
2. 将元素放入桶。（桶之间是有序的）
3. 对桶内元素进行排序。

桶的划分和桶内排序都是可以改动的。
尽量使每个桶的数据均匀，桶内排序尽量高效。

实现

实现的一种算法
1.找出待排序数组中的最大值 max、最小值 min
2.我们使用 动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max- min)/arr.length+1
3.遍历数组 arr，计算每个元素 arr[i] 放的桶
4.每个桶各自排序
5.替换原数组

/**
 * @Author: vividzcs
 * @Date: 2021/3/8 11:50 下午
 */
public class BucketSort {
    public static void main(String[] args) {
        int[] arr = {6,2,9,1,2,0,0};
        bucketSort(arr);
        for (int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    /**
     * 1.找出待排序数组中的最大值 max、最小值 min
     * 2.我们使用 动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max- min)/arr.length+1
     * 3.遍历数组 arr，计算每个元素 arr[i] 放的桶
     * 4.每个桶各自排序
     * 5. 替换原数据
     */
    private static void bucketSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i=0; i<arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        int bucketNum = (max - min) / arr.length + 1;
        List<List<Integer>> list = new ArrayList<>(bucketNum);
        for (int i=0; i<bucketNum; i++) {
            list.add(new ArrayList<>());
        }
        for (int i=0; i<arr.length; i++) {
            int num = (arr[i] - min) / (arr.length);
            list.get(num).add(arr[i]);
        }

        for (int i=0; i<bucketNum; i++) {
            Collections.sort(list.get(i));
        }

        int index = 0;
        for (int i=0; i< list.size(); i++) {
            List<Integer> bucket = list.get(i);
            for (int j=0; j<bucket.size(); j++) {
                arr[index++] = bucket.get(j);
            }
        }
    }
}