编辑代码

class Main {
	public static void main(String[] args) {
        int[] arr1 = {20,10,5,4,48,12,30,56,76,15,47,68,48,15};
        radixSort(arr1);
        display(arr1);

       
	}
    // 查找数组中的最大值
    public static int findMax(int[] arr){
        int max = arr[0];
        for(int i = 1; i < arr.length; i++){
            if(arr[i] > max){
                max = arr[i];
            }
        }
        return max;
    }
    // 计算最大值一共有几位数
    public static int calBitCount(int max){
        int count = 0;
        while(max > 0){
            count++;
            max = max / 10;
        }
        return count;
    }
    // 获取对应位上的值
    public static int getBitValue(int num,int b){
        for(int i = 0; i<b-1;i++){
            num = num / 10;
        }
        num = num % 10;
        return num;
    }
    public static void display(int[] arr){
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println("");
    }
    public static void radixSort(int[] arr){
        // 1.找出最大值，计算出需要排序的位
        int max = findMax(arr);
        int bitCount = calBitCount(max);
        //对每一位进行排序
        for(int b = 1; b <= bitCount; b++){
            // 创建排序数组
            int radixCount = 10;
            int[] count = new int[radixCount];
            int[] tempArray = new int[arr.length];
            // 统计计数数组下标对应元素个数
            for(int i = 0;i < arr.length; i++){
                int bitValue = getBitValue(arr[i],b);
                count[bitValue]++;
            }
            // 累计算出小于等于计数数组下表对应元素的个数
            for(int c = 1; c < radixCount; c++ ){
                count[c] = count[c] + count[c-1];
            }
             // 利用累加值和临时数组进行排序
            for(int i = arr.length-1; i >= 0; i--){
                int index = getBitValue(arr[i],b);
                tempArray[--count[index]] = arr[i];
            }
            // 临时数组数据拷贝回原数组
            for(int i = 0; i < arr.length; i++){
                arr[i] = tempArray[i];
            }
        }
    }
}