桶排序问题

桶排序问题

基数排序、计数排序都是桶排序。桶排序是一个非基于比较的排序，实际少用

时间复杂度和空间复杂度都是O(N)的稳定排序，

先生成一个给定的数组，用下标表示某个数，改下表对应的值表示出现的次数。

列：给定一个数组，求其排序之后相邻元素的最大值，时间复杂度O(N),基于非比较的排序。

创建一个长度为N+1的桶(0->N)，收集每个桶的最大值和最小值，和是否确定该桶为空，，如果是空桶，则取前一个非空桶的最小值和后一个非空桶的最大值相减。用来否定最大差值一定不来自同一个桶内，而不是用来说明最大差值一定来自非空桶两侧，因为将N个元素划分到N+1个桶中，必有一个桶为空桶。

public class Tong {

    public static int creatArr() {
        // 生成长度随机的数组
        int[] arr = new int[(int) (Math.random() * 100)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 100 - Math.random() * 59);
        }
        int value = getValue(arr);

        return value;
    }


    public static int getValue(int[] arr) {

        if (arr.length < 2 || null == arr) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max);
            min = Math.min(arr[i], min);
        }
        if (max == min) {
            return 0;
        }
        
        int len = arr.length;
        int[] maxArr = new int[len + 1];
        int[] minArr = new int[len + 1];
        boolean[] isNull = new boolean[len + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            index = getIndex(arr[i], len, max, min);
            maxArr[index] = isNull[index] ? Math.max(maxArr[index], arr[i]) : arr[i];
            minArr[index] = isNull[index] ? Math.min(maxArr[index], arr[i]) : arr[i];
            isNull[index] = true;

        }
        
        int res = 0;
        int lastMax = maxArr[0];
        for (int i = 1; i < len + 1; i++) {
            if (isNull[i]) {
                res = Math.max(res, minArr[i] - lastMax);
                lastMax = maxArr[i];
            }
        }


        return res;

    }

    

    public static int getIndex(int num, int length, int max, int min) {
        return (num - min) * length / (max - min);
    }

    public static void main(String[] args) {
        System.out.println(creatArr());
    }

}