chapter2-Sorting算法和算法的分析技術(shù)課件

chapter2Sorting算法和算法的分析技術(shù)6、露凝無游氛，天高風(fēng)景澈。7、翩翩新來燕，雙雙入我廬，先巢故尚在，相將還舊居。8、吁嗟身后名，于我若浮煙。9、陶淵明（約365年—427年），字元亮，（又一說名潛，字淵明）號(hào)五柳先生，私謚“靖節(jié)”，東晉末期南朝宋初期詩人、文學(xué)家、辭賦家、散文家。漢族，東晉潯陽柴桑人（今江西九江）。曾做過幾年小官，后辭官回家，從此隱居，田園生活是陶淵明詩的主要題材，相關(guān)作品有《飲酒》、《歸園田居》、《桃花源記》、《五柳先生傳》、《歸去來兮辭》等。10、倚南窗以寄傲，審容膝之易安。chapter2Sorting算法和算法的分析技術(shù)chapter2Sorting算法和算法的分析技術(shù)6、露凝無游氛，天高風(fēng)景澈。7、翩翩新來燕，雙雙入我廬，先巢故尚在，相將還舊居。8、吁嗟身后名，于我若浮煙。9、陶淵明（約365年—427年），字元亮，（又一說名潛，字淵明）號(hào)五柳先生，私謚“靖節(jié)”，東晉末期南朝宋初期詩人、文學(xué)家、辭賦家、散文家。漢族，東晉潯陽柴桑人（今江西九江）。曾做過幾年小官，后辭官回家，從此隱居，田園生活是陶淵明詩的主要題材，相關(guān)作品有《飲酒》、《歸園田居》、《桃花源記》、《五柳先生傳》、《歸去來兮辭》等。10、倚南窗以寄傲，審容膝之易安。計(jì)算機(jī)算法

——設(shè)計(jì)與分析導(dǎo)論南開大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系劉璟2Chapter2. Sorting算法與算法的分析技術(shù)2.1排序(Sorting)問題2.2O(n2)階的排序算法2.3基于相鄰元比較的排序算法和希爾(Shell)排序2.4O(nlogn)階的排序算法2.5 比較排序算法的時(shí)間復(fù)雜度下界2.6 排序算法的有關(guān)研究3計(jì)算機(jī)算法

——設(shè)計(jì)與分析導(dǎo)論南開大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系劉璟2Chapter2. Sorting算法與算法的分析技術(shù)2.1排序(Sorting)問題

2.2O(n2)階的排序算法

2.3基于相鄰元比較的排序算法和希爾(Shell)排序2.4O(nlogn)階的排序算法

2.5 比較排序算法的時(shí)間復(fù)雜度下界

2.6 排序算法的有關(guān)研究

32.1排序（Sorting）問題

有關(guān)排序的幾個(gè)基本概念：1.全序集：數(shù)據(jù)集合D稱為關(guān)于關(guān)系“<”的全序集，如果滿足1°a<b，a=b，b<a三者必居其一；2°a<b，b<c，則a<c。全體整數(shù)集、實(shí)數(shù)集、字符串集等都是全序集。2.排序（Sorting）問題：已知：n項(xiàng)記錄R1，R2，…，Rn，其一個(gè)域稱為關(guān)鍵字（Key），關(guān)鍵字值K1，K2，…，Kn屬于一全序集。要求：重排n項(xiàng)記錄為Rπ(1)，Rπ(2)，…，Rπ(n)，其中π：π(1)，π(2)，…，π(n)，為1,…,n的一個(gè)排列，使對(duì)應(yīng)的關(guān)鍵字滿足：Kπ(1)≤Kπ(2)≤…≤Kπ(n)。43.穩(wěn)定（Stable）排序算法：如果排序問題滿足：若Rπ(i)=Rπ(j)

且i<j則π(i)<π(j)，則稱其為穩(wěn)定排序算法。穩(wěn)定排序保證序列中關(guān)鍵字相同的記錄在排序過程中不會(huì)交換次序。4.內(nèi)部（Internal）排序算法：數(shù)據(jù)在高速隨機(jī)存儲(chǔ)設(shè)備上（內(nèi)存）進(jìn)行排序操作，這時(shí)數(shù)據(jù)間的比較和移動(dòng)指令的代價(jià)一般是相同的。5.外部（External）排序算法：數(shù)據(jù)主要駐留在外部的低速存儲(chǔ)設(shè)備（硬盤、磁帶）上，數(shù)據(jù)在內(nèi)存與硬盤（磁帶）之間的傳送、移動(dòng)的代價(jià)明顯高于數(shù)據(jù)比較操作，因此，外部排序算法的設(shè)計(jì)不同于內(nèi)部排序。56.原址排序算法：在排序過程中除了全部輸入數(shù)據(jù)所占用的空間之外，只需有限的額外空間。如果額外空間的大小與記錄數(shù)n無關(guān)，則稱為原址排序。7.基于關(guān)鍵字比較的排序算法：這類排序算法中僅對(duì)關(guān)鍵字進(jìn)行比較和移動(dòng)操作，因此關(guān)鍵字的比較和移動(dòng)是算法的基本操作。62.2O(n2)階的排序算法

