经典排序思想——桶排序

--write by zhuwx 2019-06-24 20:58:04 +0800 CST

点击量:7

时间复杂度:O(N)
额外空间复杂度:O(N)
是否可实现稳定性:否

思路:

桶排序的思路:首先找到数组中的最大值,然后新建一个数组,bucket 此数组的长度是数组最大值+1,其实新建的这个数组中的下标值就是原数组的数据值,这里为什么长度是数组最大值加一呢
注意*:是因为比如数组最大值是9,然后如果你设置bucket数组的长度为9,那么他的下标最大值就是8,那么原数组的9就没有桶存了
好了继续,找到最大值后,开始遍历原数组,把原数组的数据加入bucket的下表中,bucket[i],每当有1个i bucket[i]的值就加一, 然后已经装入桶后, 遍历桶,如果bucket[j]位置–>0就说明此下标有数据,也就是说,此下标在原数组里有这个值, 然后排序 就是从大到小了 arr[i++]=j;

代码:

  public static void bucketSort(int[] arr){
        if (arr==null||arr.length<2){
            return;
        }
        //常用写法
        int max = Integer.MIN_VALUE;
        for (int i =0;i<arr.length;i++){
            max = Math.max(max,arr[i]);
        }

        int[] bucket = new int[max+1];

        for (int i =0;i<arr.length;i++){
            //桶数组此下标有数据,数值就加一
            bucket[arr[i]]++;
        }

        int i = 0;

        for (int j = 0;j<bucket.length;j++){
            while (bucket[j]-->0){
                arr[i++]=j;
            }
        }
   }

利用桶排序思想做题:

荷兰国旗类问题:

题目要求:求一个数组排序后相邻值的最大差值 排序的时间复杂度为O(n)

思路:

思路:找出数组中的最小值和最大值,一共有n个数就创建n+1个桶,把最小值放入第一个桶,最大值放到最后一个桶, 然后每一个桶都有一个存值的范围 范围的求法 (max-min)/桶的个数
比如 1 4 3 2 范围就是1-1.6 1.6-2.2 2.2-2.8 2.8-3.4 3.4-4
然后五个桶的编号从0开始 因为存桶的数组的下标从0开始,然后开始装数 ((num – min) * len / (max – min)); 正常理解应该*(len+1)但是因为桶的下标从0开始 所以 *len
最重要的原理是 用后一个桶的最小值减去上一个桶的最大值, 找出这样的最大值 就是最大差值,因为一个桶内的差值肯定不超过桶的范围

代码:
 public static int maxGap(int[] nums){

        if (nums==null||nums.length<2){
            return 0;
        }
        //通常写法
        int len = nums.length;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0;i<len;i++){
            min = Math.min(min,nums[i]);
            max = Math.max(max,nums[i]);
        }
        //最小值最大值相等就返回0
        if (max==min){
            return 0;
        }
        //桶的编号
        int bid = 0;
        //三个平型数组,记录同一编号,即一个桶的信息
        int[] mins = new int[len+1];
        int[] maxs = new int[len+1];
        boolean[] hasNum = new boolean[len + 1];
        for (int i =0;i<len;i++){
            //数组值装桶
            bid = bucket(nums[i], len, min, max);
            //每次比较桶内的最小值
            mins[bid] = hasNum[bid] ? Math.min(mins[bid],nums[i]) : nums[i];
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid],nums[i]) : nums[i];
            hasNum[bid] = true;
        }

        int res = 0;
        //第一个桶的最大值
        int lastMax = maxs[0];
        int i = 1;
        //小于等于len是因为比如三个数 四个桶,最大最小数放在第一个最后一个同,这样就能把每一个桶遍历到
        for (;i<=len;i++){
            if (hasNum[i]){
                res = Math.max(res,mins[i]-lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }

    public static int bucket(long num, long len, long min, long max) {
        return (int) ((num - min) * len / (max - min));
    }

作者:一凡呀
链接:https://www.jianshu.com/p/e6ba35133375
來源:简书