分配排序的基本思想：排序過程無須比較關鍵字，而是通過"分配"和"收集"過程來實現排序.它們的時間復雜度可達到線性階：O(n)。
箱排序(Bin Sort)
1、箱排序的基本思想
??? 箱排序也稱桶排序(Bucket Sort)，其基本思想是：設置若干個箱子，依次掃描待排序的記錄R[0]，R[1]，…，R[n-1]，把關鍵字等于k的記錄全都裝入到第k個箱子里(分配)，然后按序號依次將各非空的箱子首尾連接起來(收集)。
【例】要將一副混洗的52張撲克牌按點數A<2<…<J<Q<K排序，需設置13個"箱子"，排序時依次將每張牌按點數放入相應的箱子里，然后依次將這些箱子首尾相接，就得到了按點數遞增序排列的一副牌。
2、箱排序中，箱子的個數取決于關鍵字的取值范圍。
??? 若R[0..n-1]中關鍵字的取值范圍是0到m-1的整數，則必須設置m個箱子。因此箱排序要求關鍵字的類型是有限類型，否則可能要無限個箱子。
3、箱子的類型應設計成鏈表為宜
??? 一般情況下每個箱子中存放多少個關鍵字相同的記錄是無法預料的，故箱子的類型應設計成鏈表為宜。
4、為保證排序是穩定的，分配過程中裝箱及收集過程中的連接必須按先進先出原則進行。
（1） 實現方法一
??? 每個箱子設為一個鏈隊列。當一記錄裝入某箱子時，應做人隊操作將其插入該箱子尾部；而收集過程則是對箱子做出隊操作，依次將出隊的記錄放到輸出序列中。
（2） 實現方法二
??? 若輸入的待排序記錄是以鏈表形式給出時，出隊操作可簡化為是將整個箱子鏈表鏈接到輸出鏈表的尾部。這只需要修改輸出鏈表的尾結點中的指針域，令其指向箱子鏈表的頭，然后修改輸出鏈表的尾指針，令其指向箱子鏈表的尾即可。
5、算法簡析
??? 分配過程的時間是O(n)；收集過程的時間為O(m) （采用鏈表來存儲輸入的待排序記錄）或O(m+n)。因此，箱排序的時間為O(m+n)。若箱子個數m的數量級為O(n)，則箱排序的時間是線性的，即O(n)。
? 注意：
??? 箱排序實用價值不大，僅適用于作為基數排序(下節介紹)的一個中間步驟。
桶排序
??? 箱排序的變種。為了區別于上述的箱排序，姑且稱它為桶排序(實際上箱排序和桶排序是同義詞)。
1、桶排序基本思想
??? 桶排序的思想是把[0，1)劃分為n個大小相同的子區間，每一子區間是一個桶。然后將n個記錄分配到各個桶中。因為關鍵字序列是均勻分布在[0，1)上的，所以一般不會有很多個記錄落入同一個桶中。由于同一桶中的記錄其關鍵字不盡相同，所以必須采用關鍵字比較的排序方法(通常用插入排序)對各個桶進行排序，然后依次將各非空桶中的記錄連接(收集)起來即可。
? 注意：
??? 這種排序思想基于以下假設：假設輸入的n個關鍵字序列是隨機分布在區間[0，1)之上。若關鍵字序列的取值范圍不是該區間，只要其取值均非負，我們總能將所有關鍵字除以某一合適的數，將關鍵字映射到該區間上。但要保證映射后的關鍵字是均勻分布在[0，1)上的。
2、桶排序算法
? 偽代碼算法為：
? void BucketSon(R)
??? { //對R[0..n-1]做桶排序，其中0≤R[i].key<1(0≤i<n)
????? for(i=0，i<n;i++) //分配過程．
??????? 將R[i]插入到桶B[「n(R[i].key)」]中； //可插入表頭上
????? for(i=0;i<n;i++) //排序過程
??????? 當B[i]非空時用插人排序將B[i]中的記錄排序；
????? for(i=0，i<n；i++) //收集過程
??????? 若B[i]非空，則將B[i]中的記錄依次輸出到R中；
???? }
? 注意：
??? 實現時需設置一個指針向量B[0..n-1]來表示n個桶。但因為任一記錄R[i]的關鍵字滿足：0≤R[i].key<1(0≤i≤n-1)，所以必須將R[i].key映射到B的下標區間[0，n-1)上才能使R[i]裝入某個桶中，這可通過└n*(R[i].key)┘來實現。
3、桶排序示例
??? R[0..9]中的關鍵字為 (0.78，0.17，0.39，0.26，0.72，0.94，0.21， 0.12，0.23，0.68)，用算法BucketSort排序的過程【
參見動畫演示
】。
分析：
??? 這里n=10，故B[0..9]這10個桶表示的子區間分別是[0，0.1)，[0.1，0.2)，…，[0.9，1)。
??? 收集過程只要按B[0]，B[1]，…，B[9]的次序將各非空桶首尾鏈接起來，或將其輸出到R[0..9)中即可。
4、桶排序算法分析
??? 桶排序的平均時間復雜度是線性的，即O(n)。但最壞情況仍有可能是O(n2)。
??? 箱排序只適用于關鍵字取值范圍較小的情況，否則所需箱子的數目m太多導致浪費存儲空間和計算時間。
【例】n=10，被排序的記錄關鍵字ki取值范圍是0到99之間的整數(36，5，16，98，95，47, 32，36，48)時，要用100個箱子來做一趟箱排序。（即若m=n2時，箱排序的時間O(m+n)=O(n2)）。
基數排序?
??? 基數排序(Radix Sort)是對箱排序的改進和推廣。
1、單關鍵字和多關鍵字
??? 文件中任一記錄R[i]的關鍵字均由d個分量
???????????????????? 
構成。
若這d個分量中每個分量都是一個獨立的關鍵字，則文件是多關鍵字的(如撲克牌有兩個關鍵字：點數和花色)；否則文件是單關鍵字的，
?????????????? 
(0≤j<d)只不過是關鍵字中其中的一位(如字符串、十進制整數等)。
??? 多關鍵字中的每個關鍵字的取值范圍一般不同。如撲克牌的花色取值只有4種，而點數則有13種。單關鍵字中的每位一般取值范圍相同。
2、基數
??? 設單關鍵字的每個分量的取值范圍均是：
????? C0≤kj≤Crd-1(0≤j<d)
可能的取值個數rd稱為基數。
??? 基數的選擇和關鍵字的分解因關鍵宇的類型而異:
(1) 若關鍵字是十進制整數，則按個、十等位進行分解，基數rd=10，C0=0，C9=9，d為最長整數的位數；
(2) 若關鍵字是小寫的英文字符串，則rd=26，Co='a'，C25='z'，d為字符串的最大長度。
3、基數排序的基本思想
??? 基數排序的基本思想是：從低位到高位依次對Kj(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)。
??? 基數排序是穩定的。