2.2.1選擇排序（SelectionSorting）

1.選擇排序的思想：把待排序的L[1..n]視為兩個(gè)部分：L[1..i-1]為已排序部分，L[i..n]為未排序部分。排序步驟為：

1°i=1；2°選擇：在L[i..n]中求最小元L[k]，i≤k≤n；3°交換L[i]與L[k]，i++，if（i<n）goto2°；4°停止。2.算法的描述：輸入：L[1..n]存放待排序元素，n(≥0)為元素個(gè)數(shù)。輸出：L[1..n]按關(guān)鍵字遞增順序排列。算法2.1選擇排序算法SelectSort73.算法的分析：

關(guān)鍵字的比較發(fā)生在if語句中，總的比較次數(shù)為：算法中的比較次數(shù)與n個(gè)關(guān)鍵字的值無關(guān)，因此最壞情形和平均情形的比較總次數(shù)相同。因此，算法是O(n2)階的?？臻g代價(jià)只額外占用了幾個(gè)工作單元，因此，它是個(gè)原址排序算法。

84.討論：

算法SelectSort按比較次數(shù)計(jì)算的最好情形時(shí)間復(fù)雜度為：如果把關(guān)鍵字的移動(dòng)作為基本操作，情況有所不同。從算法中的if語句可看出，關(guān)鍵字移動(dòng)min=L[j]的次數(shù)可能少于比較min>L[j]的執(zhí)行次數(shù)。另外，函數(shù)Swap()需要3次移動(dòng)，共3(n–1)次。因此，選擇排序算法的平均移動(dòng)次數(shù)會(huì)比較小，而最好情形則為3(n–1)。當(dāng)數(shù)據(jù)記錄比較大時(shí)，移動(dòng)代價(jià)大于比較代價(jià)，選擇排序也可能有較好的性能。92.2.2插入排序（InsertionSorting）

1.插入排序的思路：與選擇排序不同，它是從無序部分不經(jīng)選擇，任取一元，然后插入到有序部分的正確位置上。其步驟為：L[1..n]分為兩部分：L[1..i]為有序部分，L[i+1..n]為未排序部分。1°i=1；2°把L[i+1]插入到L[1..i]中的正確位置，i++；3°if(i<n)goto2°；4°停止。2.算法的描述：算法2.2插入排序算法InsertSort103.算法的分析：最壞情形：最好情形：平均情形：設(shè)輸入序列滿足兩個(gè)條件：1°n個(gè)關(guān)鍵字值是不同的，這可以簡(jiǎn)化分析；2°n個(gè)元素的所有不同的排列具有等可能性。在把L[i]插入到有序的L[1..i–1]的過程中，共有i種可能的位置，由假設(shè)2°可知落入每個(gè)位置的概率為1/i。而這i種情形所需要的比較次數(shù)分別為1，2，…，i-2，i-1，i-1，因此期望的比較次數(shù)為：11因此，

插入排序雖然也是O(n2)階的算法，但在一般情形下，會(huì)比選擇排序塊。算法的空間代價(jià)：基本上不需要額外空間，也是一種原址排序算法。它也是穩(wěn)定的。124.討論：在基于相鄰元比較交換的排序算法中，InsertSort是最優(yōu)的。如果把數(shù)據(jù)的移動(dòng)作為基本操作，每一次數(shù)據(jù)比較都有一次數(shù)據(jù)移動(dòng)與之對(duì)應(yīng)。因此，除了在外循環(huán)的n–1次移動(dòng)之外，數(shù)據(jù)比較與移動(dòng)次數(shù)是一致的，這與SelectSort算法是不同的。2.2.3起泡排序（BubbleSorting）

算法2.3起泡排序算法BubbleSort

算法BubbleSort的比較次數(shù)是確定的：移動(dòng)次數(shù)與數(shù)據(jù)比較相對(duì)應(yīng)，交換函數(shù)Swap需要三次數(shù)據(jù)移動(dòng)，在最壞情形下是比較次數(shù)的三倍，而在最好情形下不需要移動(dòng)。13BubbleSort是穩(wěn)定的、原址排序算法。BubbleSort的一種實(shí)用改進(jìn)算法是在程序中設(shè)一標(biāo)記位，當(dāng)一遍掃描中沒有交換發(fā)生，則排序停止。算法2.4起泡排序的改進(jìn)算法BSort

算法BSort的比較次數(shù)有所改進(jìn)：142.3基于相鄰元比較的排序算法和

希爾（Shell）排序

