百度：
基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort）畦攘，又稱“桶子法”（bucket sort）或bin sort霸妹，顧名思義，它是透過鍵值的部份資訊知押，將要排序的元素分配至某些“桶”中叹螟，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序台盯，其時間復(fù)雜度為O (nlog(r)m)罢绽，其中r為所采取的基數(shù)，而m為堆數(shù)爷恳，在某些時候有缆，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。
理解：
把一個待排序的數(shù)組按照從個位温亲、十位......進(jìn)行分類棚壁，再按每次分類從0-9(個位、十位......)進(jìn)行排序栈虚，依次進(jìn)行袖外，直到數(shù)組中最大數(shù)的位數(shù)排序完。
步驟：
- 先找出數(shù)組中最大數(shù)魂务，求出位數(shù)曼验，即需要分配的次數(shù)。
- 定義一個二維的臨時數(shù)組粘姜，第一維用來存放0-9的正在分配的類別鬓照，長度為10，第二維用來從數(shù)組中提取出來的數(shù)孤紧，因?yàn)樵诜峙淝笆遣恢?-9各自有多少數(shù)豺裆，所以定義第二維的長度為數(shù)組的長度。
- 定義一個長度為10的數(shù)組号显，用來存放每次分配到二維數(shù)組時臭猜，每個維度的長度，作為下次同樣類別存放的下標(biāo)押蚤。
- 根據(jù)求出的分配次數(shù)進(jìn)行for循環(huán)遍歷誊册，此時需要在定義一個變量n腮考，初始為1，用來根據(jù)每次遍歷分別類乘于10(比如第一次為1帅戒，恕稠、1%10得到個位數(shù)，依次類推)。
- 將得到的位數(shù)作為二維數(shù)組的第一維下標(biāo)，第二維下標(biāo)為上面的長度為10數(shù)組對應(yīng)位數(shù)的值偎肃，用來存放當(dāng)前判斷的數(shù)字煞烫。
- 定義一個變量 index浑此，用來記錄取得到的數(shù)字要存放的位置，存放后的數(shù)組將覆蓋原來要分配的數(shù)組滞详。
- 使用兩個for循環(huán)凛俱，用來取出二維數(shù)組里記錄的數(shù)組。
- 當(dāng)分配完一個類別后料饥，要將記錄數(shù)組長度的數(shù)組用到的下標(biāo)歸為0蒲犬，用于下次的使用。
演示：
image.png
Jvav代碼：
package com.company;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = new int[]{5, 45, 87, 32, 9, 7, 159, 324, 4, 107, 69,58};
Main.base(arr);
System.out.println(Arrays.toString(arr));
}
private static void base(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
//計(jì)算最大數(shù)字是幾位數(shù)
int count = (max + "").length();
//用來臨時存放數(shù)據(jù)的數(shù)組
int[][] temp = new int[10][arr.length];
//用于記錄在temp中相應(yīng)的數(shù)組中存放數(shù)字的數(shù)量
int[] counts = new int[10];
//根據(jù)最長長度的數(shù)決定比較次數(shù)
for (int j = 0, n = 1; j < count; j++,n *= 10) {
//把每個數(shù)字分別計(jì)算余數(shù)
for (int d = 0;d<arr.length;d++){
//計(jì)算余數(shù)
int yu = arr[d]/n%10;
//把當(dāng)前遍歷的數(shù)字存放在指定位置的數(shù)組中
temp[yu][counts[yu]] = arr[d];
//記錄數(shù)字
counts[yu]++;
}
//記錄取出元素要放在原數(shù)組的位置
int index = 0;
//把數(shù)組從二維數(shù)組取出來
for (int k = 0;k<counts.length;k++){
//判斷記錄的數(shù)組是否有記錄
if (counts[k]!=0){
//若有 則以記錄該數(shù)組下標(biāo)對應(yīng)值為當(dāng)前位數(shù)的數(shù)量
for (int l =0;l<counts[k];l++){
//取出元素
arr[index]=temp[k][l];
//移動下標(biāo)
index++;
}
//遍歷完岸啡，清空原叮，下個位數(shù)記錄需要
counts[k]=0;
}
}
}
}
}
