题目：

基数排序是一种基于 “数位” 排序的非比较型整数排序算法，核心思想是：将整数按数位拆分，从最低位（或最高位）开始，依次对每一位进行 “稳定排序”，最终使整体有序。

它的核心逻辑可拆解为 3 个关键点：

一、核心前提：数位分解与进制依赖

基数排序的操作对象是 “有明确数位” 的数（如十进制整数、二进制数），默认以十进制为例：

• 每个数可拆分为个位、十位、百位、千位…… 等数位（如 123 拆分为个位 3、十位 2、百位 1）；
• 排序的轮数 = 待排序数的最大位数（如最大数是 999，则需排 3 轮：个位→十位→百位）。

二、核心操作：逐位稳定排序

对每一位的排序必须是稳定排序（相同数位值的数，排序后相对位置不变），这是基数排序正确的关键 —— 因为高位排序依赖低位已排好的结果。常用的稳定排序方式是「桶排序 / 计数排序」：

1. 准备桶：十进制下，每一位的取值范围是 0~9，因此准备 10 个桶（对应 0~9）；
2. 分配：遍历所有数，按当前处理位的数值，将数放入对应桶中；
3. 收集：按桶的顺序（0→9）将数依次取出，此时数组在当前位上有序；
4. 迭代：对下一位（如个位→十位→百位）重复 “分配 - 收集”，直到所有数位处理完毕。

三、两种遍历方向（LSD vs MSD）

LSD（最低位优先）：从个位到高位，实现简单，适合整数排序。

MSD（最高位优先）：从高位到个位，可提前终止，适合字符串/字典序排序。

举个例子：待排序数组：[123, 45, 7, 987, 23, 567]步骤拆解：

1. 最大位数：3 位（987），需排 3 轮；
2. 第 1 轮：按个位排序
   • 个位值：3（123）、5（45）、7（7）、7（987）、3（23）、7（567）；
   • 分配桶→收集：[123, 23, 45, 7, 987, 567]（个位有序）；
3. 第 2 轮：按十位排序
   • 十位值：2（123）、2（23）、4（45）、0（7）、8（987）、6（567）；
   • 分配桶→收集：[7, 123, 23, 45, 567, 987]（十位 + 个位有序）；
4. 第 3 轮：按百位排序
   • 百位值：0（7）、1（123）、0（23）、0（45）、5（567）、9（987）；
   • 分配桶→收集：[7, 23, 45, 123, 567, 987]（整体有序）。

基数排序不比较数值大小，而是利用 “数位分级” 和 “稳定排序” 实现整体有序。算法展示如下：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int x[] = new int[n];
        for (int i = 0;i<n;i++){
            x[i] = scanner.nextInt();
        }
        HashMap<Integer,ArrayList<Integer>> hashMap = new HashMap<>();// 键：数位值，值：对应元素的列表（避免覆盖）
        int max = x[0];
        for (int i = 1;i<n;i++){
            if (x[i]>max){
                max = x[i];
            }
        }
        String s = max+"";
        int len = s.length();
        // 逐位处理（基数排序核心）
        for (int i = 0;i<len;i++){
            // 1. 清空HashMap，准备当前位的桶
            hashMap.clear();

            // 2. 按当前位的值，将元素存入HashMap（值用列表存，避免覆盖）
            for (int j = 0;j<n;j++){
                int digit = (x[j]/(int)Math.pow(10,i))%10;
                // 若当前数位值对应的列表不存在，新建列表
                if (!hashMap.containsKey(digit)){
                    hashMap.put(digit,new ArrayList<>());
                }
                hashMap.get(digit).add(x[j]);// 将元素加入对应列表
            }

            // 3. 对HashMap的键排序（保证数位顺序）
            ArrayList<Integer> arrayList = new ArrayList<>(hashMap.keySet());
            Collections.sort(arrayList);

            // 4. 按排序后的键，将元素写回原数组（完成当前位的排序）
            int index = 0;
            for (Integer key:arrayList){
                for (Integer value:hashMap.get(key)){
                    x[index++] = value;
                }
            }
        }
        // 输出最终排序结果
        for (int value: x){
            System.out.print(value+" ");
        }
        scan.close();
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] x = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = scanner.nextInt();
        }

        // 基数排序核心逻辑
        int max = x[0];
        for (int num : x) {
            if (num > max) max = num;
        }

        // 逐位处理（个位、十位、百位...）
        for (int exp = 1; max / exp > 0; exp *= 10) {
            // 准备10个桶（对应0-9）
            ArrayList<Integer>[] buckets = new ArrayList[10];
            for (int i = 0; i < 10; i++) {
                buckets[i] = new ArrayList<>();
            }

            // 按当前位的值放入对应桶
            for (int num : x) {
                int digit = (num / exp) % 10;
                buckets[digit].add(num);
            }

            // 从桶中收集元素，更新原数组
            int index = 0;
            for (ArrayList<Integer> bucket : buckets) {
                for (int num : bucket) {
                    x[index++] = num;
                }
            }
        }

        // 输出排序后的数组
        for (int num : x) {
            System.out.print(num + " ");
        }
        scan.close();
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++) {
            arr[i]=scan.nextInt();
        }
        radixsort(arr);
        for(int i=0;i<n;i++) {
            System.out.print(arr[i]+" ");
        }
        scan.close();
    }
     public static void radixsort(int[] arr) {
        if(arr==null||arr.length==0)return;
        int max=arr[0];
        for(int i=0;i<arr.length;i++)
            max=arr[i]>max?max=arr[i]:max;
        int length=new String(max+"").length();//第一步求出最大值的长度
        int temp=1;//利用temp来求各个位的值
        for(int j=0;j<length;j++) {//多少位循环多少次
            int[] account=new int[10];//每一位有十个数，即0,1,2....9
            int[][] newarr=new int[account.length][arr.length];//创建二维数组数组
            for(int t=0;t<arr.length;t++) {//对当前位数进行排序
                int s=(arr[t]/temp)%10;
                newarr[s][account[s]]=arr[t];
                account[s]++;
            }
            temp*=10;//本次求完下一次循环则求更高一位
            int sum=0;
            for(int g=0;g<account.length;g++) {//赋值给原数组
                for(int g1=0;g1<account[g];g1++) {//注意g1结束条件
                    arr[sum++]=newarr[g][g1];
                }
            }
        }
    }
}