2.3.1插入排序的最優(yōu)性定理2.1基于相鄰元的比較及交換的排序算法1°在最壞情形下，至少需要n(n-1)/2次比較，即W(n)=Ω(n2)；2°在平均情形下，至少需要n(n-1)/4次比較，即A(n)=Ω(n2)。把n個(gè)元素排列問題歸結(jié)為以n個(gè)關(guān)鍵字1,2,…,n的任一排列π：π(1),π(2),…,π(n)作為輸入，排序過程就是消滅序列中的逆序的過程。所謂逆序（Inversion）（π(i),π(j)），即i<j且π(i)>π(j)。例如序列（2，4，1，5，3）有4個(gè)逆序：（2，1），（4，1），（4，3），（5，3）；15證明的關(guān)鍵是，在序列中，如果兩個(gè)相鄰元為一逆序，經(jīng)過交換肯定消除了這個(gè)逆序，但這一交換只能消滅這一個(gè)逆序。證明：1°存在一種排列：n,n-1,…,2,1為全逆序，共包含n(n-1)/2個(gè)逆序，故在最壞情形，任一依靠相鄰元比較、交換完成的排序過程，至少需n(n-1)/2次比較，即W(n)=Ω(n2)。2°對(duì)于平均情形，實(shí)際上需要計(jì)算1,2,…,n的所有不同排列的平均逆序數(shù)。當(dāng)n>1時(shí)，任一排列π，必有一個(gè)唯一的、不同于它的對(duì)偶排列；π’是π的對(duì)偶排列，即π’是π的反序：π’(1)=π(n)，π’(2)=π(n-1),…,π’(n)=π(1)，例如，(2,4,1,5,3)的對(duì)偶排列是(3,5,1,4,2)；1～n之間的任一整數(shù)對(duì)（i,j）（i≠j）如果是逆序，必然出現(xiàn)在任一排列π及其對(duì)偶排列π’二者之一；161～n之間共有不同的整數(shù)對(duì)（i,j）n(n-1)/2個(gè)；1,…,n的所有排列是成對(duì)出現(xiàn)的，故每一排列平均有n(n-1)/4個(gè)逆序，平均至少需n(n-1)/4次比較，即A(n)=Ω(n2)。由定理知：1°算法InsertSort和BSort在上述條件下是最優(yōu)的；2°為了設(shè)計(jì)比θ(n2)階更快的排序算法，數(shù)據(jù)的比較和移動(dòng)必須在間隔較大的元素之間進(jìn)行。2.3.2希爾（Shell）排序

該排序算法首先把輸入序列分成h個(gè)間距為h的子序列，對(duì)每個(gè)子序列進(jìn)行h–sorting。例如，取h=6，則L[1..n]分為6個(gè)子序列：17L[1],L[7],L[13],…L[2],L[8],L[14],…L[3],L[9],L[15],…L[4],L[10],L[16],…L[5],L[11],L[17],…L[6],L[12],L[18],…進(jìn)行h–sorting后，就是逐步減少h的大小，直至把h減少到1，完成排序工作。在最后一次h=1時(shí)，采用InsertSort或BSort算法，可能出現(xiàn)最好情形或幾乎最好情形，而InsertSort的B(n)=n-1，故總比較次數(shù)有望縮小。Shell排序算法有幾個(gè)因素可以有大的變化：第一個(gè)h值如何取，h值如何逐步減少到1每次h–sorting采用何種算法，都對(duì)整個(gè)算法性能有大的影響。18Shell排序算法：輸入：KeyL[1..n]：關(guān)鍵字?jǐn)?shù)組；inth[1..t]：遞增整數(shù)序列，h[1]=1；算法2.5希爾排序算法ShellSort當(dāng)t=1時(shí)，ShellSort退化為InsertSort。增量序列ht,ht-1,…h(huán)1=1應(yīng)事先確定，一個(gè)較好的選擇是：h1=1,hs+1=3hs+1其中1≤s≤t使ht+1<n，ht+2≥n。當(dāng)n比較大時(shí)，Shell排序比插入排序要快，因?yàn)楫?dāng)ht>1時(shí)，在h-sort過程中，一次比較和交換可以至多消除2ht-3個(gè)逆序。關(guān)于Shell排序的研究至今仍在繼續(xù)，因?yàn)閷?duì)于已知的n，怎樣的增量h序列使算法性能最佳，其最優(yōu)時(shí)間復(fù)雜度如何，目前尚不清楚。一些比較好的成果指出，適當(dāng)選取增量序列，Shell排序算法的復(fù)雜度可以達(dá)到O(nlog2n)和O(n1.25)。192.4O(nlogn)階的排序算法

2.4.1快速排序算法QuickSort

1.算法的思路：其關(guān)鍵操作是劃分（partition）：取n元中的任一元（例如首元）作為劃分元（pivot），令其余n–1個(gè)元與劃分元經(jīng)過比較，把較小者移至劃分元左邊，而較大者置于劃分元之右，形成兩個(gè)序列。左序列的所有元都小于劃分元，右序列都不小于劃分元，然后用同樣的方法對(duì)左、右序列排序，從而完成排序目標(biāo)。如Fig.2.1所示。劃分過程中，劃分元被放置到了排序過程的最終位置，其左、右兩個(gè)序列雖然是無序的，但作為整體卻被確定了位置，因此在完成左、右子序列的排序之后，整個(gè)排序過程也就完成。20212.算法QuickSort：

