閱讀532 返回首頁    go 阿裏雲 go 技術社區[雲棲]

排序算法(4)

  素都是不大於k=6的正整數。
圖1 計數排序算法演示

容 易理解，算法的第(l)行是對數組tmp初始化。第(2)行檢查每個輸入元素。如果輸入元素的鍵值為i，則tmp[i]增1。因此，在第(2)行執行結束 後，tmp[i]中存放著值等於i的輸入元素個數，i=1,2,..,k。算法的第(3)行，對每個i=1,2,..,i，統計值小於或等於i的輸入元素 個數。最後在(4)-(8)行中，將每個元素L[j]存放到輸出數組R中相應的最終位置上。如果所有n個元素的值都不相同，則共有tmp[L[j]]個元 素的鍵值小於或等於L[j]，而小於L[j]的元素有tmp[L[j]]-1個，因此tmp[L[j]]就是L[j]在輸出數組R中的正確位置。當輸入元 素有相同的值時，每將一個L[j]存放到數組R時，tmp[L[j]]就減1，使下
個值等於L[j]的元素存放在輸出數組R中存放元素L[j]的前一個位置上。

計 數排序算法的計算時間複雜性很容易分析。其中，第(1)行需要O(k)時間；第(2)行需要O(n)時間，第(3)行需要O(k)時間；第(4)-(8) 行的for循環需要O(n)時間。這樣，整個算法所需的計算間為O(n+k)。當k=O(n)時，算法的計算時間複雜性為O(n)。

我們 看到，計數排序算法沒有用到元素間的比較，它利用元素的實際值來確定它們在輸出數組中的位置。因此，計數排序算法不是一個基於比較的排序算法，從而它的計 算時間下界不再是Ω(nlogn)。另一方麵，計數排序算法之所以能取得線性計算時間的上界是因為對元素的取值範圍作了一定限製，即k=O(n)。如果k =n2,n3,..，就得不到線性時間的上界。此外，我們還看到，由於算法第4行使用了downto語句，經計數排序，輸出序列中值相同的元素之間的相對 次序與他們在輸入序列中的相對次序相同，換句話說，計數排序算法是一個穩定的排序算法，但顯然不是原地置換排序算法。

基數排序 Radix Sort

基 數排序是一種用在老式穿卡機上的算法。一張卡片有80列，每列可在12個位置中的任一處穿孔。排序器可被機械地"程序化"以檢查每一迭卡片中的某一列，再 根據穿孔的位置將它們分放12個盒子裏。這樣，操作員就可逐個地把它們收集起來。其中第一個位置穿孔的放在最上麵，第二個位置穿孔的其次，等等。

對十進製數字來說，每列中隻用到10個位置(另兩個位置用於編碼非數值字符)。一個d位數占用d個列。因為卡片排序器一次隻能查看一個列，要對n張片上的d位數進行排序就要有個排序算法。

直感上，大家可能覺得應該按最重要的一位排序，然後對每個盒子中的數遞歸地排序，最後把結果合並起來。不幸的是，為排序每一個盒子中的數，10個盒子中的9個必須先放在一邊，這個過程產生了許多要加以記錄的中間卡片堆。

與 人們的直感相反，基數排序是首先按最不重要的一位數字排序來解決卡片排序問題的。同樣，把各堆卡片收集成一迭，其中0號盒子中的在1號盒子中的前麵，後者 又在2號盒子中的前麵，等等。然後對整個一迭卡片按次重要位排序，並把結果同樣地合並起來。重複這個過程，直到對所有的d位數字都進行了排序。所以，僅需 要n遍就可將一迭卡片排好序。圖1說明了基數排序作“一迭”7個三位數的過程。第一列為輸入，其餘各列示出了對各個數位進行逐次排序後表的情形。垂直向上 的箭頭指示了當前要被加以排序的數位。

　
圖1 基數排序作用於一個由7個3位數組成的表上的過程

關於這個算法很重要的一點就是按位排序要穩定。由卡片排序器所故的排序是穩定的，但操作員在把卡片從盒子裏拿出來時不能改變他們的次序，即使某一盒子中所有卡片在給定列上的穿孔位置都相同。

在 一台典型的順序隨機存取計算機上，有時采用基數排序來對有多重域關鍵字的記錄進行排序。例如，假設我們想根據三個關鍵字處、月和日來對日期排序。對這個問 題，可以用帶有比較函數的排序算法來做。給定兩個日期，先比較年份，如果相同，再比較月份，如果再相同，再比較日。這兒我們可以采用另一個方法，即用一種 穩定的排序方法對所給信息進行三次排序：先對日，其次對月，再對年。

基數排序的代碼是很簡單的、下麵的過程假設長度為n的數組A中的每個元素都有d位數字，其中第1位是最低的，第d位是最高位。

procedure Radix_Sort(var L:List;d:integer);

var

i:integer;

begin

1 for i:=1 to d do

2 使用一種穩定的排序方法來對數組L按數字i進行排序;

end;

