/**
* 模拟基数排序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]
*/
}
}
