排序算法比較

1、排序算法比較研究人員：高二（12）班 孫亦超、朱俊杰；指導老師：徐 偉研究內(nèi)容：比較排序算法的空間、時間復雜度；研究目的：有效提高程序運行的速度；研究意義：通過深入探究，分析其空間和時間復雜度，從而有效提高程序設計者的算法設計；研究日期：2004年8月2005年5月預期成果：flash演示課件、word研究報告、書面報告；排序Sorting排序問題的輸入是一個線性表，該線性表的元素屬于一個偏序集；要求對該線性表的元素做某種重排，使得線性表中除表尾外的每個元素都小于等于（或大于等于）它的后繼。設R為非空集合A上的二元關系，如果R滿足自反性(對于每一個xA，(x,x)R )，反對稱性(x,y)R(

2、y,x)Rx=y )和傳遞性(x,y)R(y,x)R(x,z)R)，則稱R為A上的偏序關系，記作。如果(x,y)R，則記作xy，讀作“x小于等于y”。存在偏序關系的集合A稱為偏序集。注意，這里的不是指數(shù)的大小，而是指在偏序關系中的順序性。xy的含義是：按照這個序，x排在y前面。根據(jù)不同的偏序定義，有不同的解釋。例如整除關系是偏序關系，36的含義是3整除6。大于或等于關系也是偏序關系，針對這個關系54是指在大于或等于關系中5排在4的前面，也就是說5比4大。在實際應用中，經(jīng)常遇到的偏序關系是定義在一個記錄類型的數(shù)據(jù)集合上的。在該記錄類型中有一個主鍵域key，key域的類型是某一個偏序集，記錄的其他

3、域稱為衛(wèi)星數(shù)據(jù)。比較線性表中的兩個元素Li和Lj的大小，實際上是比較Li.key和Lj.key的大小（這種比較當然也是偏序集中的比較）。舉例而言，某公司的數(shù)據(jù)庫里記 錄了員工的數(shù)據(jù)，每一項紀錄包括姓名，編號，年齡，工資等幾個域，如果以編號為key域?qū)T工記錄排序，則是將員工記錄按照編號排序；如果以工資為key域?qū)T工記錄排序，則是將員工記錄按照工資高低排序；如果以姓名為key域?qū)T工記錄排序，則是以員工姓名的漢語拼音按照字典順序排序。關于偏序集的具體概念和應用，請參見離散數(shù)學的相關資料。如果一個排序算法利用輸入的線性表在原地重排其中元素，而沒有額外的內(nèi)存開銷，這種排序算法叫做原地置換排序算法(

4、in place sort)；如果排序后并不改變表中相同的元素原來的相對位置，那么這種排序算法叫做穩(wěn)定排序算法(stable sort)。排序問題一般分為內(nèi)排序( internal sorting )和外排序( external sorting )兩類：1. 內(nèi)排序：待排序的表中記錄個數(shù)較少，整個排序過程中所有的記錄都可以保留在內(nèi)存中； 2. 外排序：待排序的記錄個數(shù)足夠多，以至于他們必須存儲在磁帶、磁盤上組成外部文件，排序過程中需要多次訪問外存。排序問題的計算復雜性對排序算法計算時間的分析可以遵循若干種不同的準則，通常以排序過程所需要的算法步數(shù)作為度量，有時也以排序過程中所作的鍵比較次數(shù)作為

5、度量。特別是當作一次鍵比較需要較長時間，例如，當鍵是較長的字符串時，常以鍵比較次數(shù)作為排序算法計算時間復雜性的度量。當排序時需要移動記錄，且記錄都很大時，還應該考慮記錄的移動次數(shù)。究竟采用哪種度量方法比較合適要根據(jù)具體情況而定。在下面的討論中我們主要考慮用比較的次數(shù)作為復雜性的度量。為了對有n個元素的線性表進行排序，至少必須掃描線性表一遍以獲取這n個元素的信息，因此排序問題的計算復雜性下界為(n)。如果我們對輸入的數(shù)據(jù)不做任何要求，我們所能獲得的唯一信息就是各個元素的具體的值，我們僅能通過比較來確定輸入序列的元素間次序。即給定兩個元素ai和aj，通過測試aiaj 中的哪一個成立來確定ai和aj

