分配排序的基本思想：排序過程無須比較關鍵字，而是通過"分配"和"收集"過程來實現(xiàn)排序.它們的時間復雜度可達到線性階：O(n)。

本節(jié)介紹第一種分配排序方法：箱排序。

箱排序

1、箱排序的基本思想

箱排序也稱桶排序(Bucket Sort)，其基本思想是：設置若干個箱子，依次掃描待排序的記錄 R[0]，R[1]，…，R[n-1]，把關鍵字等于 k 的記錄全都裝入到第 k 個箱子里(分配)，然后按序號依次將各非空的箱子首尾連接起來(收集)。

【例】要將一副混洗的 52 張撲克牌按點數(shù) A<2<…<J<Q<K 排序，需設置 13 個"箱子"，排序時依次將每張牌按點數(shù)放入相應的箱子里，然后依次將這些箱子首尾相接，就得到了按點數(shù)遞增序排列的一副牌。

2、箱排序中，箱子的個數(shù)取決于關鍵字的取值范圍。

若 R[0..n-1]中關鍵字的取值范圍是0到m-1的整數(shù)，則必須設置 m 個箱子。因此箱排序要求關鍵字的類型是有限類型，否則可能要無限個箱子。

3、箱子的類型應設計成鏈表為宜

一般情況下每個箱子中存放多少個關鍵字相同的記錄是無法預料的，故箱子的類型應設計成鏈表為宜。

4、為保證排序是穩(wěn)定的，分配過程中裝箱及收集過程中的連接必須按先進先出原則進行。

（1）實現(xiàn)方法一

每個箱子設為一個鏈隊列。當一記錄裝入某箱子時，應做人隊操作將其插入該箱子尾部；而收集過程則是對箱子做出隊操作，依次將出隊的記錄放到輸出序列中。

（2）實現(xiàn)方法二

若輸入的待排序記錄是以鏈表形式給出時，出隊操作可簡化為是將整個箱子鏈表鏈接到輸出鏈表的尾部。這只需要修改輸出鏈表的尾結點中的指針域，令其指向箱子鏈表的頭，然后修改輸出鏈表的尾指針，令其指向箱子鏈表的尾即可。

5、算法簡析

分配過程的時間是 O(n)；收集過程的時間為 O(m) （采用鏈表來存儲輸入的待排序記錄）或 O(m+n)。因此，箱排序的時間為 O(m+n)。若箱子個數(shù)m的數(shù)量級為 O(n)，則箱排序的時間是線性的，即 O(n)。

注意： 箱排序實用價值不大，僅適用于作為基數(shù)排序(下節(jié)介紹)的一個中間步驟。

桶排序

箱排序的變種。為了區(qū)別于上述的箱排序，姑且稱它為桶排序(實際上箱排序和桶排序是同義詞)。

1、桶排序基本思想

桶排序的思想是把[0，1)劃分為n個大小相同的子區(qū)間，每一子區(qū)間是一個桶。然后將n個記錄分配到各個桶中。因為關鍵字序列是均勻分布在[0，1)上的，所以一般不會有很多個記錄落入同一個桶中。由于同一桶中的記錄其關鍵字不盡相同，所以必須采用關鍵字比較的排序方法(通常用插入排序)對各個桶進行排序，然后依次將各非空桶中的記錄連接(收集)起來即可。

注意： 這種排序思想基于以下假設：假設輸入的 n 個關鍵字序列是隨機分布在區(qū)間[0，1)之上。若關鍵字序列的取值范圍不是該區(qū)間，只要其取值均非負，我們總能將所有關鍵字除以某一合適的數(shù)，將關鍵字映射到該區(qū)間上。但要保證映射后的關鍵字是均勻分布在[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中；  
   }  

注意： 實現(xiàn)時需設置一個指針向量 B[0..n-1]來表示 n 個桶。但因為任一記錄 R[i]的關鍵字滿足：0≤R[i].key<1(0≤i≤n-1)，所以必須將 R[i].key映射到 B 的下標區(qū)間[0，n-1)上才能使 R[i]裝入某個桶中，這可通過└n*(R[i].key)┘來實現(xiàn)。

桶排序示例

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 個桶表示的子區(qū)間分別是[0，0.1)，[0.1，0.2)，…，[0.9，1)。 收集過程只要按 B[0]，B[1]，…，B[9]的次序將各非空桶首尾鏈接起來，或將其輸出到 R[0..9)中即可。

桶排序算法分析

桶排序的平均時間復雜度是線性的，即 O(n)。但最壞情況仍有可能是 O(n2)。

箱排序只適用于關鍵字取值范圍較小的情況，否則所需箱子的數(shù)目 m 太多導致浪費存儲空間和計算時間。

【例】n=10，被排序的記錄關鍵字 ki 取值范圍是 0 到 99 之間的整數(shù)(36，5，16，98，95，47, 32，36，48)時，要用 100 個箱子來做一趟箱排序。（即若 m=n2 時，箱排序的時間 O(m+n)=O(n2)）。