编辑代码

class Main {
	
    public static int findMax(int[] arr) {
        int max = 0;
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }

    //输入50，返回2
    //输入100，返回3 
    public static int calBitCount(int max) {
        int count = 0;
        while(max >= 1) {
            max /= 10;
            count++;
        }
        return count;
    }

    // 输入（50，0），返回0
    // 输入（50，1），返回5 
    public static int getBitValue (int value, int bit) {
        if(bit == 0) {
            return value%10;
        }
        if(bit == 1) {
            return value/10%10;
        }
        if(bit == 2) {
            return value/100;
        }
        return 0;
    }


    public static void radixSort(int[] arr) {
	
	    //1. 找出最大值，计算出需要排序的位 
	    int max = findMax(arr);
	    int bitCount = calBitCount(max);
	
	
	    //2. 创建排序数组
	    int radixCount = 10;
	    int[] count = new int[radixCount];
	    int[] tempArray = new int[arr.length];
	
	    //3. 对每一位进行排序 
	    for (int b = 0; b < bitCount; ++b) {
		    //3.1 清空排序数组,把每个值赋予0 
		    for(int i = 0; i < radixCount; ++i) {
                count[i] = 0;
            }   

            //3.2 统计计数数组下标对应元素个数
            for (int i = 0; i < arr.length; ++i) {
                int bitValue = getBitValue(arr[i], b);
                count[bitValue]++;
            } 
		
            //3.3 累计算出小于等于计数数组下标对应元素的个数 
            for (int c = 1; c < radixCount; ++c) {
                count[c] += count[c-1];
            }
            
            //3.4 利用累加值和临时数组对对应的位进行排序
            for (int i = arr.length - 1; i >= 0; --i) {
                int bitValue = getBitValue(arr[i], b);
                tempArray[--count[bitValue]] = arr[i];
            } 
            
            // 3.5 临时数组数据拷贝回原数组
            for(int i = 0; i < arr.length; ++i) {
                arr[i] = tempArray[i];
            } 
        } 
    }

    public static void printArray(int[] arr) {
        for(int i = 0; i < arr.length; ++i) {
            System.out.print(arr[i] + " "); 
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {149, 34, 72, 3, 66, 28, 14};
        printArray(arr);
        radixSort(arr);
        System.out.println(); 
        printArray(arr);
	}
}