6、間的相對次序。這樣的排序算法稱為比較排序算法。下面我們討論一下比較排序算法在最壞情況下至少需要多少次比較，即比較排序算法的最壞情況復雜性下界。我們假設每次比較只測試aiaj ，如果aiaj 成立則ai排在aj 前面，否則ai排在aj 后面。任何一個比較排序算法可以描述為一串比較序列:(ai,aj),(ak,al),.,(am,an),.表示我們首先比較(ai,aj)，然后比較(ak,al)，.，比較(am,an)，.，直到我們獲取了足夠的信息可以確定所有元素的順序。顯而易見，如果我們對所有的元素兩兩進行一次比較的話(總共比較了Cn2次)，就一定可以確定所有元素的順序。但是，如果我們運氣足夠好的

7、話，我們可能不必對所有元素兩兩進行一次比較。比如說對于有三個元素a1,a2,a3的線性表進行排序，如果我們先比較a1和a2，得到a1a2；然后比較a2和a3，得到a2a3；則不必比較a1和a3，因為根據(jù)偏序集的傳遞性，必有a1a3；但是如果a2a3，我們還必須比較a1和a3才能確定a1和a3的相對位置。如果我們適當?shù)陌才疟容^的次序的話，也可以減少比較的次數(shù)。這樣我們可以用一棵二叉樹表示比較的順序，如下圖所示：該樹的每一個非葉節(jié)點表示一次比較，每一根樹枝表示一種比較結果，每一個葉節(jié)點表示一種排列順序。這樣的一棵二叉樹叫做決策樹，它用樹枝表示了每次決策做出的選擇。如此我們可以將任何一個比較排序算法

8、用一棵決策樹來表示。請注意上圖只表明了對三個元素的一種比較算法，這種比較算法依次比較(a1,a2)(a2,a3)(a1,a3)，一旦中間某步得到足夠的信息就可以停止比較，但是當算法執(zhí)行完后（三次比較后），一定可以確定三個元素間的次序。因此我們有理由將算法在最壞情況下的比較次數(shù)作為算法復雜性的度量，對于本例該算法在最壞情況下要進行C32=3次比較。顯然，一棵決策樹中最高葉節(jié)點的高度就是該決策樹對應的算法在最壞情況下所需的比較次數(shù)，而決策樹中最低葉節(jié)點的高度就是該決策樹對應的算法在最好情況下所需的比較次數(shù)。我們的問題就變?yōu)椋簩τ谌我庖豢脹Q策樹（任意一種比較排序算法），它的最高的樹葉的高度是多少？這

9、個高度就對應于比較排序算法所需的最多比較次數(shù)（在運氣最壞的情況下）；換句話說，對于任何一個輸入，該算法至少需要比較多少次就可以對元素進行排序。我們發(fā)現(xiàn)，決策樹的每個葉節(jié)點對應一個n個元素的排列，其中可能有重復的；但是由于決策樹表明了所有可能遇到的情況，因而n個元素的所有排列都在決策樹中出現(xiàn)過。n個元素共有n!種排列，即決策樹的葉節(jié)點數(shù)目至少為n!。又因為一棵高度為h的二叉樹（指二叉樹的最高樹葉高度為h）的葉節(jié)點數(shù)目最多為2h個（這時正好是滿二叉樹，即每個非葉節(jié)點都有兩個子節(jié)點），因此n!2h，得到hlog(n!)，其中l(wèi)og以2為底。根據(jù)Stirling公式有n!(n/e)n，于是hnlogn

10、-nloge，即h=(nlogn)。這樣我們就證明了對于任意一種利用比較來確定元素間相對位置的排序算法，其最壞情況下復雜性為(nlogn)。在下文中我們將討論幾種比較排序算法，其中快速排序在平均情況下復雜性為O(nlogn)，最壞情況下復雜性為O(n2)；堆排序和合并排序在最壞情況下復雜性為O(nlogn)，因此堆排序和合并排序是漸進最優(yōu)的比較排序算法。排序算法是否還能夠改進呢？從前文我們知道，如果要改進排序算法的效率，就不能只利用比較來確定元素間相對位置。因此我們還需要知道元素的其他附加信息，光知道元素的大小信息是不夠的。下文中我們介紹的計數(shù)排序，基數(shù)排序和桶排序是具有線性時間復雜性的排序算

