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

單關鍵字和多關鍵字

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

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

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

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

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

基數

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

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

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

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

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

基數排序的基本思想

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

基數排序的排序過程

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

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

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

算法分析

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

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

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

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