排序--桶排序

概念

将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

时间复杂度

• 平均：O(n + k)
• 最好：O(n)
• 最坏：O(n²)

空间复杂度

O(n + k)

稳定性

稳定

要求

• 要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。
• 数据在各个桶之间的分布是比较均匀的。

代码

public class BucketSort implements Sort {

    @Override
    public int[] sort(int[] arr) {
        // 遍历数据，获取数据范围
        // 通常不需要该步骤，比如学分0-100，年龄0-120
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int value : arr) {
            max = Math.max(max, value);
            min = Math.min(min, value);
        }

        // 根据数据范围和数据量计算桶个数
        // 通常不需要该步骤
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketArr.add(new ArrayList<>());
        }

        // 遍历数据，将每个元素放入桶
        for (int value : arr) {
            // 计算数据应放入的桶下标
            int num = (value - min) / (arr.length);
            bucketArr.get(num).add(value);
        }

        // 对每个桶进行排序
        for (ArrayList<Integer> integers : bucketArr) {
            Collections.sort(integers);
        }

        // 依次从桶中取出数据
        int[] result = new int[arr.length];

        int i = 0;
        for (ArrayList<Integer> values : bucketArr) {
            for (Integer value : values) {
                result[i++] = value;
            }
        }

        return result;
    }
}