輸入：未排序的L[1..n]，為了方便寫遞歸程序可表示為L(zhǎng)[first..last]。輸出：已排序的L[first..last]。算法2.6快速排序算法QuickSort3.劃分算法Partition：

QuickSort的核心是Partition。劃分過程中，元素在數(shù)組中有較大幅度的移動(dòng)，因此，這也是快速排序速度較快的內(nèi)在原因。有各種不同的劃分算法，其性能也不盡相同。一種較好的劃分算法，其思想如Fig.2.2所示。2223程序開始，指針left=first，指向空位，即劃分元pivot的位置，指針right=last，指向最右元，序列L[2..n]全為未做劃分處理部分；首先自right開始，向左掃描，找到第一個(gè)小于pivot的元素，把它送往left指向的左空位，left右移一位；然后從left向右掃描，找到第一個(gè)不小于pivot的元素，把它送到right指向的位置（右空位），right左移一位，完成劃分的一次循環(huán)。重復(fù)上述循環(huán)，直到left=right，令L[left]=pivot，返回left。算法2.7快速排序的劃分算法Partition24劃分過程中的實(shí)例：

254.QuickSort的復(fù)雜度分析：

最壞情形的總比較次數(shù)為：平均時(shí)間性能分析：首先假設(shè)：1°n個(gè)元素的關(guān)鍵字值互不相等。2°n個(gè)元素的關(guān)鍵字的所有不同排列，以等可能即相等的概率出現(xiàn)在輸入序列中，因此，劃分元的最終位置i也以相等概率分別取值為1,…,n。QuickSort的平均比較次數(shù)A(n)應(yīng)滿足遞歸方程：

26可簡(jiǎn)化為： （公式2.4.1）在最好情形時(shí)劃分元總是處于序列的中間，遞歸方程可大致簡(jiǎn)化成：27定理2.2在輸入序列的所有排列具有等可能性的條件下，算法QuickSort的平均數(shù)據(jù)比較次數(shù)為:其中c>0為一常數(shù)。證明方法1：采用歸納法

當(dāng)n=1時(shí)，A(n)=0，cnlnn=0，命題成立；假設(shè)當(dāng)1≤k＜n，A(K)≤cklnk成立；由公式2.4.1和假設(shè)得：

根據(jù)積分的性質(zhì)：28于是，當(dāng)n＞1取c=2時(shí)，A(n)≤2nlnn成立。推論2.3在輸入序列的不同排序均勻分布的假設(shè)條件下，算法QuickSort的平均數(shù)據(jù)比較次數(shù)為:

證明方法2：為了簡(jiǎn)化關(guān)于A(n)的遞歸方程，由

29推出：為了消除過多的A(i)項(xiàng)，計(jì)算nA(n)-(n-1)A(n-1)：即 令 則有：30這是一個(gè)較為簡(jiǎn)單的遞歸方程，不難得到：由Harmonic級(jí)數(shù)， 為Euler常數(shù)，

，得：31

由此可以得到A(n)的更準(zhǔn)確的表達(dá)式：5.空間復(fù)雜度分析：

單從劃分算法來看，QuickSort除有限的工作單元外，不占用額外的空間，但在遞歸過程中，待排序段的首元和尾元下標(biāo)需要保存，在最壞情形可能遞歸n–1次。因此，QuickSort在最壞情形下需要的空間代價(jià)為S(n)=θ(n)。326.關(guān)于QuickSort算法的幾點(diǎn)討論：

1）在最重要的性能，即平均時(shí)間代價(jià)上優(yōu)于其它算法。當(dāng)n比較大時(shí)，一般運(yùn)行確實(shí)很快，因此被廣泛采用。2）改善劃分元的選取，可能產(chǎn)生更好的效果。常見的幾種劃分元的選取方法是：

·在first,…,last中取隨機(jī)數(shù)i，以L[i]代替L[1]；

·

在first,…,last中，取中間值i=int((first+last)/2)；

·

取first，last，int（（first+last）/2）三者的中值為劃分元下標(biāo)。3）算法的核心是劃分。不同的劃分策略會(huì)影響到移動(dòng)次數(shù)。4）QuickSort采用遞歸算法的形式，簡(jiǎn)明但運(yùn)行時(shí)在時(shí)間和空間上開銷較大。一種改進(jìn)方法是使用由用戶設(shè)計(jì)的棧取代遞歸。算法2.8快速排序的改進(jìn)算法QStackSort

335）空間復(fù)雜度的改進(jìn)：快速排序算法的額外空間需求與遞歸和棧有關(guān)。當(dāng)把兩次遞歸調(diào)用改為單側(cè)進(jìn)棧，可以改進(jìn)空間復(fù)雜度。當(dāng)輸入為升序（已排序）時(shí)，共需n–1次進(jìn)棧，占用O(n)空間。如果在程序中，每進(jìn)行一次劃分以后，就對(duì)[f,i-1],[i+1,l]兩段進(jìn)行比較，把較大的一半進(jìn)棧，先計(jì)算（劃分）較小的一半，其內(nèi)層循環(huán)次數(shù)（即棧的長(zhǎng)度）必然小于logn，因此空間代價(jià)可降為O(logn)。6）快速排序算法對(duì)于較小的n，其性能不及插入算法。因此，可以設(shè)計(jì)一種綜合算法，當(dāng)輸入序列長(zhǎng)度小于某個(gè)固定值（例如n0=50）時(shí)，改用InsertSort進(jìn)行排序。7）快速排序的最壞情形時(shí)間復(fù)雜度和額外空間代價(jià)，無論如何改進(jìn)，總是它的缺點(diǎn)和不足。342.4.2合并排序算法MergeSort