11、法，這些算法無一例外地對輸入數(shù)據(jù)作了某些附加限制，從而增加已知的信息，因此可以不通過比較來確定元素間的相對位置。比較排序算法通過比較來確定輸入序列的元素間相對次序的排序算法稱為比較排序算法。在下面討論的排序算法中，冒泡排序、選擇排序和插入排序的比較次數(shù)為O(n2)，快速排序在平均情況下復雜性為O(nlogn)，堆排序和合并排序在最壞情況下復雜性為O(nlogn)?？梢?，合并排序和堆排序是比較排序算法中時間復雜度最優(yōu)算法。o 冒泡排序 o 選擇排序 o 插入排序 o 快速排序 o 歸并排序 o Shell排序 o 堆排序 冒泡排序 Bubble Sort最簡單的排序方法是冒泡排序方法。這種方法的

12、基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對這個“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個序列，并時刻注意兩個相鄰的元素的順序是否正確。如果發(fā)現(xiàn)兩個相鄰元素的順序不對，即“輕”的元素在下面，就交換它們的位置。顯然，處理一遍之后，“最輕”的元素就浮到了最高位置；處理二遍之后，“次輕”的元素就浮到了次高位置。在作第二遍處理時，由于最高位置上的元素已是“最輕”元素，所以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經(jīng)過前面i-1遍的處理，它們已正確地排好序。這個算法可實現(xiàn)如下。procedure

13、Bubble_Sort(var L:List);vari,j:position;begin1 for i:=First(L) to Last(L)-1 do2 for j:=First(L) to Last(L)-i do3 if LjLj+1 then 4 swap(Lj,Lj+1); /交換Lj和Lj+1end;上述算法將較大的元素看作較重的氣泡，每次最大的元素沉到表尾。其中First(L)和Last(L)分別表示線性表L的第一個元素和最后一個元素的位置，swap(x,y)交換變量x,y的值。上述算法簡單地將線性表的位置當作整數(shù)用for循環(huán)來處理，但實際上線性表可能用鏈表實現(xiàn)；而且上述算法

14、將線性表元素的值當作其鍵值進行處理。不過這些并不影響表達該算法的基本思想。今后如果不加說明，所有的算法都用這種簡化方式表達。容易看出該算法總共進行了n(n-1)/2次比較。如果swap過程消耗的時間不多的話，主要時間消耗在比較上，因而時間復雜性為O(n2)。但是如果元素類型是一個很大的紀錄，則Swap過程要消耗大量的時間，因此有必要分析swap執(zhí)行的次數(shù)。顯然算法Bubble_Sort在最壞情況下調(diào)用n(n-1)/2次Swap過程。我們假設輸入序列的分布是等可能的?？紤]互逆的兩個輸入序列L1=k1,k2,.,kn和L2=kn,kn-1,.,k1。我們知道，如果kikj，且ki在表中排在kj前面

15、，則在冒泡法排序時必定要將kj換到ki前面，即kj向前浮的過程中一定要穿過一次ki，這個過程要調(diào)用一次Swap。對于任意的兩個元素ki和kj，不妨設kikj，或者在L1中ki排在kj前面，或者L2在中ki排在kj前面，兩者必居其一。因此對于任意的兩個元素ki和kj，在對L1和L2排序時，總共需要將這兩個元素對調(diào)一次。n個元素中任取兩個元素有Cn2 種取法，因此對于兩個互逆序列進行排序，總共要調(diào)用Cn2 =n(n-1)/2次Swap，平均每個序列要調(diào)用n(n-1)/4次Swap。那么算法Bubble_Sort調(diào)用Swap的平均次數(shù)為n(n-1)/4?？梢詫γ芭菟惴ㄗ饕恍└倪M，如果算法第二行的某次

16、內(nèi)循環(huán)沒有進行元素交換，則說明排序工作已經(jīng)完成，可以退出外循環(huán)?？梢杂靡粋€布爾變量來記錄內(nèi)循環(huán)是否進行了記錄交換，如果沒有則終止外循環(huán)。冒泡法的另一個改進版本是雙向掃描冒泡法（Bi-Directional Bubble Sort）。設被排序的表中各元素鍵值序列為：483 67 888 50 255 406 134 592 657 745 683對該序列進行3次掃描后會發(fā)現(xiàn)，第3此掃描中最后一次交換的一對紀錄是L4和L5：50 67 255 134 | 406 483 592 657 683 745 888顯然，第3次掃描(i=3)結束后L5以后的序列都已經(jīng)排好序了，所以下一次掃描不必到達Las

