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

/**
* 模擬基數(shù)排序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類型 強(qiáng)轉(zhuǎn)為int
? ? ? ? ? ? ? ? ? ?i++;
? ? ? ? ? ? ? ? ? ?//比如999>=10^2 i++變?yōu)? 999<1000 999是三位數(shù)
? ? ? ? ? ? ? ? ? ?//遍歷arr確定元素最大是幾位數(shù)
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}

? ? ? ? ? ?for (int j=0;j<i;j++){
? ? ? ? ? ? ? ?List<Integer> n[] = new ArrayList[10];
? ? ? ? ? ? ? ?//List<Integer> list = new ArrayList<Integer>(); List是接口 ArrayList是實(shí)現(xiàn)類
? ? ? ? ? ? ? ?//這里new了一個(gè)數(shù)組 這個(gè)數(shù)組長度為10 數(shù)組類型是引用類型List<>[] 所以每個(gè)元素都應(yīng)該是對象的地址 由于是默認(rèn)初始化 每個(gè)元素都是null 需要遍歷給每個(gè)位賦值
? ? ? ? ? ? ? ?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時(shí)是求個(gè)位的值 arr[k]/10^0%10 即 arr[k]/1%10 ?j=1時(shí)arr[k]/10%10
? ? ? ? ? ? ? ? ? ? ? ?case 0:
? ? ? ? ? ? ? ? ? ? ? ? ? ?n[0].add(arr[k]);
? ? ? ? ? ? ? ? ? ? ? ? ? ?//n[0]對應(yīng)當(dāng)前位的值為0的數(shù)組 如果arr[k]的當(dāng)前位為0則加入n[0]數(shù)組中
? ? ? ? ? ? ? ? ? ? ? ? ? ?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[]中存儲(chǔ)了arr的所有元素 n[]中元素的總數(shù)是arr.length

? ? ? ? ? ? ? ?int o = 0;
? ? ? ? ? ? ? ?for (int p =0;p<n[0].size();p++){
? ? ? ? ? ? ? ? ? ?//ArrayList<>類對象 對象名.size()顯示數(shù)組的長度 .get(index)返回index位的值
? ? ? ? ? ? ? ? ? ?//將n[]中的元素遍歷存回arr中 當(dāng)n[0]中沒有元素時(shí)size=0 p<0false不執(zhí)行循環(huán)
? ? ? ? ? ? ? ? ? ?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);
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?//再套一層循環(huán)的話變成三層循環(huán)了 所以窮舉了0-9
? ? ? ? ? ? ? ?//第一遍遍歷了個(gè)位 arr中數(shù)值為一位數(shù)的元素們之間的相互順序都排列好了 因?yàn)楸闅v存回的時(shí)候從n[0]開始即個(gè)位數(shù)值為0的放在數(shù)組前排 0之后再放n[1] 0到9依次存回
? ? ? ? ? ? ? ?//即便一位數(shù)的元素之間可能相隔了十位數(shù)、百位數(shù)等元素 但相對順序已經(jīng)確定 之后十位百位每次循環(huán)時(shí)一位數(shù)元素的順序不會(huì)被改變 而中間相隔的元素會(huì)隨著循環(huán)抽出

? ? ? ? ? ? ? ?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("最終結(jié)果：");
? ? ? ?System.out.println(Arrays.toString(a));
? ? ? ?/*
? ? ? ?每一遍循環(huán)后的狀態(tài)：
? ? ? ?[1, 1, 52, 6572, 3, 123, 23, 654, 654, 9874, 64, 65, 5, 15, 9876, 87, 1238, 158, 9]
? ? ? ?第一遍排序了個(gè)位 所以一位數(shù)的相對順序都排好了 可以看到64在65前面因?yàn)閭€(gè)位4在5前面
? ? ? ?這樣即便第二輪比較十位時(shí)兩個(gè)元素都是6 由于個(gè)位已經(jīng)排好了順序 依順序先取出64再取出65 然后先存回64再存回65實(shí)現(xiàn)了排序

? ? ? ?[1, 1, 3, 5, 9, 15, 123, 23, 1238, 52, 654, 654, 158, 64, 65, 6572, 9874, 9876, 87]
? ? ? ?第二輪比較十位 一位數(shù)的十位是0 所以將所有個(gè)位數(shù)都存進(jìn)n[0] 由于上一輪已經(jīng)排好了相對順序 從n[0]存回a時(shí)依然保持了第一輪的順序 剔除掉了除十位為0的n位數(shù)之外的元素
? ? ? ?兩位數(shù)的相對排序此時(shí)也完成了 兩位數(shù)中間隔著的三位數(shù)四位數(shù)會(huì)在之后幾輪中剔除 此時(shí)不僅所有兩位數(shù)的相對排序完成 所有兩位數(shù)都在一位數(shù)的右側(cè) 即一位數(shù)和兩位數(shù)之間的相對順序也排好了

? ? ? ?[1, 1, 3, 5, 9, 15, 23, 52, 64, 65, 87, 123, 158, 1238, 6572, 654, 654, 9874, 9876]
? ? ? ?第三輪比較百位 將三位數(shù)從一位數(shù)、兩位數(shù)中間抽出

? ? ? ?[1, 1, 3, 5, 9, 15, 23, 52, 64, 65, 87, 123, 158, 654, 654, 1238, 6572, 9874, 9876]
? ? ? ?最后一輪比較千位 將四位數(shù)抽出 千位不同的按順序排好了 千位相同的9874和9876在先前比較個(gè)位時(shí)就已經(jīng)排好相對順序了 這一輪9874先放進(jìn)n[9] 9876再放進(jìn)去 先存回9874再存回9876完成了排序


? ? ? ?最終結(jié)果：
? ? ? ?[1, 1, 3, 5, 9, 15, 23, 52, 64, 65, 87, 123, 158, 654, 654, 1238, 6572, 9874, 9876]

? ? ? ? */
? ?}
}