1.算法的思路：

把序列分為兩部分，分別遞歸（排序）后，再把兩個(gè)有序序列合并為一個(gè)有序序列。如Fig.2.4。352.有序序列的合并算法：

算法2.9有序序列的合并算法Merge

3.合并排序算法MergeSort：算法2.10合并排序算法MergeSort

4.算法的復(fù)雜度分析：

該算法對(duì)兩個(gè)長(zhǎng)度為m的有序序列的合并，在最壞情形下至少需要2m–1次比較。算法在最壞情形下的比較次數(shù)可用遞歸方程表示： （公式2.4.2）36忽略n為奇數(shù)的情形，由主項(xiàng)定理可得 。假定n=2k（k為正整數(shù)），則公式2.4.2可以簡(jiǎn)化為：直接推導(dǎo)得：該算法平均情形比較次數(shù)A(n)=Ω(nlogn)。其空間代價(jià)較大，需要大小為O(n)的額外空間。該算法是不穩(wěn)定的。375.關(guān)于合并排序算法的討論：

1）對(duì)于時(shí)間復(fù)雜度而言，在最壞情形下大大優(yōu)于快速排序，但在平均情況下不一定優(yōu)于快速排序。數(shù)據(jù)的移動(dòng)次數(shù)也會(huì)對(duì)時(shí)間性能有所影響。2）可以比較容易地改寫成非遞歸程序。3）合并排序的一種改進(jìn)方法是充分利用輸入序列中可能的已排序部分。算法2.11合并排序改進(jìn)算法IIMergeSort2

例如，輸入序列為（4，12，8，6，0，11，27，5，20），實(shí)際上是4個(gè)有序串：（4，12），（8），（6，，11，27），（5，20）。第一趟掃描合并為：（4，8，12），（5，6，9，11，20，27），第二趟掃描就已排好序。這個(gè)算法在在最好情形下的比較次數(shù)為B(n)=n–1。384）主要缺點(diǎn)是空間代價(jià)較大，每次合并操作都需要與待合并的數(shù)據(jù)等長(zhǎng)的額外空間，其額外空間代價(jià)為O(n)階。

5）適合于并行計(jì)算。2.4.3堆排序算法HeapSort

1.堆排序算法的思路：

如Fig.2.5，算法把待排序的數(shù)組L[1..n]視為一個(gè)二叉樹，數(shù)組元素依次按廣度第一的順序與二叉樹的結(jié)點(diǎn)相對(duì)應(yīng)。結(jié)點(diǎn)間的鏈接利用下標(biāo)來計(jì)算。對(duì)于結(jié)點(diǎn)i，如果2i>n，則i為葉結(jié)點(diǎn)，否則，2i為其左兒子下標(biāo)，2i+1為其右兒子下標(biāo)。39這樣的二叉樹的所有的葉結(jié)點(diǎn)位于樹的最底層即d層或d–1層，在最底層的葉結(jié)點(diǎn)位于左端。算法由兩部分組成，第一部分稱為建堆（BuildingHeap），就是通過數(shù)據(jù)的比較和移動(dòng)，使得二叉樹上每個(gè)內(nèi)部節(jié)點(diǎn)的值大于其左、右子結(jié)點(diǎn)的值。這樣的二叉樹稱為堆（Heap），如Fig.2.6所示。40第二部分稱為根刪除—堆修復(fù)（Delete–Fix）過程，如Fig.2.7，可以描述為：for(i=n;i>=2;i--){Swap(L[1],L[i]);FixHeap(L[1..i-1]);}堆的修復(fù)過程，就是每次把兩個(gè)兒子中的較大者上升，直到元素L[i]降到適當(dāng)?shù)奈恢脼橹?。這一Delete–Fix過程至多重復(fù)n次，每次修復(fù)所需的比較次數(shù)不會(huì)大于樹高，而平衡二叉樹的高不會(huì)大于logn（n為結(jié)點(diǎn)數(shù)），故此算法應(yīng)有較好的性能。2.算法的描述：

算法2.12堆排序算法HeapSort

41423.算法的分析：

令n'=2d–1且n'/2≤n≤n'，并把建堆過程寫成遞歸形式：voidBHeap(H){BHeap(Hleft);BHeap(Hright);FixHeap(L,n,root,L[root]);return;}它與函數(shù)BuildHeap是等價(jià)的。由于FixHeap(L,n',root,L[root])的比較次數(shù)為2logn'，故有：43根據(jù)主項(xiàng)定理：因?yàn)閎=2，c=2，取ε=0.1，有

