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

本是古典何须时尚 2023-10-08 21:55 31阅读 0赞

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

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

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

计数排序的思想很简单:员工的年龄(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);
        }