生命是一種過程

分配排序

桶排序

??? 　箱排序的變種。為了區(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)行排序，然后依次將各非空桶中的記錄連接(收集)起來即可。
? 注意：
??? 　這種排序思想基于以下假設(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++) //分配過程．
??????? 將R[i]插入到桶B[「n(R[i].key)」]中； //可插入表頭上
????? for(i=0;i<n;i++) //排序過程
??????? 當(dāng)B[i]非空時(shí)用插人排序?qū)[i]中的記錄排序；
????? for(i=0，i<n；i++) //收集過程
??????? 若B[i]非空，則將B[i]中的記錄依次輸出到R中；
???? }

? 注意：
??? 　實(shí)現(xiàn)時(shí)需設(shè)置一個(gè)指針向量B[0..n-1]來表示n個(gè)桶。但因?yàn)槿我挥涗汻[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è)桶中，這可通過└n*(R[i].key)┘來實(shí)現(xiàn)。

3、桶排序示例
　??? 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排序的過程【 參見動(dòng)畫演示 】。
分析：
??? 　這里n=10，故B[0..9]這10個(gè)桶表示的子區(qū)間分別是[0，0.1)，[0.1，0.2)，…，[0.9，1)。
??? 　收集過程只要按B[0]，B[1]，…，B[9]的次序?qū)⒏鞣强胀笆孜叉溄悠饋恚驅(qū)⑵漭敵龅絉[0..9)中即可。

4、桶排序算法分析
??? 　桶排序的平均時(shí)間復(fù)雜度是線性的，即O(n)。但最壞情況仍有可能是O(n²)。
??? 　箱排序只適用于關(guān)鍵字取值范圍較小的情況，否則所需箱子的數(shù)目m太多導(dǎo)致浪費(fèi)存儲(chǔ)空間和計(jì)算時(shí)間。
　　【例】n=10，被排序的記錄關(guān)鍵字k_i取值范圍是0到99之間的整數(shù)(36，5，16，98，95，47, 32，36，48)時(shí)，要用100個(gè)箱子來做一趟箱排序。（即若m=n²時(shí)，箱排序的時(shí)間O(m+n)=O(n²)）。

基數(shù)排序?

??? 　基數(shù)排序(Radix Sort)是對(duì)箱排序的改進(jìn)和推廣。

1、單關(guān)鍵字和多關(guān)鍵字
??? 　文件中任一記錄R[i]的關(guān)鍵字均由d個(gè)分量
???????????????????? 構(gòu)成。
若這d個(gè)分量中每個(gè)分量都是一個(gè)獨(dú)立的關(guān)鍵字，則文件是多關(guān)鍵字的(如撲克牌有兩個(gè)關(guān)鍵字：點(diǎn)數(shù)和花色)；否則文件是單關(guān)鍵字的，
?????????????? (0≤j<d)只不過是關(guān)鍵字中其中的一位(如字符串、十進(jìn)制整數(shù)等)。
??? 多關(guān)鍵字中的每個(gè)關(guān)鍵字的取值范圍一般不同。如撲克牌的花色取值只有4種，而點(diǎn)數(shù)則有13種。單關(guān)鍵字中的每位一般取值范圍相同。

2、基數(shù)
??? 　　設(shè)單關(guān)鍵字的每個(gè)分量的取值范圍均是：
????? C₀≤k_j≤C_rd-1(0≤j<d)
可能的取值個(gè)數(shù)rd稱為基數(shù)。
??? 　基數(shù)的選擇和關(guān)鍵字的分解因關(guān)鍵宇的類型而異:
(1) 若關(guān)鍵字是十進(jìn)制整數(shù)，則按個(gè)、十等位進(jìn)行分解，基數(shù)rd=10，C₀=0，C₉=9，d為最長整數(shù)的位數(shù)；
(2) 若關(guān)鍵字是小寫的英文字符串，則rd=26，C_o='a'，C₂₅='z'，d為字符串的最大長度。

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

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

5、基數(shù)排序的類型說明和算法描述
??? 　要保證基數(shù)排序是正確的，就必須保證除第一趟外各趟箱排序是穩(wěn)定的。相應(yīng)的類型說明及算法描述【參見教材】。

6、算法分析
??? 　若排序文件不是以數(shù)組R形式給出，而是以單鏈表形式給出(此時(shí)稱為鏈?zhǔn)降幕鶖?shù)排序)，則可通過修改出隊(duì)和人隊(duì)函數(shù)使表示箱子的鏈隊(duì)列無須分配結(jié)點(diǎn)空間，而使用原鏈表的結(jié)點(diǎn)空間。人隊(duì)出隊(duì)操作亦無需移動(dòng)記錄而僅需修改指針。雖然這樣一來節(jié)省了一定的時(shí)間和空間，但算法要復(fù)雜得多，且時(shí)空復(fù)雜度就其數(shù)量級(jí)而言并未得到改觀。 有關(guān)鏈?zhǔn)降幕鶖?shù)排序可【閱讀參考書目[12]】。
??? 　基數(shù)排序的時(shí)間是線性的(即O(n))。
??? 　基數(shù)排序所需的輔助存儲(chǔ)空間為O(n+rd)。
??? 　基數(shù)排序是穩(wěn)定的。

posted on 2006-07-20 15:53 xnlijun 閱讀(385) 評(píng)論(0)  編輯  收藏