基本思想
基數排序是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。由于整數也可以表達字符串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用于整數。基數排序可以采用兩種方式：
LSD（Least Significant Digital）：從待排序元素的最右邊開始計算（如果是數字類型，即從最低位個位開始）。MSD（Most Significant Digital）：從待排序元素的最左邊開始計算（如果是數字類型，即從最高位開始）。我們以LSD方式為例，從數組R[1..n]中每個元素的最低位開始處理，假設基數為radix，如果是十進制，則radix=10?；具^程如下所示：
計算R中最大的元素，求得位數最大的元素，最大位數記為distance；對每一位round<=distance，計算R[i] % radix即可得到；將上面計算得到的余數作為bucket編號，每個bucket中可能存放多個數組R的元素；按照bucket編號的順序，收集bucket中元素，就地替換數組R中元素；重復2~4，最終數組R中的元素為有序。算法實現
基數排序算法，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; } }排序過程
假設待排序數組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數組大小為20，我們以該數組為例，最大的數組元素的位數為2，所以需要進行2輪映射（映射到對應的桶中），執行基數排序的具體過程，如下所示：
數組原始順序數組的原始順序，如下圖所示：
數組中存在的相同的元素（同一個待排序的數字出現大于1次），我們使用不同的背景顏色來區分（紅色背景表示第二次出現，靛青色表示第三次出現），如果一個元素只出現過一次，則我們就使用一種固定的顏色（淺綠色）表示。
根據數組元素個位數字將數組中元素映射到對應的桶中（bucket）
我們使用的是十進制，基數（Radix）自然是10，根據數組元素個位數的，應該映射到10個桶中，映射后的結果，如圖所示：
在映射到桶的過程中，從左到右掃描原始數組。因為映射到同一個桶中的元素可能存在多個，最多為整個數組的長度，所以在同一個桶中，要保持進入桶中的元素的先后順序（先進的排在左側，后進的排在右側）。
掃面前面已經映射到各個桶中的元素，滿足這樣的順序：先掃描編號最小的桶，桶中如果存在多個元素，必須按照從左到右的順序。這樣，將得到的數組元素重新分布，得到一個元素位置重新分布的數組，如圖所示：
這時，可以看到元素實際上是按照個位的數字進行了排序，但是基于整個元素來說并不是有序的。
這次映射的原則和過程，與前面類似，不同的是，這次掃描的數組是經過個位數字處理重新分布后的新數組，映射后桶內的狀態，如圖所示：
和前面收集方法類似，得到的數組及其順序，如圖所示：
我們可以看到，經過兩輪映射和收集過程，數組已經變成有序了，排序結束。
算法分析
時間復雜度設待排序的數組R[1..n]，數組中最大的數是d位數，基數為r（如基數為10，即10進制，最大有10種可能，即最多需要10個桶來映射數組元素）。處理一位數，需要將數組元素映射到r個桶中，映射完成后還需要收集，相當于遍歷數組一遍，最多元素書為n，則時間復雜度為O(n+r)。所以，總的時間復雜度為O(d*(n+r))。
空間復雜度設待排序的數組R[1..n]，數組中最大的數是d位數，基數為r。基數排序過程中，用到一個計數器數組，長度為r，還用到一個r*n的二位數組來做為桶，所以空間復雜度為O(r*n)。
排序穩定性通過上面的排序過程，我們可以看到，每一輪映射和收集操作，都保持從左到右的順序進行，如果出現相同的元素，則保持他們在原始數組中的順序。
可見，基數排序是一種穩定的排序。
新聞熱點
疑難解答
