## **基數排序** 基數排序(Radix Sort)是桶排序的擴展，它的基本思想是：將整數按位數切割成不同的數字，然后按每個位數分別比較。 排序過程：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列。 ## **算法描述** 1. 取得數組中的最大數，并取得位數； 2. arr為原始數組，從最低位開始取每個位組成radix數組； 3. 對radix進行計數排序（利用計數排序適用于小范圍數的特點）； ## **穩定性** 通過上面的排序過程，我們可以看到，每一輪映射和收集操作，都保持從左到右的順序進行，如果出現相同的元素，則保持他們在原始數組中的順序。可見，基數排序是一種穩定的排序。 ## **適用場景** 基數排序要求較高，元素必須是整數，整數時長度10W以上，最大值100W以下效率較好，但是基數排序比其他排序好在可以適用字符串，或者其他需要根據多個條件進行排序的場景，例如日期，先排序日，再排序月，最后排序年 ，其它排序算法可是做不了的。 ## **JAVA代碼實現** ``` public abstract class Sorter { public abstract void sort(int[] array); } public class RadixSorter extends Sorter { private int radix; public RadixSorter() { radix = 10; } @Override public void sort(int[] array) { // 數組的第一維表示可能的余數0-radix，第二維表示array中的等于該余數的元素 // 如：十進制123的個位為3，則bucket[3][] = {123} int[][] bucket = new int[radix][array.length]; int distance = getDistance(array); // 表示最大的數有多少位 int temp = 1; int round = 1; // 控制鍵值排序依據在哪一位 while (round <= distance) { // 用來計數：數組counter[i]用來表示該位是i的數的個數 int[] counter = new int[radix]; // 將array中元素分布填充到bucket中，并進行計數 for (int i = 0; i < array.length; i++) { int which = (array[i] / temp) % radix; bucket[which][counter[which]] = array[i]; counter[which]++; } int index = 0; // 根據bucket中收集到的array中的元素，根據統計計數，在array中重新排列 for (int i = 0; i < radix; i++) { if (counter[i] != 0) for (int j = 0; j < counter[i]; j++) { array[index] = bucket[i][j]; index++; } counter[i] = 0; } temp *= radix; round++; } } private int getDistance(int[] array) { int max = computeMax(array); int digits = 0; int temp = max / radix; while(temp != 0) { digits++; temp = temp / radix; } return digits + 1; } private int computeMax(int[] array) { int max = array[0]; for(int i=1; i<array.length; i++) { if(array[i]>max) { max = array[i]; } } return max; } } ```