北大青鳥(niǎo)北京通州學(xué)術(shù)部提供：
北大青鳥(niǎo)北京，北大青鳥(niǎo)學(xué)校學(xué)術(shù)部老師講解：什么是基數(shù)排序？
北大青鳥(niǎo)北京，北大青鳥(niǎo)學(xué)校解答：基數(shù)排序(radix sort）是屬于“分配式排序”（distribution sort），基數(shù)排序法又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過(guò)鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的比較性排序法。
效率分析：
時(shí)間效率：設(shè)待排序列為n個(gè)記錄，d個(gè)關(guān)鍵碼，關(guān)鍵碼的取值范圍為radix，則進(jìn)行鏈?zhǔn)交鶖?shù)排序的時(shí)間復(fù)雜度為O(d(n+radix))，其中，一趟分配時(shí)間復(fù)雜度為O(n)，一趟收集時(shí)間復(fù)雜度為O(n)，共進(jìn)行d趟分配和收集。 空間效率：需要2*radix個(gè)指向隊(duì)列的輔助空間，以及用于靜態(tài)鏈表的n個(gè)指針。（北大青鳥(niǎo)北京校區(qū)）
實(shí)現(xiàn)方法：
最高位優(yōu)先(Most Significant Digit first)法，簡(jiǎn)稱MSD法：先按k1排序分組，同一組中記錄，關(guān)鍵碼k1相等，再對(duì)各組按k2排序分成子組，之后，對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd對(duì)各子組排序后。再將各組連接起來(lái)，便得到一個(gè)有序序列。 最低位優(yōu)先(Least Significant Digit first)法，簡(jiǎn)稱LSD法：先從kd開(kāi)始排序，再對(duì)kd-1進(jìn)行排序，依次重復(fù)，直到對(duì)k1排序后便得到一個(gè)有序序列。（北大青鳥(niǎo)北京校區(qū)）
代碼實(shí)現(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. } （北大青鳥(niǎo)北京校區(qū)）
北大青鳥(niǎo)北京校區(qū)老師提示：基數(shù)排序一般僅是用于記錄的關(guān)鍵字為整數(shù)類型的情況。
在已介紹的各種內(nèi)部排序方法中，就所需要的計(jì)算時(shí)間來(lái)看，快速排序、歸并排序、堆排序是很好的方法。但是，歸并排序需要大小為n的輔助空間，快速排序需要一個(gè)棧。除了快速排序、堆排序、選擇排序、希爾排序不穩(wěn)定外，其它排序方法都是穩(wěn)定的。
北大青鳥(niǎo)北京校區(qū)老師提示：評(píng)價(jià)一個(gè)排序算法性能好壞的主要標(biāo)準(zhǔn)是它所需的計(jì)算時(shí)間和存儲(chǔ)空間。影響計(jì)算時(shí)間的兩個(gè)重要因素是比較關(guān)鍵字的次數(shù)和記錄的移動(dòng)次數(shù)。在實(shí)際應(yīng)用中，究竟應(yīng)該選用何種排序方法，取決于具體的應(yīng)用和機(jī)器條件。
