java模拟基数排序radix sort

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* 模拟基数排序radix sort
*/
public class TestRadixSort {
   public static void sort(int[] arr){
       if (arr.length>1) {
           int i = 0;
           for (int a : arr) {
               while (a >= (int)Math.pow(10, i)) {
                   //Math.pow(a,b)求a的b次幂 返回double类型 强转为int
                   i++;
                   //比如999>=10^2 i++变为3 999<1000 999是三位数
                   //遍历arr确定元素最大是几位数
               }
           }

           for (int j=0;j<i;j++){
               List<Integer> n[] = new ArrayList[10];
               //List<Integer> list = new ArrayList<Integer>(); List是接口 ArrayList是实现类
               //这里new了一个数组 这个数组长度为10 数组类型是引用类型List<>[] 所以每个元素都应该是对象的地址 由于是默认初始化 每个元素都是null 需要遍历给每个位赋值
               for (int m=0;m<10;m++){
                   n[m] = new ArrayList<Integer>();
               }
               for (int k=0;k<arr.length;k++){
                   switch (arr[k]/(int)Math.pow(10,j)%10){
                       //求元素每一位的值 j=0时是求个位的值 arr[k]/10^0%10 即 arr[k]/1%10  j=1时arr[k]/10%10
                       case 0:
                           n[0].add(arr[k]);
                           //n[0]对应当前位的值为0的数组 如果arr[k]的当前位为0则加入n[0]数组中
                           break;
                       case 1:
                           n[1].add(arr[k]);
                           break;
                       case 2:
                           n[2].add(arr[k]);
                           break;
                       case 3:
                           n[3].add(arr[k]);
                           break;
                       case 4:
                           n[4].add(arr[k]);
                           break;
                       case 5:
                           n[5].add(arr[k]);
                           break;
                       case 6:
                           n[6].add(arr[k]);
                           break;
                       case 7:
                           n[7].add(arr[k]);
                           break;
                       case 8:
                           n[8].add(arr[k]);
                           break;
                       default:
                           n[9].add(arr[k]);
                   }
               }
               //这里遍历了arr 所以n[]中存储了arr的所有元素 n[]中元素的总数是arr.length

               int o = 0;
               for (int p =0;p<n[0].size();p++){
                   //ArrayList<>类对象 对象名.size()显示数组的长度 .get(index)返回index位的值
                   //将n[]中的元素遍历存回arr中 当n[0]中没有元素时size=0 p<0false不执行循环
                   arr[o++] = n[0].get(p);
               }

               for (int p =0;p<n[1].size();p++){
                   arr[o++] = n[1].get(p);
               }
               for (int p =0;p<n[2].size();p++){
                   arr[o++] = n[2].get(p);
               }
               for (int p =0;p<n[3].size();p++){
                   arr[o++] = n[3].get(p);
               }
               for (int p =0;p<n[4].size();p++){
                   arr[o++] = n[4].get(p);
               }
               for (int p =0;p<n[5].size();p++){
                   arr[o++] = n[5].get(p);
               }
               for (int p =0;p<n[6].size();p++){
                   arr[o++] = n[6].get(p);
               }
               for (int p =0;p<n[7].size();p++){
                   arr[o++] = n[7].get(p);
               }
               for (int p =0;p<n[8].size();p++){
                   arr[o++] = n[8].get(p);
               }
               for (int p =0;p<n[9].size();p++){
                   arr[o++] = n[9].get(p);
               }
               //再套一层循环的话变成三层循环了 所以穷举了0-9
               //第一遍遍历了个位 arr中数值为一位数的元素们之间的相互顺序都排列好了 因为遍历存回的时候从n[0]开始即个位数值为0的放在数组前排 0之后再放n[1] 0到9依次存回
               //即便一位数的元素之间可能相隔了十位数、百位数等元素 但相对顺序已经确定 之后十位百位每次循环时一位数元素的顺序不会被改变 而中间相隔的元素会随着循环抽出

               System.out.println(Arrays.toString(arr));
           }
       }
   }

   public static void main(String[] args) {
       int[] a = {52,3,87,654,1,9876,123,65,1238,5,654,23,9874,15,9,158,6572,1,64};
       sort(a);
       System.out.println("最终结果：");
       System.out.println(Arrays.toString(a));
       /*
       每一遍循环后的状态：
       [1, 1, 52, 6572, 3, 123, 23, 654, 654, 9874, 64, 65, 5, 15, 9876, 87, 1238, 158, 9]
       第一遍排序了个位 所以一位数的相对顺序都排好了 可以看到64在65前面因为个位4在5前面
       这样即便第二轮比较十位时两个元素都是6 由于个位已经排好了顺序 依顺序先取出64再取出65 然后先存回64再存回65实现了排序

       [1, 1, 3, 5, 9, 15, 123, 23, 1238, 52, 654, 654, 158, 64, 65, 6572, 9874, 9876, 87]
       第二轮比较十位 一位数的十位是0 所以将所有个位数都存进n[0] 由于上一轮已经排好了相对顺序 从n[0]存回a时依然保持了第一轮的顺序 剔除掉了除十位为0的n位数之外的元素
       两位数的相对排序此时也完成了 两位数中间隔着的三位数四位数会在之后几轮中剔除 此时不仅所有两位数的相对排序完成 所有两位数都在一位数的右侧 即一位数和两位数之间的相对顺序也排好了

       [1, 1, 3, 5, 9, 15, 23, 52, 64, 65, 87, 123, 158, 1238, 6572, 654, 654, 9874, 9876]
       第三轮比较百位 将三位数从一位数、两位数中间抽出

       [1, 1, 3, 5, 9, 15, 23, 52, 64, 65, 87, 123, 158, 654, 654, 1238, 6572, 9874, 9876]
       最后一轮比较千位 将四位数抽出 千位不同的按顺序排好了 千位相同的9874和9876在先前比较个位时就已经排好相对顺序了 这一轮9874先放进n[9] 9876再放进去 先存回9874再存回9876完成了排序


       最终结果：
       [1, 1, 3, 5, 9, 15, 23, 52, 64, 65, 87, 123, 158, 654, 654, 1238, 6572, 9874, 9876]

        */
   }
}