17、t(L)-i=11-4=7，即第2行的for 循環(huán)j不必到達7，只要到達4-1=3就可以了。按照這種思路，可以來回地進行掃描，即先從頭掃到尾，再從尾掃到頭。這樣就得到雙向冒泡排序算法：procedure Bi-Directional_Bubble_Sort(var L:List);varlow,up,t,i:position;begin1 low:=First(L);up:=Last(L);2 while uplow do begin3 t:=low;4 for i:=low to up-1 do5 if LiLi+1 then begin6 swap(Li,Li+1);7 t:=i; end

18、;8 up:=t;9 for i:=up downto low+1 do10 if LiLj+1改為Lj= Lj+1，則不再是穩(wěn)定排序法。選擇排序 Selection Sort選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將Li.n中最小者與Li交換位置。這樣，經(jīng)過i遍處理之后，前i個記錄的位置已經(jīng)是正確的了。選擇排序算法可實現(xiàn)如下。procedure Selection_Sort(var L:List);vari,j,s:position;begin1 for i:=First(L) to Last(L)-1 do begin2 s:=i;3 for j:=i+1 t

19、o Last(L) do4 if Lj Ls then 5 s:=j; /記錄Li.n中最小元素的位置6 swap(Li,Ls); /交換Li,Lsend; end;算法Selection_Sort中里面的一個for循環(huán)需要進行n-i次比較，所以整個算法需要次比較。顯而易見，算法Selection_Sort中共調(diào)用了n-1次swap過程。選擇排序法是一個原地置換排序法，也是穩(wěn)定排序法。插入排序 Insertion Sort插入排序的基本思想是，經(jīng)過i-1遍處理后,L1.i-1己排好序。第i遍處理僅將Li插入L1.i-1的適當位置，使得L1.i又是排好序的序列。要達到這個目的，我們可以用順序比較

20、的方法。首先比較Li和Li-1，如果Li-1 Li，則L1.i已排好序，第i遍處理就結束了；否則交換Li與Li-1的位置，繼續(xù)比較Li-1和Li-2，直到找到某一個位置j(1ji-1)，使得Lj Lj+1時為止。圖1演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。圖1 對4個元素進行插入排序在下面的插入排序算法中，為了寫程序方便我們可以引入一個哨兵元素L0，它小于L1.n中任一記錄。所以，我們設元素的類型ElementType中有一個常量-，它比可能出現(xiàn)的任何記錄都小。如果常量-不好事先確定，就必須在決定Li是否向前移動之前檢查當前位置是否為1，若當前位置已經(jīng)為1時就

