目錄

0. 基數排序由來

1. 基數排序圖解

2. 基數排序代碼

3. 基數排序測試

4. 小結

5. 參考資料

0. 基數排序由來

有一個學生記錄數組，數組元素包含三個字段：系別，班號，班內編號。現在要對這個數組排序，使得系別小的在前，系別相同的班號小的在前，班號相同則班內編號較小的在前。這個排序與一般的排序要求（只對某個關鍵字段排序）不同的是：對多個關鍵字段排序。有2種方法可解決：一種是掃描一遍記錄，將之按系別分組，再對組內記錄按班號分組，然后對組內記錄進行單關鍵字排序；另一種方法是，將這個數組按班內編號排序（班內編號在確定的范圍內），然后再對整個數組按班號排序（班號在確定的范圍內），最后對整個數組按系別排序（系別在確定的范圍內）。第一種方法采取的策略是最高位優先排序。第二種方法采取分步驟按關鍵字類別排序的策略通常稱為基數排序，可以看出基數排序的特點是各關鍵字段的分布是在確定范圍（一般較小）內的。

對單關鍵字排序也可采用多關鍵字排序的思想：將單關鍵字分解成多個關鍵字段，在可控范圍內，不用比較，直接排序。

計算機實現基數排序方式：分配和收集。按關鍵字段將記錄重新分成若各組，再將各個組有序組合成新記錄序列。

1. 基數排序圖解

1.1 基數排序圖示

1） 輔助隊列實現基數排序

?

不足：需要額外利用隊列來輔助排序，存在空間浪費。

2）鏈隊列實現基數排序

?

?

3）基于桶有序的基數排序（也稱計數排序，統計子關鍵字的出現頻率）

考慮一種簡單情況，如果你給一些unsigned char 排序，除了教科書上的很多方法外，還有一種簡單的。可以這樣考慮，試想排一系列的unsigned char, 值從0~ 255 ， 放在 u_char data_array[ARRAY_SIZE] 中，分配一個數組 int membuffer[256]; 用于統計每個元素出現的次數，也就成為了數組的排序結果。

1 for(int i=0;i<256;i++) 2 membuffer[i]=0; 3 for(int i=0;i<ARRAY_SIZE;i++) 4 membuffer[data_array[i]]++;

1.2 基數排序分析

基數排序的優點就是：不用比較，每個關鍵字的范圍確定且一般較小，排序時間復雜度低。但為什么基數排序的應用范圍沒有快速排序那樣廣呢？原因有以下幾點：

1）基數排序一般需要額外的存儲空間：順序隊列實現需要O(n)的元素空間，鏈隊列實現需要O(n+2d)個指針空間，計數實現也需要O(n)的元素空間

2）基數排序的時間復雜度看似O(n)，但它每次排序都是對整個數組的處理，相對快排來講，cache局部性不好。

在我的印象中，基數排序一般出現在面試中，在實際生產環境中還沒有發現采用基數排序。

2.?基數排序代碼

1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 5 // 基于無符號整數的基數排序 6 void radix(int byte, unsigned int N, const unsigned int *source, unsigned int *dest) { 7 unsigned int count[256]; 8 unsigned int index[256]; 9 int i = 0; 10 11 memset(count, 0, sizeof (count)); 12 13 // 統計出現頻率 14 for (i=0; i < N; ++i) { 15 ++count[((source[i])>>(byte*8))&0xff]; // 以一個字節為單位 16 } 17 18 // 為dest下標初始化做準備 19 index[0] = 0; 20 for (i = 1; i < 256; ++i) { 21 index[i] = index[i-1] + count[i-1]; 22 } 23 24 // 數組重排列 25 for (i = 0; i < N; ++i) { 26 dest[index[((source[i])>>(byte*8))&0xff]++] = source[i]; 27 } 28 } 29 30 void radixsort (unsigned int *source, unsigned int *temp, unsigned int N) { 31 radix(0, N, source, temp); 32 radix(1, N, temp, source); 33 radix(2, N, source, temp); 34 radix(3, N, temp, source); 35 } 36 37 38 int main(int argc, char** argv) { 39 unsigned int a[5] = {300, 200, 2,20, 5}; 40 unsigned int len = 5; 41 unsigned int b[5] = {0}; 42 unsigned int i = 0; 43 44 radixsort(a, b, len); 45 for (; i < 5; ++i) { 46 printf("%ld ", a[i]); 47 } 48 49 return 0; 50 }

3.?基數排序測試

1）上節代碼的運行結果如下：

2）網友的性能對比測試：

引用網絡上的測試數據：

今實測性能在n =1024*1000的時候，VC 6 上 release 模式，排序時間：(tick)

n ? ? ? ? ? ? ? ? ? ? ? ? ? Radix Sort ? ? ? ? ? ? ? ? ?STL Sort
100*1024 ? ? ? ? ? ? ?20 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?20
1000*1024 ? ? ? ? ? ?250 ? ? ? ? ? ? ? ? ? ? ? ? ? ?320
4000*1024 ? ? ? ? ? ?991 ? ? ? ? ? ? ? ? ? ? ? ? ? ?1513
10000*1024 ? ? ? ? ?2093 ? ? ? ? ? ? ? ? ? ? ? ? ? 3606

從以上數據可見Radix Sort 的確可能比STL Sort 快，而且，因為Radix Sort時間復雜度小，在更長的時間內表現更為充分。n 從100* 1024增長到10000*1024， 排序時間也從20 增長到2093， 可以看出的確是O(n)的。

4. 小結

基數排序采用多關鍵字的排序思想，由最低位到最高位逐步處理各關鍵字斷序列，達到了O(n)的時間復雜度，但增加了空間復雜度。

基數排序一般適用于已知關鍵字的分布情況，且分布比較集中。計算機實現一般采用分配-收集策略或計數方式（統計各關鍵字的出現頻率）。

5. 參考資料

Radix Sort 的介紹

轉載于:https://www.cnblogs.com/didiaoxiong/p/3259987.html

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的详谈基数排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。