北大青鳥北京通州學術(shù)部提供：
北大青鳥北京，北大青鳥學校學術(shù)部老師講解：什么是基數(shù)排序？
北大青鳥北京，北大青鳥學校解答：基數(shù)排序(radix sort）是屬于“分配式排序”（distribution sort），基數(shù)排序法又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時候，基數(shù)排序法的效率高于其它的比較性排序法。
效率分析：
時間效率：設待排序列為n個記錄，d個關(guān)鍵碼，關(guān)鍵碼的取值范圍為radix，則進行鏈式基數(shù)排序的時間復雜度為O(d(n+radix))，其中，一趟分配時間復雜度為O(n)，一趟收集時間復雜度為O(n)，共進行d趟分配和收集。 空間效率：需要2*radix個指向隊列的輔助空間，以及用于靜態(tài)鏈表的n個指針。（北大青鳥北京校區(qū)）
實現(xiàn)方法：
最高位優(yōu)先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關(guān)鍵碼k1相等，再對各組按k2排序分成子組，之后，對后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd對各子組排序后。再將各組連接起來，便得到一個有序序列。 最低位優(yōu)先(Least Significant Digit first)法，簡稱LSD法：先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序后便得到一個有序序列。（北大青鳥北京校區(qū)）
代碼實現(xiàn)：
1. public class RadixSort {
2. public static void sort(int[] number, int d) {
3. int k=0;
4. int n=1;
5. int m=1;
6. int[][] temp = new int[number.length][number.length];
7. int[] order = new int[number.length];
8. while(m <= d) {
9. for(int i = 0; i < number.length; i++) {
10. int lsd = ((number[i] / n) % 10);
11. temp[lsd][order[lsd]] = number[i];
12. order[lsd]++;
13. }
14. for(int i = 0; i < d; i++) {
15. if(order[i] != 0)
16. for(int j = 0; j < order[i]; j++) {
17. number[k] = temp[i][j];
18. k++;
19. }
20. order[i] = 0;
21. }
22. n *= 10;
23. k = 0;
24. m++;
25. }
26. }
27. public static void main(String[] args) {
28. int[] data =
29. {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
30. RadixSort.sort(data, 10);
31. for(int i = 0; i < data.length; i++) {
32. System.out.print(data[i] + " ");
33. }
34. } （北大青鳥北京校區(qū)）
北大青鳥北京校區(qū)老師提示：基數(shù)排序一般僅是用于記錄的關(guān)鍵字為整數(shù)類型的情況。
在已介紹的各種內(nèi)部排序方法中，就所需要的計算時間來看，快速排序、歸并排序、堆排序是很好的方法。但是，歸并排序需要大小為n的輔助空間，快速排序需要一個棧。除了快速排序、堆排序、選擇排序、希爾排序不穩(wěn)定外，其它排序方法都是穩(wěn)定的。
北大青鳥北京校區(qū)老師提示：評價一個排序算法性能好壞的主要標準是它所需的計算時間和存儲空間。影響計算時間的兩個重要因素是比較關(guān)鍵字的次數(shù)和記錄的移動次數(shù)。在實際應用中，究竟應該選用何種排序方法，取決于具體的應用和機器條件。