基 數排序的正確性可以通過對正在被排序的列進行歸納而加以證明。對本算法時間代價的分析要取決於選擇哪種穩定的中間排序算法。當每位數字都界於l到k之間， 且k不太大時，可以選擇計數排序。對n個d位數的每一遍處理的時間為O(n+k)，共有d遍，故基數排序的總時間為θ(dn+kd)。當d為常數，k=O (n)時，基數排序有線性運行時間。

某些計算機科學家傾向於把一個計算機字中所含位數看成是θ(lgn)。具體一點說，假設共有 dlgn位數字，d為正常數。這樣，如果待排序的每個數恰能容於一個計算機字內，我們就可以把它視為一個以n為基數的d位數。看一個例子：對一百萬個64 位數排序。通過把這些數當作是以216為基數的四位數，用基數排序四遍就可完成排序。這與一個典型的O(nlgn)比較排序相比要好得多，後者對每一個參 加排序的數約要lgn=20次操作。但有一點不理想，即采用計數排序作為中間穩定排序算法的基數排序版本不能夠進行原地置換排序，而很多O(nlgn)比 較排序算法卻是可以的。因此，當內存比較緊張時，一般來說選擇快速排序更合適些。

桶排序 Bin Sort

平均情況下桶排序以線性時間運行。像計數排序一樣，桶排序也對輸入作了某種假設， 因而運行得很快。具體來說，計數排序假設輸入是由一個小範圍內的整數構成，而桶排序則 假設輸入由一個隨機過程產生，該過程將元素一致地分布在區間[0，1)上。

桶排序的思想就是把區間[0，1)劃分成n個相同大小的子區間，或稱桶，然後將n個輸入數分布到各個桶中去。因為輸入數均勻分布在[0，1)上，所以一般不會有很多數落在 一個桶中的情況。為得到結果，先對各個桶中的數進行排序，然後按次序把各桶中的元素列 出來即可。

在桶排序算法的代碼中，假設輸入是個含n個元素的數組A，且每個元素滿足0≤ A[i]<1。另外還需要一個輔助數組B[O..n-1]來存放鏈表實現的桶，並假設可以用某種機製來維護這些表。

桶排序的算法如下，其中floor(x)是地板函數，表示不超過x的最大整數。

procedure Bin_Sort(var A:List);

begin

1 n:=length(A);

2 for i:=1 to n do

3 將A[i]插到表B[floor(n*A[i])]中;

4 for i:=0 to n-1 do

5 用插入排序對表B[i]進行排序;

6 將表B[0],B[1],...,B[n-1]按順序合並;

end;



圖1 Bin_Sort的操作

圖1 演示了桶排序作用於有10個數的輸入數組上的操作過程。(a)輸入數組A[1..10]。(b)在該算法的第5行後的有序表(桶)數組B[0..9]。桶 i中存放了區間[i/10，(i+1)/10]上的值。排序輸出由表B[O]、B[1]、...、B[9]的按序並置構成。

要說明這 個算法能證確地工作，看兩個元素A[i]和A[j]。如果它們落在同一個桶中，則它們在輸出序列中有著正確的相對次序，因為它們所在的桶是采用插入排序 的。現假設它們落到不同的桶中，設分別為B[i']和B[j']。不失一般性，假設i'<j'。在算法的代碼中，當第6行中將B中的表並置起來時， 桶B[i']中的元素先於桶B[j']中的元素，因而在輸出序列中A[i]先於A[j]。現在要證鰽[i]≤A[j]。假設情況正好相反，我們有：

i'=floor(n*A[i])≥floor(n*A[j])=j'

得矛盾 (因為i'<j')，從而證明桶排序能正確地工作。

現在來分析算法的運行時間。除第5行外，所有各行在最壞情況的時間都是O(n)。第5行中檢查所有桶的時間是O(n)。分析中唯一有趣的部分就在於第5行中插人排序所花的時間。

為分析插人排序的時間代價，設ni為表示桶B[i]中元素個數的隨機變量。因為插入排序以二次時間運行，故為排序桶B[i]中元素的期望時間為E[O(ni2)]=O(E[ni2])，對各個桶中的所有元素排序的總期望時間為：

(1)

為 了求這個和式，要確定每個隨機變量ni的分布。我們共有n個元素，n個桶。某個元素落到桶B[i]的概率為l/n，因為每個桶對應於區間[0，1)的 l/n。這種情況與投球的例子很類似：有n個球 (元素)和n個盒子 (桶)，每次投球都是獨立的，且以概率p=1/n落到任一桶中。這樣，ni=k的概率就服從二項分布B(k;n,p)，其期望值為E[ni]=np=1， 方差V[ni]=np(1-p)=1-1/n。對任意隨機變量X，有:

　 (2)

將這個界用到(1)式上，得出桶排序中的插人排序的期望運行時間為O(n)。因而，整個桶排序的期望運行時間就是線性的。

下麵的Java Applet程序演示了桶排序的基本思想。

在該演示程序中，線性表的元素類型為整型，桶的標號為整數，算法將值為i的元素放入標號為i的桶中，再按照桶的標號的順序將元素依次取出，就得到了最終的排序結果。

最後更新：2017-04-02 00:06:15

  上一篇：go 電腦記之程序員
  下一篇：go 很幽默的講解六種Socket I/O模型