Java-桶排序(计数排序&基数排序)-蒲公英云

Java-桶排序(计数排序&基数排序)

桶排序是非基于比较排序的

计数排序(非负十进制):先准备十个队列然后按个位数字进桶

桶排序是一种思想:一个坑好几个萝卜

计数排序的思想很简单:员工的年龄(18-35),那就创建(35-18+1)个桶,然后遍历员工年龄的数组放在对应的桶中然后再输出就可以了.

public static void radixSort(int [] arr) {
        if(arr==null||arr.length<2) {
            return;
        }
        radixSort(arr,0,arr.length-1,maxbits(arr));
    }
    public static int maxbits(int [] arr) {
        int max = Integer.MIN_VALUE;
        for(int i = 0;i<arr.length;i++) {
            max = Math.max(max,arr[i]);
        }
        int count = 0;
        while(max!=0) {
            max/=10;
            count++;
        }
        return count;
    }
    public static int getbits(int num,int bitnum) {
        for(int i = 1;i<=bitnum-1;i++) {
            num = num/10;
        }
        return num%10;
    }
    public static void radixSort(int [] arr,int L,int R,int digit) {
        int radix = 10;
        int [] help = new int [R-L+1];
        int i = 0;
        int j = 0;
        for(int d = 1;d<=digit;d++) {
            int [] count = new int [radix];
            for(i = L; i <= R; i++) {
                j = getbits(arr[i], d);
                count[j]++;
            }
            for(i = 1;i<radix;i++) {
                count[i] += count[i-1];
            }
            for(i = R;i>=L;i--) {
                j = getbits(arr[i], d); 
                help[count[j]-1] = arr[i];
                count[j]--;
            }
            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = help[j];
            }
        }
    }
    public static void main(String[] args) {
       int [] arr = {1,3,5,7,9,2,4,6,8,10};
       radixSort(arr);
       System.out.println(Arrays.toString(arr));
    }

基数排序的原理并不复杂有一批数,先按个位数字大小排序,然后十位…….

举个例子 {11,1,18,4,27,635,621,55,9}这坨数

首先按第一位排: 11,1,621,4,635,55,27,18,9

然后在此基础上用第二位排: 1,4,9,11,18,621,27,635,55

在此基础上用第三位排:1,4,9,11,18,27,55,621,635

这个原理是怎么回事呢先用小位数上的排序但是高位数上的数字对这个数的大小影响更大所以再在此基础上对其排序

代码实现为了减少空间的消耗所以看起来很复杂….

男♂以理解的部分其实只有41行到48行的部分一个是累加一个是倒序放置在代码注释里面已经给出了(同样很难理解的)解释

public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxbits(arr));
    }
    public static int maxbits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }
    // arr[l..r]排序  ,  digit
    // l..r    3 56 17 100    3
    public static void radixSort(int[] arr, int L, int R, int digit) {
        final int radix = 10;
        int i = 0, j = 0;
        // 有多少个数准备多少个辅助空间
        int[] help = new int[R - L + 1];
        for (int d = 1; d <= digit; d++) { // 有多少位就进出几次
            // 10个空间
            // count[0] 当前位(d位)是0的数字有多少个
            // count[1] 当前位(d位)是(0和1)的数字有多少个
            // count[2] 当前位(d位)是(0、1和2)的数字有多少个
            // count[i] 当前位(d位)是(0~i)的数字有多少个
            int[] count = new int[radix]; // count[0..9]
            for (i = L; i <= R; i++) {
                // 103  1   3
                // 209  1   9
                j = getDigit(arr[i], d);
                count[j]++;
            }//计算d位是j的数有多少个 计数排序啊
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];//累加上去 当前位是i~0的有多少个
            }//意义就是下面的arr[i]它该放在第几个
            for (i = R; i >= L; i--) {//倒序放置 是在上一次(前一位)排序基础上再进行排序 算是计数排序的核心
                j = getDigit(arr[i], d);
                help[count[j] - 1] = arr[i];//
                count[j]--;
            }
            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = help[j];//把help中的值赋给arr
            }
        }
    }
    public static int getDigit(int x, int d) {
        return ((x / ((int) Math.pow(10, d - 1))) % 10);
    }