[数据结构与算法]十大排序--桶排序

桶排序

介绍

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

步骤

1. 找出待排序数组的最大值和最小值；
2. 跟据数组的最大值和最小值的差值以及桶的大小确定桶的数量；
3. 将数组中的每个元素分配到桶中；
4. 从桶中取出有序元素；

演示

推荐排序算法动态调试、演示网站: https://www.cs.usfca.edu/~galles/visualization/BucketSort.html

图片来源于：https://www.runoob.com/w3cnote/bucket-sort.html

元素分布在桶中：

然后，元素在每个桶中排序：

代码与思想

/**
 * TODO 桶排序
 * 思想： 哈希表
 * @author nanfeng
 * @date 2022/03/19/ 17:44
 */
public class BucketSort {
    public static void main(String[] args) {
        int[] nums = new int[]{711,42,333,6,7555,85,93,24,30,177};
        bucketSort(nums,3);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 桶排序
     *
     * @param nums       待排序数组
     * @param bucketSize 桶大小
     */
    public static void bucketSort(int[] nums,int bucketSize){
        // 最小值、最大值初始化
        int min = nums[0];
        int max = min;
        // 找出最小值、最大值
        for(int i=0;i<nums.length;i++){
            if(min>nums[i]) min = nums[i];
            if(max<nums[i]) max = nums[i];
        }
        // 根据最大值、最小值差值除以桶的大小确定桶的数量
        int bucketCount = (max - min) / bucketSize + 1;
        // 桶由二维数组保存
        int[][] buckets = new int[bucketCount][0];
        for (int i = 0; i < nums.length; i++) {
            // 获取元素在桶中的下标
            int index = (nums[i] - min) / bucketSize;
            // 在桶中放入元素，此处并没有直接将桶初始化为桶大小，而是放一个扩充一个
            buckets[index] = arrayAppend(buckets[index], nums[i]);
        }
        // 对桶内元素进行排序
        for(int i=0;i<buckets.length;i++){
            // 桶内为空
            if (buckets[i].length==0) continue;
            // 因为桶内元素在桶大小的区间内，刚好符合计数排序擅长的方向（相比于比较排序更快）
            // 计数排序可前往本专栏学习
            CountSort.countSort(buckets[i]);
        }
        // 将有序的桶内元素依次取出覆盖到原数组中
        int index = 0;
        for (int[] bucket : buckets) {
            for (int i : bucket) {
                nums[index++] = i;
            }
        }
    }

    /**
     * 数组添加
     *
     * @param nums 待扩展数组
     * @param num  待加入元素
     * @return {@link int[]}
     */
    public static int[] arrayAppend(int[] nums,int num){
        // 扩充数组大小
        int[] newNums = Arrays.copyOf(nums,nums.length+1);
        // 新数组尾部加入
        newNums[newNums.length-1] = num;
        return newNums;
    }
}