本節(jié)介紹第二種分配排序，基數(shù)排序(Radix Sort)是對箱排序的改進和推廣。

單關(guān)鍵字和多關(guān)鍵字

文件中任一記錄R[i]的關(guān)鍵字均由d個分量

http://wiki.jikexueyuan.com/project/data-structure-sorting/images/k.gif" alt="" />構(gòu)成。

若這d個分量中每個分量都是一個獨立的關(guān)鍵字，則文件是多關(guān)鍵字的(如撲克牌有兩個關(guān)鍵字：點數(shù)和花色)；否則文件是單關(guān)鍵字的，

http://wiki.jikexueyuan.com/project/data-structure-sorting/images/k1.gif" alt="" />(0≤j<d)只不過是關(guān)鍵字中其中的一位(如字符串、十進制整數(shù)等)。

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

基數(shù)

設(shè)單關(guān)鍵字的每個分量的取值范圍均是：

C0≤kj≤Crd-1(0≤j<d)

可能的取值個數(shù) rd 稱為基數(shù)。

基數(shù)的選擇和關(guān)鍵字的分解因關(guān)鍵宇的類型而異:

(1) 若關(guān)鍵字是十進制整數(shù)，則按個、十等位進行分解，基數(shù) rd=10，C0=0，C9=9，d 為最長整數(shù)的位數(shù)； (2) 若關(guān)鍵字是小寫的英文字符串，則 rd=26，Co='a'，C25='z'，d 為字符串的最大長度。

基數(shù)排序的基本思想

基數(shù)排序的基本思想是：從低位到高位依次對 Kj(j=d-1，d-2，…，0)進行箱排序。在 d 趟箱排序中，所需的箱子數(shù)就是基數(shù) rd，這就是"基數(shù)排序"名稱的由來。

基數(shù)排序的排序過程

要排序的記錄關(guān)鍵字取值范圍是 0 到 99 之間的整數(shù)(36，5，16，98，95，47， 32，36，48)。對這些關(guān)鍵字進行基數(shù)排序的過程【參見動畫演示】。

基數(shù)排序的類型說明和算法描述

要保證基數(shù)排序是正確的，就必須保證除第一趟外各趟箱排序是穩(wěn)定的。

算法分析

若排序文件不是以數(shù)組 R 形式給出，而是以單鏈表形式給出(此時稱為鏈式的基數(shù)排序)，則可通過修改出隊和人隊函數(shù)使表示箱子的鏈隊列無須分配結(jié)點空間，而使用原鏈表的結(jié)點空間。人隊出隊操作亦無需移動記錄而僅需修改指針。雖然這樣一來節(jié)省了一定的時間和空間，但算法要復雜得多，且時空復雜度就其數(shù)量級而言并未得到改觀。

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

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

基數(shù)排序是穩(wěn)定的。