故

因此，建堆過程在最壞情形下的時(shí)間復(fù)雜度為線性階。對(duì)于算法的第二部分，因?yàn)閷?duì)于有k個(gè)結(jié)點(diǎn)的堆進(jìn)行修復(fù)，至多需要 次比較，即全部比較次數(shù)至多為：

44定理2.4

HeapSort在最壞情形下的數(shù)據(jù)比較次數(shù)為W(n)=2nlogn+O(n)，即HeapSort是一個(gè)θ(nlogn)階的排序算法。HeapSort在平均情形下的比較次數(shù)是O(nlogn)。它是一個(gè)原址排序算法。4.堆排序算法的缺點(diǎn)：

1）當(dāng)輸入序列為有序或幾乎有序時(shí)，堆排序算法根本沒有利用序列有序的條件，需要θ(nlogn)次比較，與最壞情形相比幾乎沒有改進(jìn)。2）堆排序大約需要2*nlogn次比較，在大多數(shù)情況下，比快速排序和合并排序要慢。5.加速堆排序算法AHeapSort：

在原來的FixHeap算法中，每一次需要做兩次比較，即：if(L[vac*2]<L[vac*2+1])和if(k<L[larger])。改進(jìn)后的AFixHeap算法，每一步只做一次比較。45算法2.13改進(jìn)的堆恢復(fù)過程AfixHeap

在大多數(shù)情況下，第一個(gè)循環(huán)把空位移至葉結(jié)點(diǎn)，共用logn次比較，而向上的移動(dòng)次數(shù)則很少。結(jié)點(diǎn)的比較次數(shù)在最壞情形下仍為2logn，但在大多數(shù)情況下則接近（大于）logn。如Fig.2.9所示。46為了把最壞情形下的比較次數(shù)由2nlogn縮小到nlogn，進(jìn)一步改進(jìn)的思路描述如下：設(shè)堆的高度為 ，空位的移動(dòng)分為下移和上移，每下移、上移一層需要一次比較。開始時(shí)空位在頂點(diǎn)，設(shè)待插入元素的最終應(yīng)插入的位置在h層，0≤h≤H。1°m=H/2；2°空位下移m層，共用m次比較；3°if(L[vac/2]<k)goto5°；4°m/=2;goto2°；5°空位上移至最終位置，至多用m次比較。利用這一改進(jìn)，AheapSort在最壞情形下的數(shù)據(jù)比較次數(shù)應(yīng)為W(n)=nlogn+nloglogn+O(n)。476.另一種樹排序算法：

如果排序時(shí)建成一個(gè)頂元最小的堆（如圖Fig.2.10），根消除后很難修復(fù)（合并）為一個(gè)堆，這就是堆排序?yàn)槭裁匆炎畲笤胤诺蕉秧數(shù)脑颉?/p>

48有改進(jìn)算法LheapSort，把數(shù)組L[1..n]視為一個(gè)被稱為左完全2-3樹（簡(jiǎn)稱LECT樹或L樹）的樹結(jié)構(gòu)。實(shí)例：L[1..n]，n=23。

每次取不大于剩余元素?cái)?shù)的2k-1個(gè)元素形成一個(gè)完全二叉樹，因n=15+7+1，故n=23個(gè)元的數(shù)組唯一地與Fig.2.11的樹結(jié)構(gòu)對(duì)應(yīng)。數(shù)組元素按深度優(yōu)先的順序排列。49對(duì)于下標(biāo)為i的結(jié)點(diǎn)，i+1是其左子結(jié)點(diǎn)的下標(biāo)，右子結(jié)點(diǎn)的下標(biāo)則需要利用其右鄰?fù)耆珮涞母聵?biāo)r來計(jì)算，即(i+r+1)/2。例如，結(jié)點(diǎn)2的左子結(jié)點(diǎn)下標(biāo)為3=2+1，該完全樹的右子結(jié)點(diǎn)下標(biāo)為6=（2+9+1）/2。這需要至多為logn的額外空間來保存各個(gè)完全子樹的根下標(biāo)，即保留24、9、2、1四個(gè)值。LHeapSort同樣由兩部分——建堆過程和刪除—整理過程組成建堆過程之后，L[1..n]已經(jīng)對(duì)應(yīng)一個(gè)n=23結(jié)點(diǎn)的左完全2-3樹，故L[1]已是最小元。前幾步刪除—整理過程如圖：50515253

刪去L[1]，空位置不動(dòng)，由L[2..23]形成另一棵L樹—LT2；

LT2已是一個(gè)堆，故不需整理，轉(zhuǎn)至下一步刪除—整理；

刪去L[2]，由L[3..23]形成新的L樹—LT3；

整理LT3稱為堆，其過程與HeapSort的FixHeap過程類似。一個(gè)簡(jiǎn)單的實(shí)例：n=11，L[1..11]={8，4，7，2，3，9，6，1，10，11，5}。下圖是LheapSort(L,n)的排序過程，其中1～11步是建堆過程，12～23步是刪除—整理過程。54557.算法LHeapSort的分析：

