168
技術社區[雲棲]
排序算法(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;
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
begin
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前一個位置作為分割點
end;
end;
該 算法的實現很精巧。其中，有一些細節需要注意。例如，算法中的位置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);
var
i,j:integer;
tmp:TList;
begin
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保證了排序的穩定性
begin
5 R[tmp[L[j]]]:=L[j];//L[j]存放在輸出數組R的第tmp[L[j]]個位置上
6 dec(tmp[L[j]]); //tmp[L[j]]表示L中剩餘的元素中小於等於L[j]的元素的個數
end;
end;
圖1所示的是Counting_Sort作用於一個輸入數組L[1..8]上的過程，其中L的每一個元
最後更新：2017-04-02 00:06:15