分配排序的基本思想：排序過(guò)程無(wú)須比較關(guān)鍵字，而是通過(guò)"分配"和"收集"過(guò)程來(lái)實(shí)現(xiàn)排序.它們的時(shí)間復(fù)雜度可達(dá)到線性階：O(n)。

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

箱排序

1、箱排序的基本思想

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

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

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

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

3、箱子的類型應(yīng)設(shè)計(jì)成鏈表為宜

一般情況下每個(gè)箱子中存放多少個(gè)關(guān)鍵字相同的記錄是無(wú)法預(yù)料的，故箱子的類型應(yīng)設(shè)計(jì)成鏈表為宜。

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

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

每個(gè)箱子設(shè)為一個(gè)鏈隊(duì)列。當(dāng)一記錄裝入某箱子時(shí)，應(yīng)做人隊(duì)操作將其插入該箱子尾部；而收集過(guò)程則是對(duì)箱子做出隊(duì)操作，依次將出隊(duì)的記錄放到輸出序列中。

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

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

5、算法簡(jiǎn)析

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

注意： 箱排序?qū)嵱脙r(jià)值不大，僅適用于作為基數(shù)排序(下節(jié)介紹)的一個(gè)中間步驟。

桶排序

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

1、桶排序基本思想

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

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

2、桶排序算法

偽代碼算法為：

void BucketSon(R)  
  { //對(duì)R[0..n-1]做桶排序，其中0≤R[i].key<1(0≤i<n)  
    for(i=0，i<n;i++) //分配過(guò)程．  
      將R[i]插入到桶B[「n(R[i].key)」]中； //可插入表頭上  
    for(i=0;i<n;i++) //排序過(guò)程  
      當(dāng)B[i]非空時(shí)用插人排序?qū)[i]中的記錄排序；  
    for(i=0，i<n；i++) //收集過(guò)程  
      若B[i]非空，則將B[i]中的記錄依次輸出到R中；  
   }  

注意： 實(shí)現(xiàn)時(shí)需設(shè)置一個(gè)指針向量 B[0..n-1]來(lái)表示 n 個(gè)桶。但因?yàn)槿我挥涗?R[i]的關(guān)鍵字滿足：0≤R[i].key<1(0≤i≤n-1)，所以必須將 R[i].key映射到 B 的下標(biāo)區(qū)間[0，n-1)上才能使 R[i]裝入某個(gè)桶中，這可通過(guò)└n*(R[i].key)┘來(lái)實(shí)現(xiàn)。

桶排序示例

R[0..9]中的關(guān)鍵字為 (0.78，0.17，0.39，0.26，0.72，0.94，0.21， 0.12，0.23，0.68)，用算法BucketSort排序的過(guò)程【參見(jiàn)動(dòng)畫(huà)演示】。

分析： 這里 n=10，故 B[0..9]這 10 個(gè)桶表示的子區(qū)間分別是[0，0.1)，[0.1，0.2)，…，[0.9，1)。 收集過(guò)程只要按 B[0]，B[1]，…，B[9]的次序?qū)⒏鞣强胀笆孜叉溄悠饋?lái)，或?qū)⑵漭敵龅?R[0..9)中即可。

桶排序算法分析

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

箱排序只適用于關(guān)鍵字取值范圍較小的情況，否則所需箱子的數(shù)目 m 太多導(dǎo)致浪費(fèi)存儲(chǔ)空間和計(jì)算時(shí)間。

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