编辑代码

import java.util.ArrayList;  
import java.util.HashMap;  
import java.util.List;  
import java.util.Map;  
  
public class RadixSort {  
    public static void main(String[] args) {  
        int[] nums = {170, 45, 75, 90, 802, 24, 2, 66};  
        int[] sortedNums = radixSort(nums);  
        for (int num : sortedNums) {  
            System.out.print(num + " ");  
        }  
    }  
  
    public static int[] radixSort(int[] nums) {  
        // 获取最大值，以确定最大位数  
        int maxNum = getMaxNum(nums);  
        int maxDigits = getMaxDigits(maxNum);  
  
        // 创建桶和散列表  
        List<List<Integer>> buckets = new ArrayList<>();  
        Map<Integer, Integer> hashMap = new HashMap<>();  
        for (int i = 0; i < 10; i++) {  
            buckets.add(new ArrayList<>());  
        }  
  
        // 对每一位进行排序  
        for (int i = 0; i < maxDigits; i++) {  
            // 将每个数放入对应的桶中  
            for (int num : nums) {  
                int digit = getDigit(num, i);  
                buckets.get(digit).add(num);  
                hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);  
            }  
            // 从桶中取出数，放回原数组  
            int index = 0;  
            for (List<Integer> bucket : buckets) {  
                for (int num : bucket) {  
                    nums[index++] = num;  
                    int count = hashMap.get(num);  
                    if (count == 1) {  
                        hashMap.remove(num);  
                    } else {  
                        hashMap.put(num, count - 1);  
                    }  
                }  
                bucket.clear();  
            }  
        }  
        return nums;  
    }  
  
    // 获取数组中的最大值  
    private static int getMaxNum(int[] nums) {  
        int maxNum = nums[0];  
        for (int num : nums) {  
            if (num > maxNum) {  
                maxNum = num;  
            }  
        }  
        return maxNum;  
    }  
  
    // 获取一个数的位数  
    private static int getMaxDigits(int num) {  
        int digits = 0;  
        while (num > 0) {  
            digits++;  
            num /= 10;  
        }  
        return digits;  
    }  
  
    // 获取一个数的某一位上的数字  
    private static int getDigit(int num, int digit) {  
        while (digit > 0) {  
            num /= 10;  
            digit--;  
        }  
        return num % 10;  
    }  
}