排序算法(3)

  =e then insertion_sort(l,p,r)//若l[p..r]足夠小則直接對l[p..r]進行插入排序

else begin

2 q:=partition(p,r,l);//将l[p..r]分解為l[p..q]和l[q+1..r]兩部分

3 quick_sort(p,q,l); //遞歸排序l[p..q]

4 quick_sort(q+1,r,l);//遞歸排序l[q+1..r]

end;

對 線性表l[1..n]進行排序，隻要調用quick_sort(1,n,l)就可以了。算法首先判斷l[p..r]是否足夠小，若足夠小則直接對l [p..r]進行排序，sort可以是任何一種簡單的排序法，一般用插入排序。這是因為，對于較小的表，快速排序中劃分和遞歸的開銷使得該算法的效率還不 如其它的直接排序法好。至于規模多小才算足夠小，并沒有一定的标準，因為這跟生成的代碼和執行代碼的計算機有關，可以采取試驗的方法确定這個規模門檻值。經 驗表明，在大多數計算機上，取這個門檻值為12較好，也就是說，當r-p<=e=12即l[p..r]的規模不大于12時，直接采用插入排序法對l [p..r]進行排序(參見 sorting and searching algorithms: a cookbook)。當然，比較友善的方法是取該門檻值為1，當待排序的表隻有一個元素時，根本不用排序(其實還剩兩個元素時就已經在partition函 數中排好序了)，隻要把第1行的if語句該為if p=r then exit else ...。這就是通常教科書上看到的快速排序的形式。

注意：算法quick_sort中變量q的值一定不能等于r，否則該過程會無限遞歸下去，永遠不能結束。是以下文中在partition函數裡加了限制條件，避免q=r情況的出現。

算法quick_sort中調用了一個函數partition，該函數主要實作以下兩個功能：

1. 在l[p..r]中選擇一個支點元素pivot;

2. 對l[p..r]中的元素進行整理，使得l[p..q]分為兩部分l[p..q]和l[q+1..r]，并且l[p..q]中的每一個元素的值不大于 pivot，l[q+1..r]中的每一個元素的值不小于pivot，但是l[p..q]和l[q+1..r]中的元素并不要求排好序。

快速排序法改進性能的關鍵就在于上述的第二個功能，因為該功能并不要求l[p..q]和l[q+1..r]中的元素排好序。

函數partition可以實作如下。以下的實作方法是原地置換的，當然也有不是原地置換的方法，實作起來較為簡單，這裡就不介紹了。

function partition(p,r:position;var l:list):position;

var

pivot:elementtype;

i,j:position;

begin

1 pivot:=select_pivot(p,r,l); //在l[p..r]中選擇一個支點元素pivot

2 i:=p-1;

3 j:=r+1;

4 while true do

5 repeat j:=j-1 until l[j]<=pivot; //移動左指針，注意這裡不能用while循環

6 repeat i:=i+1 until l[i]>=pivot; //移動右指針，注意這裡不能用while循環

7 if i< j then swap(l[i],l[j]) //交換l[i]和l[j]

8 else if j<>r then return j //傳回j的值作為分割點

9 else return j-1; //傳回j前一個位置作為分割點

該 算法的實作很精巧。其中，有一些細節需要注意。例如，算法中的位置i和j不會超出a[p..r]的位置界，并且該算法的循環不會出現死循環，如果将兩個 repeat語句換為while則要注意當l[i]=l[j]=pivot且i<j時i和j的值都不再變化，會出現死循環。

另外，最後一個if..then..語句很重要，因為如果pivot取的不好，使得partition結束時j正好等于r，則如前所述，算法quick_sort會無限遞歸下去；是以必須判斷j是否等于r，若j=r則傳回j的前驅。

以上算法的一個執行執行個體如圖1所示，其中pivot=l[p]=5：

圖1 partition過程的一個執行執行個體

partition 對l[p..r]進行劃分時，以pivot作為劃分的基準，然後分别從左、右兩端開始，擴充兩個區域l[p..i]和l[j..r]，使得l[p..i] 中元素的值小于或等于pivot，而l[j..r]中元素的值大于或等于pivot。初始時i=p-1，且j=i+1，進而這兩個區域是空的。在 while循環體中，位置j逐漸減小，i逐漸增大，直到l[i]≥pivot≥l[j]。如果這兩個不等式是嚴格的，則l[i]不會是左邊區域的元素，而 l[j]不會是右邊區域的元素。此時若i在j之前，就應該交換l[i]與l[j]的位置，擴充左右兩個區域。 while循環重複至i不再j之前時結束。這時l[p..r]己被劃分成l[p..q]和l[q+1..r]，且滿足l[p..q]中元素的值不大于l [q+1..r]中元素的值。在過程partition結束時傳回劃分點q。

