排序 - 分配排序 - 基數排序

　　多關鍵字中的每個關鍵字的取值范圍一般不同。如撲克牌的花色取值只有4種，而點數則有13種。單關鍵字中的每位一般取值范圍相

　　同。

　　2、基數

　　設單關鍵字的每個分量的取值范圍均是：

　　C 0 ≤k j ≤C rd-1 (0≤j

　　可能的取值個數rd稱為基數。

　　基數的選擇和關鍵字的分解因關鍵宇的類型而異:

　　(1) 若關鍵字是十進制整數，則按個、十等位進行分解，基數rd=10，C 0 =0，C 9 =9，d為最長整數的位數;

　　(2) 若關鍵字是小寫的英文字符串，則rd=26，C o ='a'，C 25 ='z'，d為字符串的最大長度。

　　3、基數排序的基本思想

　　基數排序的基本思想是：從低位到高位依次對K j (j=d-1，d-2，…，0)進行箱排序。在d趟箱排序中，所需的箱子數就是基數

　　rd，這就是"基數排序"名稱的由來。

　　4、基數排序的排序過程

　　要排序的記錄關鍵字取值范圍是0到99之間的整數(36，5，16，98，95，47， 32，36，48)。對這些關鍵字進行基數排序的過程。

　　5、基數排序的類型說明和算法描述

　　要保證基數排序是正確的，就必須保證除第一趟外各趟箱排序是穩定的。相應的類型說明及算法描述【參見教材】。

　　6、算法分析

　　若排序文件不是以數組R形式給出，而是以單鏈表形式給出(此時稱為鏈式的基數排序)，則可通過修改出隊和人隊函數使表示箱子

　　的鏈隊列無須分配結點空間，而使用原鏈表的結點空間。人隊出隊操作亦無需移動記錄而僅需修改指針。雖然這樣一來節省了一定的

　　時間和空間，但算法要復雜得多，且時空復雜度就其數量級而言並未得到改觀。 有關鏈式的基數排序可【閱讀參考書目[12]】。

　　基數排序的時間是線性的(即O(n))。

　　基數排序所需的輔助存儲空間為O(n+rd)。

　　基數排序是穩定的。