桶排序（Bucket Sort） O(n)

介绍

桶排序相当与计数排序的升级版，和hash的实现一个原理，桶排序的性能和数据分布情况以及桶个数的设定有很大关系。

算法描述

• 初始化一些桶（数组），桶里可以添加多个数值（链表）
• 遍历待排序的序列，得到每个值对应的桶，
• 添加进桶内，并排序
• 遍历所有的桶，取出数据，该序列就是有序序列

动图展示

bucketSort.gif

代码实现

public class BucketSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{27, 6, 27, 42, 23, 15, 38, 50, 35, 14, 40, 28, 29};
        int[] res = bucketSort(arrays);
        print(res);
    }

    private static int[] bucketSort(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int item : arr) {
            min = Math.min(item, min);
            max = Math.max(item, max);
        }
        int bucketSize = 5;
        int bucketCount = Math.floorDiv(max - min, bucketSize) + 1;
        List<List<Integer>> res = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            res.add(new ArrayList<>());
        }
        for (int value : arr) {
            int bucket = Math.floorDiv(value - min, bucketCount);
            List<Integer> list = res.get(bucket);
            list.add(value);
            list.sort(Integer::compareTo);
        }

        int[] result = new int[arr.length];
        int idx = 0;
        for (List<Integer> list : res) {
            for (int i : list) {
                result[idx++] = i;
            }
        }
        return result;
    }

    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }
}