1）最壞情形和平均情形：在最壞情形下的時(shí)間復(fù)雜度為W(n)=θ(nlogn)。LHeapSort在最壞情形、平均情形下的性能與HeapSort大致相同。已有的研究成果指出，LHeapSort在最壞情形下的移動(dòng)次數(shù)約為1.5nlogn次。2）最好情形：

表2.1有序條件下的各種算法性能

當(dāng)輸入序列為有序時(shí)，LHeapSort極快，不同算法的實(shí)驗(yàn)數(shù)據(jù)如表：56LHeapSort在最好情形下的比較次數(shù)為B(n)=2n=O(n)，數(shù)據(jù)移動(dòng)次數(shù)為0次，而HeapSort在最好情形下的復(fù)雜度為B(n)=θ(nlogn)，已有的研究結(jié)果認(rèn)為是B(n)≥nlogn/2。3）當(dāng)輸入序列為幾乎有序時(shí)，性能比其它排序算法要好。4）空間代價(jià)：LHeapSort在排序過程中需要一個(gè)長(zhǎng)度為logn+1的整型數(shù)組，用于存放各個(gè)完全數(shù)的根的下標(biāo)。572.5排序算法的時(shí)間復(fù)雜度下界

2.5.1判定樹（DecisionTree）模型對(duì)于n=3，設(shè)三個(gè)關(guān)鍵字為a，b，c，可以用程序區(qū)分出六種可能的排列次序。它對(duì)應(yīng)于Fig.2.13的判定樹（程序）581°比較排序算法與圖中的判定樹是一致的；2°任一比較排序算法（對(duì)某一確定n值）都與一棵判定樹相對(duì)應(yīng)；3°判定樹的全部外部結(jié)點(diǎn)對(duì)應(yīng)于所有不同的排序結(jié)果。例如，n=3時(shí)，a，b，c的六種不同結(jié)果都應(yīng)包含在判定樹的外部結(jié)點(diǎn)中。從DT的根到一個(gè)葉結(jié)點(diǎn)的路長(zhǎng)，即某條路上的內(nèi)部結(jié)點(diǎn)數(shù)，也是算法運(yùn)行所需要的比較次數(shù)。判定樹DT的最長(zhǎng)路長(zhǎng)即為算法在最壞情形下的比較次數(shù)，平均路長(zhǎng)（從根到所有葉結(jié)點(diǎn)路長(zhǎng)的平均值）即為算法在平均情形下的比較次數(shù)。因此我們把對(duì)于算法在最壞情形下和期望的時(shí)間復(fù)雜度的計(jì)算變換為對(duì)于算法對(duì)應(yīng)的判定樹的最長(zhǎng)路長(zhǎng)和平均路長(zhǎng)的計(jì)算。592.5.2最壞情形引理2.5判定樹DT的葉結(jié)點(diǎn)數(shù)l與樹的深度d有如下關(guān)系： l≤2d。引理2.6有l(wèi)個(gè)葉結(jié)點(diǎn)的DT的深度為：引理2.7任意一棵n元判定樹DT至少有n!個(gè)葉結(jié)點(diǎn)。定理2.8任何n元比較排序算法在最壞情形下的比較次數(shù)為：2.5.3平均情形判定樹DT中，根到所有葉結(jié)點(diǎn)的路徑之和稱為DT的外部路長(zhǎng)epl（externalpathlength），而epl/l就是平均路長(zhǎng)，其中葉結(jié)點(diǎn)數(shù)l>n!。60引理2.9在所有具有l(wèi)個(gè)葉結(jié)點(diǎn)的判定樹中，若某棵樹的epl最小，則這個(gè)DT的所有葉結(jié)點(diǎn)是平衡的，即它的葉結(jié)點(diǎn)之多分布在樹的最下面兩層。如Fig.2.14。證明：

設(shè)判定樹有葉結(jié)點(diǎn)X位于k層，k<d–1。因DT有d層，故必有葉結(jié)點(diǎn)Z1，Z2在d層，其父結(jié)點(diǎn)Y在d–1層。

61對(duì)判定樹DT做一小的調(diào)整，把葉結(jié)點(diǎn)Z1，Z2從父結(jié)點(diǎn)Y上摘下，掛到結(jié)點(diǎn)X上（如Fig.2.15）。顯然它仍然是一個(gè)有l(wèi)個(gè)葉結(jié)點(diǎn)的判定樹DT’，但外部路長(zhǎng)epl發(fā)生了變化。具體地說有三條路長(zhǎng)發(fā)生了變化：在DT上，從根到X，Z1，Z2的三條路長(zhǎng)為k+2d。在DT’上，從根到Z1，Z2，Y的三條路長(zhǎng)為2(k+1)+d-1=2k+d+1。因k<d–1，所以2k+d+1<k+(d-1)+d+1=k+2d，得證。62引理2.10有l(wèi)個(gè)葉結(jié)點(diǎn)的判定樹DT的最小epl可表示為：1°l=2k，有上面引理可以斷定，最佳DT為完全滿二叉樹，即葉結(jié)點(diǎn)全在底層，顯然

