排序算法 --- 桶排序

一、排序思想

之前将的计数排序,有些局限性,比如数列最大值和最小值差距不能太大,而且只能排整数。桶排序就对这些局限性做了弥补。桶排序的思想就是每个桶代表一个区间范围,里面可以装若干个元素。然后对这些桶内部进行排序,最后遍历这些桶,那么数列就是有序的了。


欢迎大家关注我的公众号 javawebkf,目前正在慢慢地将简书文章搬到公众号,以后简书和公众号文章将同步更新,且简书上的付费文章在公众号上将免费。


1. 案例:

假如现在有如下数列:

4.5,   0.84,   3.25,   2.18,   0.5
  • 首先创建与元素个数相同的桶,这里就创建5个桶;
  • 最后一个桶让它只包含最大元素,即只包含4.5;
  • 最大数是4.5,最小是0.5,间距是4,除去最后一个桶还有4个桶,所以每个桶间距是1,如下图:

桶排序

  • 然后开始遍历原始数列,把元素放入对应的桶中,如下:

桶排序

  • 对每个桶内部的元素进行排序,如下:

桶排序

  • 最后遍历所有的桶,输出的元素就是有序的了。

桶排序的缺点:如果数据分布不均衡,比如最大值1000,最小值0.5,剩余元素都是零点几的,也就是说最后一个桶放最大元素,其他元素都在第一个桶,这样性能就会下降,并且创建了很多空桶,浪费空间。

二、代码实现

public static void sort(double[] arr){
        if (arr == null || arr.length == 1){
            return;
        }
        int arrNum = arr.length; // 元素个数
        // 拿到最大数和最小数,用来确定间距
        double max = arr[0];
        double min = arr[1];
        for (int i = 0; i < arrNum; i++) {
            max = arr[i] > max ? arr[i] : max;
            min = arr[i] < min ? arr[i] : min;
        }
        double distance = max - min;
        // 创建 arrNum 个桶,桶用linkedList表示,因为linkedList是可重复的,待排数列可能有相同的元素
        List<LinkedList<Double>> buckets = new ArrayList<>();
        for (int i = 0; i < arrNum; i++) {
            buckets.add(new LinkedList<>());
        }
        // 遍历原始数组,将每个元素放到桶中
        for (int i = 0; i < arrNum; i++) {
            // 判断该元素应该放入哪个桶中:当前元素减去最小值,乘以桶数量减一,再除以最大值减最小,得到的值就是桶编号
            int num = (int)((arr[i] - min) * (arrNum - 1) / (max - min));
            buckets.get(num).add(arr[i]);
        }
        // 对每个桶内部进行排序
        for (int i = 0; i < buckets.size(); i++) {
            Collections.sort(buckets.get(i));
        }
        // 最后遍历桶,输出所有元素
        int i = 0;
        for (LinkedList<Double> bucket : buckets){
            for (double num : bucket){
                arr[i++] = num;
            }
        }
}
下一篇
举报

扫码关注云+社区

领取腾讯云代金券