尋找支點元素select_pivot有多種實作方法，不同的實作方法會導緻快速排序的不同性能。根據分治法平衡子問題的思想，我們希望支點元素可以使l[p..r]盡量平均地分為兩部分，但實際上這是很難做到的。下面我們給出幾種尋找pivot的方法。

1. 選擇l[p..r]的第一個元素l[p]的值作為pivot；

2. 選擇l[p..r]的最後一個元素l[r]的值作為pivot；

3. 選擇l[p..r]中間位置的元素l[m]的值作為pivot；

4. 選擇l[p..r]的某一個随機位置上的值l[random(r-p)+p]的值作為pivot；

按照第4種方法随機選擇pivot的快速排序法又稱為随機化版本的快速排序法，在下面的複雜性分析中我們将看到該方法具有平均情況下最好的性能，在實際應用中該方法的性能也是最好的。

下 面是一個快速排序的java applet示範程式，該程式使用第一種pivot選擇法，即選l[p]為pivot，是以partition過程作了一些簡化，與我們這裡的 partition過程實作方法不同，但功能相同。該程式是針對用數組實作的線性表，用c語言實作的。

線性時間排序算法

我們已經知道，通過比較确定兩個元素之間相對位置的比較排序算法計算時間複雜性下界為o(nlogn)，要想改進這個下界，就必須對輸入的資料作某些限制。下面介紹的幾種排序算法都可以在o(n)時間内對一個線性表進行排序，但是他們要求輸入資料滿足某種條件。

計數排序

基數排序

桶排序

計數排序 counting sort

計數排序是一個非基于比較的線性時間排序算法。它對輸入的資料有附加的限制條件：

1. 輸入的線性表的元素屬于有限偏序集s；

2. 設輸入的線性表的長度為n，|s|=k（表示集合s中元素的總數目為k），則k=o(n)。

在這兩個條件下，計數排序的複雜性為o(n)。

計 數排序算法的基本思想是對于給定的輸入序列中的每一個元素x，确定該序列中值小于x的元素的個數。一旦有了這個資訊，就可以将x直接存放到最終的輸出序列 的正确位置上。例如，如果輸入序列中隻有17個元素的值小于x的值，則x可以直接存放在輸出序列的第18個位置上。當然，如果有多個元素具有相同的值時， 我們不能将這些元素放在輸出序列的同一個位置上，是以，上述方案還要作适當的修改。

假設輸入的線性表l的長度為n，l=l1,l2,..,ln；線性表的元素屬于有限偏序集s，|s|=k且k=o(n)，s={s1,s2,..sk}；則計數排序算法可以描述如下：

1. 掃描整個集合s，對每一個si∈s，找到線上性表l中小于等于si的元素的個數t(si)；

2. 掃描整個線性表l，對l中的每一個元素li，将li放在輸出線性表的第t(li)個位置上，并将t(li)減1。

具體的實作如下。

注意：在以下的讨論中，為了友善，我們假設線性表是用數組來實作的，并且假設線性表的元素類型telement為整型，其值在1..k之間，線性表的長度為n，且k=o(n)。這些假設對計數排序算法沒有實質的影響，但是可以使以下介紹的算法看起來容易了解。

在下面的計數排序算法中，我們假設l為輸入的長度為n的線性表，輸出的排序結果存放線上性表r中。算法中還用到一個輔助表tmp用于對輸入元素進行計數。

type

telement=1..k;

tlist=array [1..maxlength] of telement;

tposition=integer;

procedure counting_sort(var l,r:tlist);

i,j:integer;

tmp:tlist;

1 for i:=1 to k do tmp[i]:=0;

2 for j:=1 to n do inc(tmp[l[j]]);

//執行完上面的循環後，tmp[i]的值是l中等于i的元素的個數

3 for i:=2 to k do tmp[i]:=tmp[i]+tmp[i-1];

//執行完上面的循環後，tmp[i]的值是l中小于等于i的元素的個數

4 for j:=n downto 1 do //注意這裡的downto保證了排序的穩定性

5 r[tmp[l[j]]]:=l[j];//l[j]存放在輸出數組r的第tmp[l[j]]個位置上

6 dec(tmp[l[j]]); //tmp[l[j]]表示l中剩餘的元素中小于等于l[j]的元素的個數

圖1所示的是counting_sort作用于一個輸入數組l[1..8]上的過程，其中l的每一個元