epl=llogl，即為上式。2°若l≠2k，設(shè)DT深度為d，全部葉結(jié)點(diǎn)在d層和d–1層，如Fig.2.16所示。這時(shí)，因 ，因此有下面的定理：63定理2.11任何n元比較排序算法在平均情形下的比較次數(shù)至少為log(n!)，即A(n)≥log(n!)≈nlogn–1.443n證明：因任一n元比較排序算法的判定樹的葉結(jié)點(diǎn)數(shù)l≤n!，且所以642.6排序算法的有關(guān)研究

比較排序算法的改進(jìn)與分析基數(shù)排序（RadixSorting）

例如當(dāng)元素關(guān)鍵字有三位十進(jìn)制整數(shù)組成時(shí)，算法如Fig.2.17所示。外部排序算法粗排序（RoughlySorting）

并行排序（ParallelSorting）第二章完6566算法2.1選擇排序算法SelectSorttemplate<classKey>voidSelectSort(KeyL[],intn){

inti,j,k;

for(i=1;i<n;i++){

for(j=i+1,k=i;j<=n;j++)

if(L[k]>L[j])k=j;Swap(L[i],L[k]);}

return;}返回67算法2.2插入排序算法InsertSort

template<classKey>voidInsertSort(KeyL[],intn){

inti,j;Keytemp;

for(i=2;i<=n;i++){

for(j=i-1,temp=L[i];j>0;j--){

if(L[j]>temp)L[j+1]=L[j];

else{L[j+1]=temp;break;}}}

return;}返回68算法2.3起泡排序算法BubbleSorttemplate<classKey>voidBubbleSort(KeyL[],intn){

inti,j;

for(i=1;i<n;i++){

for(j=n;j>i;j--)

if(L[j]<L[j-1])Swap(L[j],L[j-1]);}

return;}返回69算法2.4起泡排序的改進(jìn)算法BSorttemplate<classKey>voidBSort(KeyL[],intn){

intp=1;inti,j;

for(i=1;(i<n)&&p;i++)for(j=n;j>i;j--){p=0;

if(L[j]<L[j-1]){p=1;Swap(L[j],L[j-1]);}}}

return;}返回70算法2.5希爾排序算法ShellSorttemplate<classKey>voidShellSort(KeyL[],intn,intt,inth[]){

for(inth=h[t],s=t;s>=1;s--,h=h[s])

for(intk=1;k<=h;k++)

for(inti=h+k;i<=n;i+=h){Keytemp=L[i];

intj=i–h;

while((L[j]>temp)&&(j>0)){L[j+h]=L[j];j-=h;}L[j+h]=temp;}

return;}返回71算法2.6快速排序算法QuickSorttemplate<classKey>voidQuickSort(KeyL[],intfirst,intlast){

if(first<last){

intsplit=Partition(L,first,last);QuickSort(L,first,split–1);QuickSort(L,split+1,last);}

return;}返回72算法2.7快速排序的劃分算法Partitiontemplate<classKey>intPartition(KeyL[],intfirst,intlast){

intleft=first;intright=last;Keypivot=L[first];

while(left<right){

while(L[right]>=pivot)right--;L[left++]=L[right];

while(L[left]<pivot)left++;L[right--]=L[left];}L[left]=pivot;

returnleft;}返回73算法2.8快速排序的改進(jìn)算法QStackSorttemplate<classKey>voidQStackSort(KeyL[],intn){

intf,l,i;stack.push(1,n);

while(!stack.empty){stack.pop(f,l);

while(f<l){i=Partition(L,f,l);Stack.push(i+1,l);l=i–1;}}

return;}返回74算法2.9有序序列的合并算法Mergetemplate<classKey>voidMerge(KeyS[],intl,intm,intr){KeyT[];

inti=l;intj=m+1;intk=l;

while((i<=m)&&(j<=r)){

if(S[i]<=S[j])T[k++]=S[i++];

elseT[k++]=S[j++];}

if(i>m)

for(intp=j;p<=r;p++)T[k++]=S[p];else

for(intp=i;p<=m;p++)T[k++]=S[p];

for(p=l;p<=r;p++)S[p]=T[p];

return;}返回75算法2.10合并排序算法MergeSorttemplate<classKey>voidMergeSort(KeyL[],intfirst,intlast){

if(first<last){

intmid=(first+last)/2;MergeSort(L,first,mid);MergeSort(L,mid+1,last);Merge(L,first,mid,last);}

return;}返回76算法2.11合并排序改進(jìn)算法IIMergeSort2template<classType>voidMergeSort2(TypeL[],intn){

while(n>1){

inti=1;intj,k;

do{

for(j=i;(j<n)&&(L[j]<L[j+1]);j++);

if(j==n)return;

for(k=j;(k<n)&&(L[k]<L[k+1]);k++);

if(k>j){Merge(L,i,j,k);i=k+1;}}

while(i<=n)}

return;}返回77算法2.12堆排序算法HeapSorttemplate<cla