21、應結束第i遍的處理。另一個辦法是在第i遍處理開始時，就將Li放入L0中，這樣也可以保證在適當?shù)臅r候結束第i遍處理。下面的算法中將對當前位置進行判斷。插入排序算法如下：procedure Selection_Sort(var L:List);vari,j:position;v:ElementType;begin1 for i:=First(L)+1 to Last(L) do begin2 v:=Li;3 j:=i;4 while (jFirst(L)and(Lj-1 v) do /循環(huán)找到插入點 begin5 Lj:=Lj-1; /移動元素6 j:=j-1; end;7 Lj:=v; /插入元

22、素 end;end;下面考慮算法Insertion_Sort的復雜性。對于確定的i，內(nèi)while循環(huán)的次數(shù)為O(i)，所以整個循環(huán)體內(nèi)執(zhí)行了O(i)=O(i)，其中i從2到n。即比較次數(shù)為O(n2)。如果輸入序列是從大到小排列的，那么內(nèi)while循環(huán)次數(shù)為i-1次，所以整個循環(huán)體執(zhí)行了(i-1)=n(n-1)/2次。由此可知，最壞情況下，Insertion_Sort要比較(n2)次。如果元素類型是一個很大的紀錄，則算法第5行要消耗大量的時間，因此有必要分析移動元素的次數(shù)。經(jīng)過分析可知，平均情況下第5行要執(zhí)行n(n-1)/4次，分析方法與冒泡排序的分析相同。如果移動元素要消耗大量的時間，則可以用

23、鏈表來實現(xiàn)線性表，這樣Insertion_Sort可以改寫如下(當然前一個算法同樣也適用于鏈表，只不過沒下面這個好，但是下面算法這個比較復雜)：注意：在下面的算法中鏈表L增加了一個哨兵單元，其中的元素為-，即線性表L的第一個元素是L.nextprocedure Selection_Sort_II(var L:PList);vari,j,tmp:Position;begin1 if L.next=nil then exit; /如果鏈表L為空則直接退出2 i:=L.next; /i指向L的第一個元素，注意，L有一個哨兵元素，因此L.next才是L的第一個元素3 while i.nextnil d

24、o begin4 tmp:=i.next; /tmp指向Li的下一個位置5 j:=L;6 while (ji)and(tmp.data=j.next.data) do /從前向后找到tmp的位置，tmp應該插在j后面7 j:=j.next;8 if ji then /j=i說明不需要改變tmp的位置 begin9 i.next:=tmp.next; /將tmp從i后面摘除10 tmp.next:=j.next; /在j后面插入tmp11 j.next:=tmp; end12 else i:=i.next; /否則i指向下一個元素 end;end;上述改進算法主要是利用鏈表刪除和插入元素方便的特

25、性，對于數(shù)組則不適用。插入排序法是一個原地置換排序法，也是一個穩(wěn)定排序法。插入法雖然在最壞情況下復雜性為(n2)，但是對于小規(guī)模輸入來說，插入排序法是一個快速的原地置換排序法。許多復雜的排序法，在規(guī)模較小的情況下，都使用插入排序法來進行排序，比如快速排序和桶排序。堆排序：proceduresift(i,m:integer);調(diào)整以i為根的子樹成為堆,m為結點總數(shù)vark:integer;begina0:=ai;k:=2*i;在完全二叉樹中結點i的左孩子為2*i,右孩子為2*i+1whilek=mdobeginif(km)and(akak+1)theninc(k);找出ak與ak+1中較大值if

26、a0akthenbeginai:=ak;i:=k;k:=2*i;endelsek:=m+1;end;ai:=a0;將根放在合適的位置end;procedureheapsort;varj:integer;beginforj:=ndiv2downto1dosift(j,n);forj:=ndownto2dobeginswap(a1,aj);sift(1,j-1);end;end;歸并排序a為序列表，tmp為輔助數(shù)組proceduremerge(vara:listtype;p,q,r:integer);將已排序好的子序列ap.q與aq+1.r合并為有序的tmpp.rvarI,j,t:integer;

27、tmp:listtype;begint:=p;i:=p;j:=q+1;t為tmp指針，I,j分別為左右子序列的指針while(t=r)dobeginif(ir)or(ai=aj)滿足取左邊序列當前元素的要求thenbegintmpt:=ai;inc(i);endelsebegintmpt:=aj;inc(j);end;inc(t);end;fori:=ptordoai:=tmpi;end;mergeproceduremerge_sort(vara:listtype;p,r:integer);合并排序ap.rvarq:integer;beginifprthenbeginq:=(p+r-1)div

28、2;merge_sort(a,p,q);merge_sort(a,q+1,r);merge(a,p,q,r);end;end;mainbeginmerge_sort(a,1,n);end.快速排序 Quick Sort我們已經(jīng)知道，在決策樹計算模型下，任何一個基于比較來確定兩個元素相對位置的排序算法需要(nlogn)計算時間。如果我們能設計一個需要O(n1ogn)時間的排序算法，則在漸近的意義上，這個排序算法就是最優(yōu)的。許多排序算法都是追求這個目標。下面介紹快速排序算法，它在平均情況下需要O算法的基本思想快速排序的基本思想是基于分治策略的。對于輸入的子序列Lp.r，如果規(guī)模足夠小則直接進行排序

29、，否則分三步處理： 分解(Divide)：將輸入的序列Lp.r劃分成兩個非空子序列Lp.q和Lq+1.r，使Lp.q中任一元素的值不大于Lq+1.r中任一元素的值。 遞歸求解(Conquer)：通過遞歸調(diào)用快速排序算法分別對Lp.q和Lq+1.r進行排序。 合并(Merge)：由于對分解出的兩個子序列的排序是就地進行的，所以在Lp.q和Lq+1.r都排好序后不需要執(zhí)行任何計算Lp.r就已排好序。 這個解決流程是符合分治法的基本步驟的。因此，快速排序法是分治法的經(jīng)典應用實例之一。算法的實現(xiàn)算法Quick_Sort的實現(xiàn)：注意：下面的記號Lp.r代表線性表L從位置p到位置r的元素的集合，但是L并不

30、一定要用數(shù)組來實現(xiàn)，可以是用任何一種實現(xiàn)方法（比如說鏈表），這里Lp.r只是一種記號。procedure Quick_Sort(p,r:position;var L:List);conste=12;varq:position;begin1 if r-p=e then Insertion_Sort(L,p,r)/若Lp.r足夠小則直接對Lp.r進行插入排序 else begin2 q:=partition(p,r,L);/將Lp.r分解為Lp.q和Lq+1.r兩部分3 Quick_Sort(p,q,L); /遞歸排序Lp.q4 Quick_Sort(q+1,r,L);/遞歸排序Lq+1.r en

31、d;end;對線性表L1.n進行排序，只要調(diào)用Quick_Sort(1,n,L)就可以了。算法首先判斷Lp.r是否足夠小，若足夠小則直接對Lp.r進行排序，Sort可以是任何一種簡單的排序法，一般用插入排序。這是因為，對于較小的表，快速排序中劃分和遞歸的開銷使得該算法的效率還不如其它的直接排序法好。至于規(guī)模多小才算足夠小，并沒有一定的標準，因為這跟生成的代碼和執(zhí)行代碼的計算機有關，可以采取試驗的方法確定這個規(guī)模閾值。經(jīng)驗表明，在大多數(shù)計算機上，取這個閾值為12較好，也就是說，當r-p=e=12即Lp.r的規(guī)模不大于12時，直接采用插入排序法對Lp.r進行排序(參見 Sorting and Se

32、arching Algorithms: A Cookbook)。當然，比較方便的方法是取該閾值為1，當待排序的表只有一個元素時，根本不用排序(其實還剩兩個元素時就已經(jīng)在Partition函數(shù)中排好序了)，只要把第1行的if語句該為if p=r then exit else .。這就是通常教科書上看到的快速排序的形式。注意：算法Quick_Sort中變量q的值一定不能等于r，否則該過程會無限遞歸下去，永遠不能結束。因此下文中在partition函數(shù)里加了限制條件，避免q=r情況的出現(xiàn)。算法Quick_Sort中調(diào)用了一個函數(shù)partition，該函數(shù)主要實現(xiàn)以下兩個功能：1. 在Lp.r中選擇一

33、個支點元素pivot; 2. 對Lp.r中的元素進行整理，使得Lp.q分為兩部分Lp.q和Lq+1.r，并且Lp.q中的每一個元素的值不大于pivot，Lq+1.r中的每一個元素的值不小于pivot，但是Lp.q和Lq+1.r中的元素并不要求排好序。 快速排序法改進性能的關鍵就在于上述的第二個功能，因為該功能并不要求Lp.q和Lq+1.r中的元素排好序。函數(shù)partition可以實現(xiàn)如下。以下的實現(xiàn)方法是原地置換的，當然也有不是原地置換的方法，實現(xiàn)起來較為簡單，這里就不介紹了。function partition(p,r:position;var L:List):position;varpiv

34、ot:ElementType;i,j:position;begin1 pivot:=Select_Pivot(p,r,L); /在Lp.r中選擇一個支點元素pivot2 i:=p-1;3 j:=r+1;4 while true do begin5 repeat j:=j-1 until Lj=pivot; /移動右指針，注意這里不能用while循環(huán)7 if i j then swap(Li,Lj) /交換Li和Lj8 else if jr then return j /返回j的值作為分割點9 else return j-1; /返回j前一個位置作為分割點 end;end;該算法的實現(xiàn)很精巧。其

35、中，有一些細節(jié)需要注意。例如，算法中的位置i和j不會超出Ap.r的位置界，并且該算法的循環(huán)不會出現(xiàn)死循環(huán)，如果將兩個repeat語句換為while則要注意當Li=Lj=pivot且ij時i和j的值都不再變化，會出現(xiàn)死循環(huán)。另外，最后一個if.then.語句很重要，因為如果pivot取的不好，使得Partition結束時j正好等于r，則如前所述，算法Quick_Sort會無限遞歸下去；因此必須判斷j是否等于r，若j=r則返回j的前驅(qū)。以上算法的一個執(zhí)行實例如圖1所示，其中pivot=Lp=5：圖1 Partition過程的一個執(zhí)行實例Partition對Lp.r進行劃分時，以pivot作為劃分的

36、基準，然后分別從左、右兩端開始，擴展兩個區(qū)域Lp.i和Lj.r，使得Lp.i中元素的值小于或等于pivot，而Lj.r中元素的值大于或等于pivot。初始時i=p-1，且j=i+1，從而這兩個區(qū)域是空的。在while循環(huán)體中，位置j逐漸減小，i逐漸增大，直到LipivotLj。如果這兩個不等式是嚴格的，則Li不會是左邊區(qū)域的元素，而Lj不會是右邊區(qū)域的元素。此時若i在j之前，就應該交換Li與Lj的位置，擴展左右兩個區(qū)域。 while循環(huán)重復至i不再j之前時結束。這時Lp.r己被劃分成Lp.q和Lq+1.r，且滿足Lp.q中元素的值不大于Lq+1.r中元素的值。在過程Partition結束時返回

37、劃分點q。尋找支點元素select_pivot有多種實現(xiàn)方法，不同的實現(xiàn)方法會導致快速排序的不同性能。根據(jù)分治法平衡子問題的思想，我們希望支點元素可以使Lp.r盡量平均地分為兩部分，但實際上這是很難做到的。下面我們給出幾種尋找pivot的方法。1. 選擇Lp.r的第一個元素Lp的值作為pivot； 2. 選擇Lp.r的最后一個元素Lr的值作為pivot； 3. 選擇Lp.r中間位置的元素Lm的值作為pivot； 4. 選擇Lp.r的某一個隨機位置上的值Lrandom(r-p)+p的值作為pivot； 按照第4種方法隨機選擇pivot的快速排序法又稱為隨機化版本的快速排序法，在下面的復雜性分析中

38、我們將看到該方法具有平均情況下最好的性能，在實際應用中該方法的性能也是最好的。下面是一個快速排序的Java Applet演示程序，該程序使用第一種pivot選擇法，即選Lp為pivot，因此Partition過程作了一些簡化，與我們這里的Partition過程實現(xiàn)方法不同，但功能相同。該程序是針對用數(shù)組實現(xiàn)的線性表，用C語言實現(xiàn)的。 性能分析下面我們就最好情況，最壞情況和平均情況對快速排序算法的性能作一點分析。注意：這里為方便起見，我們假設算法Quick_Sort的范圍閾值為1（即一直將線性表分解到只剩一個元素），這對該算法復雜性的分析沒有本質(zhì)的影響。我們先分析函數(shù)partition的性能，該

39、函數(shù)對于確定的輸入復雜性是確定的。觀察該函數(shù)，我們發(fā)現(xiàn)，對于有n個元素的確定輸入Lp.r，該函數(shù)運行時間顯然為(n)。最壞情況無論適用哪一種方法來選擇pivot，由于我們不知道各個元素間的相對大小關系（若知道就已經(jīng)排好序了），所以我們無法確定pivot的選擇對劃分造成的影響。因此對各種pivot選擇法而言，最壞情況和最好情況都是相同的。我們從直覺上可以判斷出最壞情況發(fā)生在每次劃分過程產(chǎn)生的兩個區(qū)間分別包含n-1個元素和1個元素的時候(設輸入的表有n個元素)。下面我們暫時認為該猜測正確，在后文我們再詳細證明該猜測。對于有n個元素的表Lp.r，由于函數(shù)Partition的計算時間為(n)，所以快速

40、排序在序壞情況下的復雜性有遞歸式如下：T(1)=(1), T(n)=T(n-1)+T(1)+(n) (1)用迭代法可以解出上式的解為T(n)=(n2)。這個最壞情況運行時間與插入排序是一樣的。下面我們來證明這種每次劃分過程產(chǎn)生的兩個區(qū)間分別包含n-1個元素和1個元素的情況就是最壞情況。設T(n)是過程Quick_Sort作用于規(guī)模為n的輸入上的最壞情況的時間，則T(n)=max(T(q)+T(n-q)+(n) ,其中1qn-1 (2)我們假設對于任何k0,b0為待定常數(shù)?？梢赃x擇足夠大的a,b使anlogn+bT(1)，對于n1有： （8）下面我們來確定和式 （9）的界。因為和式中每一項至多是nlogn，則有界：這是個比較緊的界，但是對于解遞歸式（8）來說