一、排序思想

基數(shù)排序是桶排序的擴(kuò)展，它將所有待排序的數(shù)值統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的前面補(bǔ)0，然后從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成后，待排序列就有序了。

1. 案例：

現(xiàn)有如下待排序列：

53    3    542    748    14    214

然后假如有如下10個(gè)桶(一維數(shù)組)，編號從0到9：

• 第一輪排序：將每個(gè)元素的個(gè)位數(shù)取出，然后放到對應(yīng)編號的桶里。比如第一個(gè)元素53，個(gè)位數(shù)是3，所以放在下標(biāo)為3的桶里。一輪下來，情況如下：

第一輪結(jié)束后，按照桶下標(biāo)順序，依次取出各桶中數(shù)據(jù)，放回原數(shù)組，所以原數(shù)組就變成了：

542    53    3    14    214    748

• 第二輪：將每個(gè)元素的十位取出(沒有十位的就是0)，然后放到對應(yīng)編號的桶里。比如第一個(gè)元素542，十位是4，所以放到下標(biāo)為4的桶里。一輪下來，情況如下：

第二輪結(jié)束后，按照桶下標(biāo)順序，依次取出桶中數(shù)據(jù)，放回原數(shù)組，所以原數(shù)組就變成了：

3    14    214    542    748    53

• 第三輪：將每個(gè)元素的百位取出(沒有百位的就是0)，然后放到對應(yīng)編號的桶里。比如第一個(gè)元素3，百位是0，所以放到下標(biāo)為0的桶里。一輪下來，情況如下：

第三輪結(jié)束后，按照桶下標(biāo)順序，依次取出桶中數(shù)據(jù)，放回原數(shù)組，所以原數(shù)組就變成了：

3    14    53    214    542    748    

此時(shí)數(shù)組就是有序的了。總共要進(jìn)行幾輪呢？就是數(shù)組中最大數(shù)有多少位，就要進(jìn)行幾輪。通過這些分析大家發(fā)現(xiàn)啥沒有？每一輪的排序，就是對0到9數(shù)字排序，那豈不是很適合用計(jì)數(shù)排序？沒錯(cuò)，就是這樣，所以，基數(shù)排序中，我們要做的就是每一輪都用計(jì)數(shù)排序就好了。

二、代碼實(shí)現(xiàn)

以下代碼就是基于計(jì)數(shù)排序?qū)崿F(xiàn)的，網(wǎng)上的一些基數(shù)排序教程可能會用二維數(shù)組來表示桶，這樣容易理解，但是非常浪費(fèi)空間。

public static void radixSort(int[] arr) {
 if (arr == null || arr.length == 1) {
  return;
 }
 // 1. 先求數(shù)組中最大數(shù)的位數(shù)
 int max = arr[0];
 for(int i=1; i<arr.length; i++) {
  max = arr[i] > max ? arr[i] : max;
 }
 int maxLength = (max + "").length();
 // 2. 定義一個(gè)用來接收每一輪排序結(jié)果的數(shù)組
 int[] result = new int[arr.length];
 // 3. 定義一個(gè)長度為數(shù)據(jù)范圍的數(shù)組，每個(gè)數(shù)各數(shù)位只可能是0到9，所以數(shù)組長度為10
 int[] count = new int[10];
 // 4. 循環(huán)進(jìn)行排序
 for(int i=0; i<maxLength; i++) {
  // 5. 第一輪求個(gè)位，第二輪求十位……，求個(gè)位：num / 1 % 10，求百位：num / 10 % 10……
  int division = (int)Math.pow(10, i); // 求10的次方
  // 從這里開始其實(shí)就是計(jì)數(shù)排序
  for(int j=0; j<arr.length; j++) {
   int num = arr[j] / division % 10;
   // num就是數(shù)組下標(biāo)值，然后該下標(biāo)對應(yīng)的元素值加1。count數(shù)組下標(biāo)和對應(yīng)的值就表示該數(shù)出現(xiàn)了多少次
   count[num] ++;
  }
  // 6. 對count進(jìn)行變形，使其變成穩(wěn)定的
  for(int x=1; x<count.length; x++) {
   count[x] += count[x-1];
  }
  // 7. 逆序遍歷原數(shù)組
  for(int y=arr.length-1; y>=0; y--) {
   int num = arr[y] / division % 10;
   result[count[num] - 1] = arr[y];
   count[num]--;
  }
  // 8. 拷貝result到原數(shù)組
  System.arraycopy(result, 0, arr, 0, arr.length);
  // 9. 清空count，進(jìn)行下一輪的計(jì)數(shù)
  Arrays.fill(count, 0);
 }
}