1、1計(jì)算機(jī)算法計(jì)算機(jī)算法設(shè)計(jì)與分析導(dǎo)論設(shè)計(jì)與分析導(dǎo)論南開(kāi)大學(xué)南開(kāi)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系計(jì)算機(jī)科學(xué)與技術(shù)系劉璟2v 2.1 排序排序(sorting)問(wèn)題問(wèn)題 v 2.2 o(n2)階的排序算法階的排序算法 v 2.3 基于相鄰元比較的排序算法和希爾基于相鄰元比較的排序算法和希爾(shell)排序排序 v 2.4 o(nlogn)階的排序算法階的排序算法 v 2.5 比較排序算法的時(shí)間復(fù)雜度下界比較排序算法的時(shí)間復(fù)雜度下界 v 2.6 排序算法的有關(guān)研究排序算法的有關(guān)研究 32.1 排序（排序（sorting）問(wèn)題）問(wèn)題 有關(guān)排序的幾個(gè)基本概念：有關(guān)排序的幾個(gè)基本概念：1. 全序集：全序集：數(shù)據(jù)

2、集合數(shù)據(jù)集合d稱為關(guān)于關(guān)系稱為關(guān)于關(guān)系“”的全序集，如果的全序集，如果 滿足滿足 1 a b，a = b，b a 三者必居其一；三者必居其一； 2 a b，b c，則，則a c。全體整數(shù)集、實(shí)數(shù)集、字符串集等都是全序集。全體整數(shù)集、實(shí)數(shù)集、字符串集等都是全序集。 2. 排序（排序（sorting）問(wèn)題：）問(wèn)題：已知：已知：n項(xiàng)記錄項(xiàng)記錄r1，r2，rn，其一個(gè)域稱為關(guān)鍵字，其一個(gè)域稱為關(guān)鍵字（key），關(guān)鍵字值），關(guān)鍵字值k1，k2，kn屬于一全序集。屬于一全序集。要求：要求：重排重排n項(xiàng)記錄為項(xiàng)記錄為r(1) ，r(2)，r(n)，其中其中：(1)，(2)，(n)，為，為1, , n的一個(gè)排

3、列，使對(duì)應(yīng)的關(guān)鍵字滿足：的一個(gè)排列，使對(duì)應(yīng)的關(guān)鍵字滿足：k(1) k(2) k(n)。dcb,a, 43. 穩(wěn)定（穩(wěn)定（stable）排序算法：）排序算法：如果排序問(wèn)題滿足：若如果排序問(wèn)題滿足：若r(i) = r(j) 且且 i j 則則(i) (j )，則稱，則稱其為穩(wěn)定排序算法。其為穩(wěn)定排序算法。穩(wěn)定排序保證序列中關(guān)鍵字相同的記錄穩(wěn)定排序保證序列中關(guān)鍵字相同的記錄在排序過(guò)程中不會(huì)交換次序。在排序過(guò)程中不會(huì)交換次序。4. 內(nèi)部（內(nèi)部（internal）排序算法：）排序算法：數(shù)據(jù)在高速隨機(jī)存儲(chǔ)設(shè)備上（內(nèi)存）進(jìn)行排序操作，這時(shí)數(shù)數(shù)據(jù)在高速隨機(jī)存儲(chǔ)設(shè)備上（內(nèi)存）進(jìn)行排序操作，這時(shí)數(shù)據(jù)間的比較和移動(dòng)

4、指令的代價(jià)一般是相同的。據(jù)間的比較和移動(dòng)指令的代價(jià)一般是相同的。5. 外部（外部（external）排序算法：）排序算法：數(shù)據(jù)主要駐留在外部的低速存儲(chǔ)設(shè)備（硬盤(pán)、磁帶）上，數(shù)數(shù)據(jù)主要駐留在外部的低速存儲(chǔ)設(shè)備（硬盤(pán)、磁帶）上，數(shù)據(jù)在內(nèi)存與硬盤(pán)（磁帶）之間的傳送、移動(dòng)的代價(jià)明顯高于據(jù)在內(nèi)存與硬盤(pán)（磁帶）之間的傳送、移動(dòng)的代價(jià)明顯高于數(shù)據(jù)比較操作，因此，外部排序算法的設(shè)計(jì)不同于內(nèi)部排序。數(shù)據(jù)比較操作，因此，外部排序算法的設(shè)計(jì)不同于內(nèi)部排序。56. 原址排序算法：原址排序算法：在排序過(guò)程中除了全部輸入數(shù)據(jù)所占用的空間之外，只需有在排序過(guò)程中除了全部輸入數(shù)據(jù)所占用的空間之外，只需有限的額外空間。如果額外

5、空間的大小與記錄數(shù)限的額外空間。如果額外空間的大小與記錄數(shù)n無(wú)關(guān)，則稱為無(wú)關(guān)，則稱為原址排序。原址排序。7. 基于關(guān)鍵字比較的排序算法：基于關(guān)鍵字比較的排序算法：這類排序算法中僅對(duì)關(guān)鍵字進(jìn)行比較和移動(dòng)操作，因此關(guān)鍵這類排序算法中僅對(duì)關(guān)鍵字進(jìn)行比較和移動(dòng)操作，因此關(guān)鍵字的比較和移動(dòng)是算法的基本操作。字的比較和移動(dòng)是算法的基本操作。62.2 o(n2)階的排序算法階的排序算法 v2.2.1 選擇排序（選擇排序（selection sorting） 1. 選擇排序的思想：選擇排序的思想：把待排序的把待排序的l1. n視為兩個(gè)部分：視為兩個(gè)部分： l1.i- -1為已排序部分，為已排序部分，l i .

6、n 為未排序部分。排序步驟為：為未排序部分。排序步驟為： 1 i = 1；2 選擇：在選擇：在l i.n 中求最小元中求最小元lk，i k n；3 交換交換li與與lk，i+，if（ i lj的執(zhí)行次數(shù)。另外，函數(shù)的執(zhí)行次數(shù)。另外，函數(shù)swap( )需要需要3次次移動(dòng)，共移動(dòng)，共3( n 1 )次。因此，選擇排序算法的平均移動(dòng)次數(shù)會(huì)次。因此，選擇排序算法的平均移動(dòng)次數(shù)會(huì)比較小，而最好情形則為比較小，而最好情形則為3( n 1 )。當(dāng)數(shù)據(jù)記錄比較大時(shí)，移。當(dāng)數(shù)據(jù)記錄比較大時(shí)，移動(dòng)代價(jià)大于比較代價(jià)，選擇排序也可能有較好的性能。動(dòng)代價(jià)大于比較代價(jià)，選擇排序也可能有較好的性能。 )n(2)1n(n)n

7、(b2 9v2.2.2 插入排序（插入排序（insertion sorting） 1. 插入排序的思路：插入排序的思路： 與選擇排序不同，它是從無(wú)序部分不經(jīng)選擇，任取一元，然與選擇排序不同，它是從無(wú)序部分不經(jīng)選擇，任取一元，然后插入到有序部分的正確位置上。后插入到有序部分的正確位置上。其步驟為：其步驟為：l 1.n 分為兩部分：分為兩部分：l 1.i 為有序部分，為有序部分，l i+1.n 為未排序?yàn)槲磁判虿糠帧２糠帧?1 i = 1 ； 2 把把li+1插入到插入到l1.i中的正確位置，中的正確位置，i+； 3 if ( i n ) goto 2； 4 停止。停止。2. 算法的描述：算法的描

8、述： 算法算法 2.2 插入排序算法插入排序算法 insertsort 103. 算法的分析：算法的分析：最壞情形：最壞情形：最好情形：最好情形：平均情形：設(shè)輸入序列滿足兩個(gè)條件：平均情形：設(shè)輸入序列滿足兩個(gè)條件：1 n個(gè)關(guān)鍵字值是不同的，這可以簡(jiǎn)化分析；個(gè)關(guān)鍵字值是不同的，這可以簡(jiǎn)化分析；2 n個(gè)元素的所有不同的排列具有等可能性。個(gè)元素的所有不同的排列具有等可能性。在把在把li插入到有序的插入到有序的l1.i1的過(guò)程中，共有的過(guò)程中，共有i種可能的位置，種可能的位置，由假設(shè)由假設(shè)2可知落入每個(gè)位置的概率為可知落入每個(gè)位置的概率為1/i。而這。而這i種情形所需種情形所需要的比較次數(shù)分別為要的比

9、較次數(shù)分別為1，2， ，i-2，i-1，i-1，因此期望的比，因此期望的比較次數(shù)為：較次數(shù)為：)n(2)1n(n)1i ()n(w2n2i )n(1n)n(b 11因此，因此， 插入排序雖然也是插入排序雖然也是o(n2)階的算法，但在一般情形下，會(huì)比選階的算法，但在一般情形下，會(huì)比選擇排序塊。擇排序塊。算法的空間代價(jià)：基本上不需要額外空間，也是一種原址排算法的空間代價(jià)：基本上不需要額外空間，也是一種原址排序算法。序算法。它也是穩(wěn)定的。它也是穩(wěn)定的。i121ii112)1i ( ii1ji1)1i (i11i1j )n(4ni11n4)1n(n)i121i()n(a22n2in2i 124. 討

10、論：討論： 在基于相鄰元比較交換的排序算法中，在基于相鄰元比較交換的排序算法中，insertsort是最優(yōu)的。是最優(yōu)的。如果把數(shù)據(jù)的移動(dòng)作為基本操作，每一次數(shù)據(jù)比較都有一次如果把數(shù)據(jù)的移動(dòng)作為基本操作，每一次數(shù)據(jù)比較都有一次數(shù)據(jù)移動(dòng)與之對(duì)應(yīng)。因此，除了在外循環(huán)的數(shù)據(jù)移動(dòng)與之對(duì)應(yīng)。因此，除了在外循環(huán)的n 1次移動(dòng)之外，次移動(dòng)之外，數(shù)據(jù)比較與移動(dòng)次數(shù)是一致的，這與數(shù)據(jù)比較與移動(dòng)次數(shù)是一致的，這與selectsort算法是不同的。算法是不同的。v2.2.3 起泡排序（起泡排序（bubble sorting） 算法算法 2.3 起泡排序算法起泡排序算法 bubblesort 算法算法bubblesor

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

12、進(jìn)算法起泡排序的改進(jìn)算法 bsort 算法算法bsort的比較次數(shù)有所改進(jìn)：的比較次數(shù)有所改進(jìn)： )n(1n)n(b),n(4)1n(n)n(a),n(2)1n(n)n(w22 142.3 基于相鄰元比較的排序算法和基于相鄰元比較的排序算法和希爾（希爾（shellshell）排序）排序 v2.3.1 插入排序的最優(yōu)性插入排序的最優(yōu)性 定理定理2.1 基于相鄰元的比較及交換的排序算法基于相鄰元的比較及交換的排序算法 1在最壞情形下，至少需要在最壞情形下，至少需要n(n-1)/2次比較，即次比較，即w(n) = (n2)； 2在平均情形下，至少需要在平均情形下，至少需要n(n-1)/4次比較，即次

13、比較，即a(n) = (n2)。把把n個(gè)元素排列問(wèn)題歸結(jié)為以個(gè)元素排列問(wèn)題歸結(jié)為以n個(gè)關(guān)鍵字個(gè)關(guān)鍵字1, 2, ,n的任一排列的任一排列：(1), (2), ,(n)作為輸入，排序過(guò)程就是消滅序列中的逆序作為輸入，排序過(guò)程就是消滅序列中的逆序的過(guò)程。的過(guò)程。所謂所謂逆序逆序（inversion）（）（(i), (j) ），即），即i (j)。例。例如序列（如序列（2，4，1，5，3）有）有4個(gè)逆序：（個(gè)逆序：（2，1），（），（4，1），），（4，3），（），（5，3）；）；15證明的關(guān)鍵是，在序列中，如果兩個(gè)相鄰元為一逆序，經(jīng)過(guò)證明的關(guān)鍵是，在序列中，如果兩個(gè)相鄰元為一逆序，經(jīng)過(guò)交換肯定消除

14、了這個(gè)逆序，但這一交換只能消滅這一個(gè)逆序。交換肯定消除了這個(gè)逆序，但這一交換只能消滅這一個(gè)逆序。證明：證明：1存在一種排列：存在一種排列：n, n-1, ,2, 1 為全逆序，共包含為全逆序，共包含n(n-1)/2個(gè)逆序，故在最壞情形，任一依靠相鄰元比較、交換完成的個(gè)逆序，故在最壞情形，任一依靠相鄰元比較、交換完成的排序過(guò)程，至少需排序過(guò)程，至少需n(n-1)/2次比較，即次比較，即w(n) = (n2)。2對(duì)于平均情形，實(shí)際上需要計(jì)算對(duì)于平均情形，實(shí)際上需要計(jì)算1, 2, ,n的所有不同排列的所有不同排列的平均逆序數(shù)。的平均逆序數(shù)。當(dāng)當(dāng)n 1時(shí)，任一排列時(shí)，任一排列，必有一個(gè)唯一的、不同于它

15、的對(duì)偶排列；，必有一個(gè)唯一的、不同于它的對(duì)偶排列；是是的對(duì)偶排列，即的對(duì)偶排列，即是是的反序：的反序：(1)= (n)，(2)= (n-1), , (n)= (1)，例如，例如，(2,4,1,5,3)的對(duì)偶排列是的對(duì)偶排列是(3,5,1,4,2)； 1n之間的任一整數(shù)對(duì)（之間的任一整數(shù)對(duì)（i, j）（）（ij）如果是逆序，必然出現(xiàn)在任一排列）如果是逆序，必然出現(xiàn)在任一排列及其對(duì)偶排列及其對(duì)偶排列二者之一；二者之一；16 1n之間共有不同的整數(shù)對(duì)（之間共有不同的整數(shù)對(duì)（i, j） n(n-1)/2個(gè)；個(gè)； 1, ,n的所有排列是成對(duì)出現(xiàn)的，故每一排列平均有的所有排列是成對(duì)出現(xiàn)的，故每一排列平均有

16、n(n-1)/4個(gè)逆序，平個(gè)逆序，平均至少需均至少需n(n-1)/4次比較，即次比較，即a(n) = (n2)。 由定理知：由定理知：1算法算法insertsort和和bsort在上述條件下是最優(yōu)的；在上述條件下是最優(yōu)的；2為了設(shè)計(jì)比為了設(shè)計(jì)比(n2)階更快的排序算法，數(shù)據(jù)的比較和移動(dòng)階更快的排序算法，數(shù)據(jù)的比較和移動(dòng)必須在間隔較大的元素之間進(jìn)行。必須在間隔較大的元素之間進(jìn)行。v2.3.2 希爾（希爾（shell）排序）排序 該排序算法首先把輸入序列分成該排序算法首先把輸入序列分成h個(gè)間距為個(gè)間距為h的子序列，對(duì)每的子序列，對(duì)每個(gè)子序列進(jìn)行個(gè)子序列進(jìn)行hsorting。例如，取。例如，取h =

17、 6，則，則l1.n分為分為6個(gè)個(gè)子序列：子序列：17l1, l7, l13, l2, l8, l14, l3, l9, l15, l4, l10, l16, l5, l11, l17, l6, l12, l18, 進(jìn)行進(jìn)行hsorting后，就是逐步減少后，就是逐步減少h的大小，直至把的大小，直至把h減少到減少到1，完成排序工作。在最后一次完成排序工作。在最后一次h = 1時(shí)，采用時(shí)，采用insertsort或或bsort算法，可能出現(xiàn)最好情形或幾乎最好情形，而算法，可能出現(xiàn)最好情形或幾乎最好情形，而insertsort的的b(n)=n-1，故總比較次數(shù)有望縮小。，故總比較次數(shù)有望縮小。sh

18、ell排序算法有幾個(gè)因排序算法有幾個(gè)因素可以有大的變化：第一個(gè)素可以有大的變化：第一個(gè)h值如何取，值如何取，h值如何逐步減少到值如何逐步減少到1每次每次hsorting采用何種算法，都對(duì)整個(gè)算法性能有大的影響采用何種算法，都對(duì)整個(gè)算法性能有大的影響。18shell排序算法：排序算法：輸入：輸入：key l1.n：關(guān)鍵字?jǐn)?shù)組；：關(guān)鍵字?jǐn)?shù)組；int h1.t：遞增整數(shù)序列，：遞增整數(shù)序列，h1 = 1；算法算法 2.5 希爾排序算法希爾排序算法 shellsort 當(dāng)當(dāng)t = 1時(shí)，時(shí)，shellsort退化為退化為insertsort。增量序列。增量序列ht, ht-1, h1 = 1應(yīng)事先確定

19、，一個(gè)較好的選擇是：應(yīng)事先確定，一個(gè)較好的選擇是：h1 = 1, hs+1 = 3hs + 1其中其中1st 使使ht+1 1時(shí)，時(shí)，在在h-sort過(guò)程中，一次比較和交換可以至多消除過(guò)程中，一次比較和交換可以至多消除2ht -3個(gè)逆序。個(gè)逆序。關(guān)于關(guān)于shell排序的研究至今仍在繼續(xù)，因?yàn)閷?duì)于已知的排序的研究至今仍在繼續(xù)，因?yàn)閷?duì)于已知的n，怎樣，怎樣的增量的增量h序列使算法性能最佳，其最優(yōu)時(shí)間復(fù)雜度如何，目前序列使算法性能最佳，其最優(yōu)時(shí)間復(fù)雜度如何，目前尚不清楚。一些比較好的成果指出，適當(dāng)選取增量序列，尚不清楚。一些比較好的成果指出，適當(dāng)選取增量序列，shell排序算法的復(fù)雜度可以達(dá)到排序算

20、法的復(fù)雜度可以達(dá)到o(nlog2n)和和o(n1.25)。 192.4 o(nlogn)階的排序算法階的排序算法 v2.4.1 快速排序算法快速排序算法quicksort 1. 算法的思路：算法的思路： 其關(guān)鍵操作是其關(guān)鍵操作是劃分劃分（partition）：）：取取n元中的任一元（例如首元）作為劃分元（元中的任一元（例如首元）作為劃分元（pivot），令其余），令其余n 1個(gè)元與劃分元經(jīng)過(guò)比較，把較小者移至劃分元左邊，而個(gè)元與劃分元經(jīng)過(guò)比較，把較小者移至劃分元左邊，而較大者置于劃分元之右，形成兩個(gè)序列。左序列的所有元都較大者置于劃分元之右，形成兩個(gè)序列。左序列的所有元都小于劃分元，右序列都不

21、小于劃分元，然后用同樣的方法對(duì)小于劃分元，右序列都不小于劃分元，然后用同樣的方法對(duì)左、右序列排序，從而完成排序目標(biāo)。如左、右序列排序，從而完成排序目標(biāo)。如fig.2.1 所示。所示。劃分過(guò)程中，劃分元被放置到了排序過(guò)程的最終位置，其左、劃分過(guò)程中，劃分元被放置到了排序過(guò)程的最終位置，其左、右兩個(gè)序列雖然是無(wú)序的，但作為整體卻被確定了位置，因右兩個(gè)序列雖然是無(wú)序的，但作為整體卻被確定了位置，因此在完成左、右子序列的排序之后，整個(gè)排序過(guò)程也就完成。此在完成左、右子序列的排序之后，整個(gè)排序過(guò)程也就完成。20212. 算法算法quicksort： 輸入：輸入：未排序的未排序的l1.n，為了方便寫(xiě)遞歸程

22、序可表示為，為了方便寫(xiě)遞歸程序可表示為lfirst.last。輸出：輸出：已排序的已排序的lfirst.last。算法算法 2.6 快速排序算法快速排序算法 quicksort3. 劃分算法劃分算法partition： quicksort的核心是的核心是partition。劃分過(guò)程中，元素在數(shù)組中有。劃分過(guò)程中，元素在數(shù)組中有較大幅度的移動(dòng)，因此，這也是快速排序速度較快的內(nèi)在原較大幅度的移動(dòng)，因此，這也是快速排序速度較快的內(nèi)在原因。因。有各種不同的劃分算法，其性能也不盡相同。一種較好的劃有各種不同的劃分算法，其性能也不盡相同。一種較好的劃分算法，其思想如分算法，其思想如fig.2.2所示。所示

23、。 2223程序開(kāi)始，指針程序開(kāi)始，指針left = first，指向空位，即劃分元，指向空位，即劃分元pivot的位置，的位置，指針指針right = last，指向最右元，序列，指向最右元，序列l(wèi)2.n全為未做劃分處理全為未做劃分處理部分；首先自部分；首先自right開(kāi)始，向左掃描，找到第一個(gè)小于開(kāi)始，向左掃描，找到第一個(gè)小于pivot的的元素，把它送往元素，把它送往left指向的左空位，指向的左空位，left右移一位；然后從右移一位；然后從left向右掃描，找到第一個(gè)不小于向右掃描，找到第一個(gè)不小于pivot的元素，把它送到的元素，把它送到right指指向的位置（右空位），向的位置（右空

24、位），right左移一位，完成劃分的一次循環(huán)。左移一位，完成劃分的一次循環(huán)。重復(fù)上述循環(huán)，直到重復(fù)上述循環(huán)，直到left = right，令，令lleft = pivot，返回，返回left。算法算法2.7 快速排序的劃分算法快速排序的劃分算法 partition24劃分過(guò)程中的實(shí)例：劃分過(guò)程中的實(shí)例： 254. quicksort的復(fù)雜度分析：的復(fù)雜度分析： 最壞情形最壞情形的總比較次數(shù)為：的總比較次數(shù)為：平均時(shí)間性能分析平均時(shí)間性能分析：首先假設(shè)：首先假設(shè)：1n個(gè)元素的關(guān)鍵字值互不相等。個(gè)元素的關(guān)鍵字值互不相等。2n個(gè)元素的關(guān)鍵字的所有不同排列，以等可能即相等的概率出現(xiàn)在輸入個(gè)元素的關(guān)鍵字

25、的所有不同排列，以等可能即相等的概率出現(xiàn)在輸入序列中，因此，劃分元的最終位置序列中，因此，劃分元的最終位置i也以相等概率分別取值為也以相等概率分別取值為1, ,n。quicksort的平均比較次數(shù)的平均比較次數(shù)a(n)應(yīng)滿足遞歸方程：應(yīng)滿足遞歸方程： )n(2)1n(n)1k()n(w2n2k n1i1n),in(a)1i (a(n11n1n, 0)n(a26可簡(jiǎn)化為：可簡(jiǎn)化為： （公式（公式2.4.1） 在最好情形時(shí)劃分元總是處于序列的中間，遞歸方程可大致在最好情形時(shí)劃分元總是處于序列的中間，遞歸方程可大致簡(jiǎn)化成：簡(jiǎn)化成： 1n1i) i (an21n)n(a)nlogn(nnlogn)2n

26、421(nlogn)8n(b8)4n()2n()1n()4n(b4)12n(2)1n()n(b)0)1(b()2n(b21n)n(b 27定理定理2.2 在輸入序列的所有排列具有等可能性的條件下，算法在輸入序列的所有排列具有等可能性的條件下，算法quicksort的平均數(shù)據(jù)比較次數(shù)為的平均數(shù)據(jù)比較次數(shù)為: 其中其中c 0為一常數(shù)。為一常數(shù)。證明方法證明方法1：采用歸納法采用歸納法 當(dāng)當(dāng)n = 1時(shí)，時(shí)， a(n) = 0，cn lnn = 0，命題成立；，命題成立；假設(shè)當(dāng)假設(shè)當(dāng)1 k n， a(k) ck lnk 成立；成立； 由公式由公式2.4.1和假設(shè)得：和假設(shè)得： 根據(jù)積分的性質(zhì)：根據(jù)積

27、分的性質(zhì)：)nlogn(onlncn)n(a 1n1k1n1iklnckn21n) i (an21n)n(a)414nnlnn21( c1n)4x2xlnx( cxdxlnxcklnck2222n11n1k 28于是，當(dāng)于是，當(dāng)n1取取c = 2時(shí)，時(shí)， a(n) 2n lnn 成立。成立。推論推論2.3 在輸入序列的不同排序均勻分布的假設(shè)條件下，算法在輸入序列的不同排序均勻分布的假設(shè)條件下，算法quicksort的平均數(shù)據(jù)比較次數(shù)為的平均數(shù)據(jù)比較次數(shù)為: 證明方法證明方法2：為了簡(jiǎn)化關(guān)于為了簡(jiǎn)化關(guān)于a(n)的遞歸方程，的遞歸方程，由由 n2c1n)2c1 (nlncn)414nnlnn21(

28、nc21n)n(a22 nlogn386.1nlnn2)n(a ) 1n(a)2(a) 1 (a(n21n) i (an21n)n(a1n1i 29推出：推出：為了消除過(guò)多的為了消除過(guò)多的a(i)項(xiàng)，計(jì)算項(xiàng)，計(jì)算na(n)-(n-1)a(n-1) ：即即令令 則有：則有：) 2n(a) 2(a) 1 (a(1n22n) i (a1n22n) 1n(a2n1i ) 1n( 2) 1n(a2) i (a2)2n)(1n() i (a2) 1n(n) 1n(a) 1n()n(na2n1i1n2i )1n(n)1n(2n)1n(a1n)n(a 0)1(c,1n)n(a)n(c 30這是一個(gè)較為簡(jiǎn)單的遞

29、歸方程，不難得到：這是一個(gè)較為簡(jiǎn)單的遞歸方程，不難得到：由由harmonic級(jí)數(shù)，級(jí)數(shù)， 為為euler常數(shù)，常數(shù)， ，得：得： 1n,)1n(n)1n(2)1n(c1n,0)n(c n1in1in1i)1i ( i14i12)1i ( i1i2)n(c577. 0nlni1n1i n1i1n2in1i1nni1i1)1i ( i131 由此可以得到由此可以得到a(n)的更準(zhǔn)確的表達(dá)式：的更準(zhǔn)確的表達(dá)式：5. 空間復(fù)雜度分析：空間復(fù)雜度分析： 單從劃分算法來(lái)看，單從劃分算法來(lái)看，quicksort除有限的工作單元外，不占用除有限的工作單元外，不占用額外的空間，但在遞歸過(guò)程中，待排序段的首元和尾

30、元下標(biāo)額外的空間，但在遞歸過(guò)程中，待排序段的首元和尾元下標(biāo)需要保存，在最壞情形可能遞歸需要保存，在最壞情形可能遞歸n 1次。因此，次。因此，quicksort在在最壞情形下需要的空間代價(jià)為最壞情形下需要的空間代價(jià)為s(n)=(n)。 1nn4)577.0nln(2)n(c n846.2nlog)1n(386.1154.1n846.2nlog)1n(386.1)n(a 326. 關(guān)于關(guān)于quicksort算法的幾點(diǎn)討論：算法的幾點(diǎn)討論： 1）在最重要的性能，即平均時(shí)間代價(jià)上優(yōu)于其它算法。在最重要的性能，即平均時(shí)間代價(jià)上優(yōu)于其它算法。當(dāng)當(dāng)n比較大時(shí)，一般運(yùn)行確實(shí)很快，因此被廣泛采用。比較大時(shí)，一般

31、運(yùn)行確實(shí)很快，因此被廣泛采用。2）改善劃分元的選取，可能產(chǎn)生更好的效果。常見(jiàn)的幾種劃改善劃分元的選取，可能產(chǎn)生更好的效果。常見(jiàn)的幾種劃分元的選取方法是：分元的選取方法是： 在在first, ,last中取隨機(jī)數(shù)中取隨機(jī)數(shù)i，以，以li 代替代替l1； 在在first, ,last中，取中間值中，取中間值i = int (first+last)/2)； 取取first，last，int（first+last）/2）三者的中值為劃分元下標(biāo)。）三者的中值為劃分元下標(biāo)。3）算法的核心是劃分。不同的劃分策略會(huì)影響到移動(dòng)次數(shù)。算法的核心是劃分。不同的劃分策略會(huì)影響到移動(dòng)次數(shù)。 4）quicksort采用遞

32、歸算法的形式，簡(jiǎn)明但運(yùn)行時(shí)在時(shí)間和采用遞歸算法的形式，簡(jiǎn)明但運(yùn)行時(shí)在時(shí)間和空間上開(kāi)銷較大。一種改進(jìn)方法是使用由用戶設(shè)計(jì)的棧取代空間上開(kāi)銷較大。一種改進(jìn)方法是使用由用戶設(shè)計(jì)的棧取代遞歸。遞歸。 算法算法2.8 快速排序的改進(jìn)算法快速排序的改進(jìn)算法 qstacksort 335）空間復(fù)雜度的改進(jìn)：空間復(fù)雜度的改進(jìn)：快速排序算法的額外空間需求與遞歸和棧有關(guān)。當(dāng)把兩次遞快速排序算法的額外空間需求與遞歸和棧有關(guān)。當(dāng)把兩次遞歸調(diào)用改為單側(cè)進(jìn)棧，可以改進(jìn)空間復(fù)雜度。當(dāng)輸入為升序歸調(diào)用改為單側(cè)進(jìn)棧，可以改進(jìn)空間復(fù)雜度。當(dāng)輸入為升序（已排序）時(shí)，共需（已排序）時(shí)，共需n 1次進(jìn)棧，占用次進(jìn)棧，占用o(n)空間。

33、如果在程空間。如果在程序中，每進(jìn)行一次劃分以后，就對(duì)序中，每進(jìn)行一次劃分以后，就對(duì) f, i-1 , i+1,l 兩段進(jìn)行比兩段進(jìn)行比較，把較大的一半進(jìn)棧，先計(jì)算（劃分）較小的一半，其內(nèi)較，把較大的一半進(jìn)棧，先計(jì)算（劃分）較小的一半，其內(nèi)層循環(huán)次數(shù)（即棧的長(zhǎng)度）必然小于層循環(huán)次數(shù)（即棧的長(zhǎng)度）必然小于logn，因此空間代價(jià)可，因此空間代價(jià)可降為降為o(logn)。 6）快速排序算法對(duì)于較小的快速排序算法對(duì)于較小的n，其性能不及插入算法。因此，其性能不及插入算法。因此，可以設(shè)計(jì)一種綜合算法，當(dāng)輸入序列長(zhǎng)度小于某個(gè)固定值可以設(shè)計(jì)一種綜合算法，當(dāng)輸入序列長(zhǎng)度小于某個(gè)固定值（例如（例如 n0=50）時(shí)

34、，改用）時(shí)，改用insertsort進(jìn)行排序。進(jìn)行排序。7）快速排序的最壞情形時(shí)間復(fù)雜度和額外空間代價(jià)，無(wú)論如快速排序的最壞情形時(shí)間復(fù)雜度和額外空間代價(jià)，無(wú)論如何改進(jìn)，總是它的缺點(diǎn)和不足。何改進(jìn)，總是它的缺點(diǎn)和不足。34v2.4.2 合并排序算法合并排序算法mergesort 1. 算法的思路算法的思路 ： 把序列分為兩部分，分別遞歸（排序）后，再把兩個(gè)有序序把序列分為兩部分，分別遞歸（排序）后，再把兩個(gè)有序序列合并為一個(gè)有序序列。如列合并為一個(gè)有序序列。如fig.2.4。 352. 有序序列的合并算法：有序序列的合并算法： 算法算法2.9 有序序列的合并算法有序序列的合并算法 merge 3

35、. 合并排序算法合并排序算法mergesort： 算法算法2.10 合并排序算法合并排序算法 mergesort 4. 算法的復(fù)雜度分析：算法的復(fù)雜度分析： 該算法對(duì)兩個(gè)長(zhǎng)度為該算法對(duì)兩個(gè)長(zhǎng)度為m的有序序列的合并，在最壞情形下至的有序序列的合并，在最壞情形下至少需要少需要2m 1次比較。次比較。算法在最壞情形下的比較次數(shù)可用遞歸方程表示：算法在最壞情形下的比較次數(shù)可用遞歸方程表示： （公式（公式 2.4.2） 1n)2n(w)2n(w)n(w0)1(w 36忽略忽略n為奇數(shù)的情形，由主項(xiàng)定理可得為奇數(shù)的情形，由主項(xiàng)定理可得 。 假定假定n = 2k（k為正整數(shù)），則公式為正整數(shù)），則公式2.4

36、.2可以簡(jiǎn)化為：可以簡(jiǎn)化為： 直接推導(dǎo)得：直接推導(dǎo)得： 該算法平均情形比較次數(shù)該算法平均情形比較次數(shù)a(n) =(nlogn)。其空間代價(jià)較大，需要大小為其空間代價(jià)較大，需要大小為o(n)的額外空間。的額外空間。該算法是不穩(wěn)定的。該算法是不穩(wěn)定的。)nlogn()n(w 1n,1n)2n(w2)n(w0)1(w1nnlogn)2421(kn)1(w21n)12n)4n(w2(21n)2n(w2)n(w1kk 375. 關(guān)于合并排序算法的討論：關(guān)于合并排序算法的討論： 1）對(duì)于時(shí)間復(fù)雜度而言，在最壞情形下大大優(yōu)于快速排序，對(duì)于時(shí)間復(fù)雜度而言，在最壞情形下大大優(yōu)于快速排序，但在平均情況下不一定優(yōu)于

37、快速排序。數(shù)據(jù)的移動(dòng)次數(shù)也會(huì)但在平均情況下不一定優(yōu)于快速排序。數(shù)據(jù)的移動(dòng)次數(shù)也會(huì)對(duì)時(shí)間性能有所影響。對(duì)時(shí)間性能有所影響。 2）可以比較容易地改寫(xiě)成非遞歸程序。可以比較容易地改寫(xiě)成非遞歸程序。3）合并排序的一種改進(jìn)方法是充分利用輸入序列中可能的已合并排序的一種改進(jìn)方法是充分利用輸入序列中可能的已排序部分。排序部分。 算法算法2.11 合并排序改進(jìn)算法合并排序改進(jìn)算法ii mergesort2 例如，輸入序列為（例如，輸入序列為（4，12，8，6，0，11，27，5，20），實(shí)），實(shí)際上是際上是4個(gè)有序串：（個(gè)有序串：（4，12），（），（8），（），（6，11，27），），（5，20）。第一趟掃

38、描合并為：（）。第一趟掃描合并為：（4，8，12），（），（5，6，9，11，20，27），第二趟掃描就已排好序。），第二趟掃描就已排好序。 這個(gè)算法在在最好情形下的比較次數(shù)為這個(gè)算法在在最好情形下的比較次數(shù)為b(n) = n 1。384）主要缺點(diǎn)是空間代價(jià)較大，每次合并操作都需要與待合并主要缺點(diǎn)是空間代價(jià)較大，每次合并操作都需要與待合并的數(shù)據(jù)等長(zhǎng)的額外空間，其額外空間代價(jià)為的數(shù)據(jù)等長(zhǎng)的額外空間，其額外空間代價(jià)為o(n)階。階。 5）適合于并行計(jì)算。適合于并行計(jì)算。v2.4.3 堆排序算法堆排序算法heapsort 1. 堆排序算法的思路：堆排序算法的思路： 如如fig.2.5，算法把待排序的

39、，算法把待排序的數(shù)組數(shù)組l1.n視為一個(gè)二叉樹(shù)，視為一個(gè)二叉樹(shù)，數(shù)組元素依次按廣度第一的數(shù)組元素依次按廣度第一的順序與二叉樹(shù)的結(jié)點(diǎn)相對(duì)應(yīng)。順序與二叉樹(shù)的結(jié)點(diǎn)相對(duì)應(yīng)。結(jié)點(diǎn)間的鏈接利用下標(biāo)來(lái)計(jì)結(jié)點(diǎn)間的鏈接利用下標(biāo)來(lái)計(jì)算。對(duì)于結(jié)點(diǎn)算。對(duì)于結(jié)點(diǎn)i，如果，如果2i n，則則i為葉結(jié)點(diǎn)，否則，為葉結(jié)點(diǎn)，否則，2i為其為其左兒子下標(biāo)，左兒子下標(biāo)，2i+1為其右兒為其右兒子下標(biāo)。子下標(biāo)。 39這樣的二叉樹(shù)的所有的葉結(jié)點(diǎn)位于樹(shù)的最底層即這樣的二叉樹(shù)的所有的葉結(jié)點(diǎn)位于樹(shù)的最底層即d層或?qū)踊騞 1層，層，在最底層的葉結(jié)點(diǎn)位于左端。在最底層的葉結(jié)點(diǎn)位于左端。算法由兩部分組成，第一部分稱為算法由兩部分組成，第一部分稱為

40、建堆建堆（buildingheap），），就是通過(guò)數(shù)據(jù)的比較和移動(dòng)，使得二叉樹(shù)上每個(gè)內(nèi)部節(jié)點(diǎn)的就是通過(guò)數(shù)據(jù)的比較和移動(dòng)，使得二叉樹(shù)上每個(gè)內(nèi)部節(jié)點(diǎn)的值大于其左、右子結(jié)點(diǎn)的值。這樣的二叉樹(shù)稱為堆（值大于其左、右子結(jié)點(diǎn)的值。這樣的二叉樹(shù)稱為堆（heap），），如如fig.2.6所示。所示。 40第二部分稱為第二部分稱為根刪除根刪除堆修復(fù)堆修復(fù)（delete fix）過(guò)程，如）過(guò)程，如fig.2.7，可以描述為：，可以描述為： for ( i = n ; i = 2 ; i- ) swap( l1 , li ) ; fixheap( l1.i-1 );堆的修復(fù)過(guò)程，就是每次把兩個(gè)兒子中的較大者上升，直

41、到堆的修復(fù)過(guò)程，就是每次把兩個(gè)兒子中的較大者上升，直到元素元素li降到適當(dāng)?shù)奈恢脼橹埂＿@一降到適當(dāng)?shù)奈恢脼橹埂＿@一delete fix過(guò)程至多重復(fù)過(guò)程至多重復(fù)n次，每次修復(fù)所需的比較次數(shù)不會(huì)大于樹(shù)高，而平衡二叉樹(shù)次，每次修復(fù)所需的比較次數(shù)不會(huì)大于樹(shù)高，而平衡二叉樹(shù)的高不會(huì)大于的高不會(huì)大于logn（n為結(jié)點(diǎn)數(shù)），故此算法應(yīng)有較好的性能。為結(jié)點(diǎn)數(shù)），故此算法應(yīng)有較好的性能。 2. 算法的描述：算法的描述： 算法算法2.12 堆排序算法堆排序算法 heapsort 41423. 算法的分析算法的分析 ： 令令n = 2d 1 且且 n/2 n n ，并把建堆過(guò)程寫(xiě)成遞歸形式，并把建堆過(guò)程寫(xiě)成遞歸形式

42、 ：void bheap( h ) bheap( hleft ) ; bheap( hright) ; fixheap( l , n , root , lroot ) ; return ;它與函數(shù)它與函數(shù)buildheap是等價(jià)的。是等價(jià)的。由于由于fixheap( l, n, root, lroot )的比較次數(shù)為的比較次數(shù)為2logn，故有：，故有： nlog2)2n(w2)n(w)nlog2)1n(21(w2)n(w 43根據(jù)主項(xiàng)定理：因?yàn)楦鶕?jù)主項(xiàng)定理：因?yàn)閎 = 2，c = 2，取，取= 0.1，有，有 故故 因此，建堆過(guò)程在最壞情形下的時(shí)間復(fù)雜度為線性階。因此，建堆過(guò)程在最壞情形下的

43、時(shí)間復(fù)雜度為線性階。對(duì)于算法的第二部分，因?yàn)閷?duì)于有對(duì)于算法的第二部分，因?yàn)閷?duì)于有k個(gè)結(jié)點(diǎn)的堆進(jìn)行修復(fù)，至個(gè)結(jié)點(diǎn)的堆進(jìn)行修復(fù)，至多需要多需要 次比較，即全部比較次數(shù)至多為：次比較，即全部比較次數(shù)至多為： )n(onloga) n(w)2(log2 )n()n(w) n(w)n(w)2n(w) n() n(w klog2 )n443. 1nlogn(2)nnlnn)(e(log2xdxlnelog2klog2n11n1k 44定理定理2.4 heapsort在最壞情形下的數(shù)據(jù)比較次數(shù)為在最壞情形下的數(shù)據(jù)比較次數(shù)為w(n) = 2nlogn + o(n)，即，即heapsort是一個(gè)是一個(gè)(nlog

44、n)階的排序算法。階的排序算法。heapsort在平均情形下的比較次數(shù)是在平均情形下的比較次數(shù)是o(nlogn)。它是一個(gè)原。它是一個(gè)原址排序算法。址排序算法。 4. 堆排序算法的缺點(diǎn)：堆排序算法的缺點(diǎn)： 1）當(dāng)輸入序列為有序或幾乎有序時(shí)，堆排序算法根本沒(méi)有利當(dāng)輸入序列為有序或幾乎有序時(shí)，堆排序算法根本沒(méi)有利用序列有序的條件，需要用序列有序的條件，需要(nlogn)次比較，與最壞情形相比次比較，與最壞情形相比幾乎沒(méi)有改進(jìn)。幾乎沒(méi)有改進(jìn)。2）堆排序大約需要堆排序大約需要2 * nlogn次比較，在大多數(shù)情況下，比快次比較，在大多數(shù)情況下，比快速排序和合并排序要慢。速排序和合并排序要慢。 5. 加

45、速堆排序算法加速堆排序算法aheapsort： 在原來(lái)的在原來(lái)的fixheap算法中，每一次需要做兩次比較，即：算法中，每一次需要做兩次比較，即：if( lvac*2 lvac*2+1 )和和if( k llarger )。改進(jìn)后的。改進(jìn)后的afixheap算法，每一步只做一次比較。算法，每一步只做一次比較。45算法算法2.13 改進(jìn)的堆恢復(fù)過(guò)程改進(jìn)的堆恢復(fù)過(guò)程 afixheap 在大多數(shù)情況下，第一個(gè)循環(huán)把空位移至葉結(jié)點(diǎn)，共用在大多數(shù)情況下，第一個(gè)循環(huán)把空位移至葉結(jié)點(diǎn)，共用logn次比較，而向上的移動(dòng)次數(shù)則很少。結(jié)點(diǎn)的比較次數(shù)在最壞次比較，而向上的移動(dòng)次數(shù)則很少。結(jié)點(diǎn)的比較次數(shù)在最壞情形下仍

46、為情形下仍為2logn，但在大多數(shù)情況下則接近（大于），但在大多數(shù)情況下則接近（大于）logn。如如fig.2.9所示。所示。 46為了把最壞情形下的比較次數(shù)由為了把最壞情形下的比較次數(shù)由2nlogn縮小到縮小到nlogn，進(jìn)一步，進(jìn)一步改進(jìn)的思路描述如下：改進(jìn)的思路描述如下：設(shè)堆的高度為設(shè)堆的高度為 ，空位的移動(dòng)分為下移和上移，每下移、上移一層需要一次比空位的移動(dòng)分為下移和上移，每下移、上移一層需要一次比較。開(kāi)始時(shí)空位在頂點(diǎn)，設(shè)待插入元素的最終應(yīng)插入的位置較。開(kāi)始時(shí)空位在頂點(diǎn)，設(shè)待插入元素的最終應(yīng)插入的位置在在h層，層，0hh。1m = h/2；2空位下移空位下移m層，共用層，共用m次比較；

47、次比較；3if( lvac/2 n!。 llogd n443. 1nlogn!nlog)n(w 60引理引理2.9 在所有具有在所有具有l(wèi)個(gè)葉結(jié)點(diǎn)的判定樹(shù)中，若某棵樹(shù)的個(gè)葉結(jié)點(diǎn)的判定樹(shù)中，若某棵樹(shù)的epl最最小，則這個(gè)小，則這個(gè)dt的所有葉結(jié)點(diǎn)是平衡的，即它的葉結(jié)點(diǎn)之多分的所有葉結(jié)點(diǎn)是平衡的，即它的葉結(jié)點(diǎn)之多分布在樹(shù)的最下面兩層。如布在樹(shù)的最下面兩層。如fig.2.14。證明：證明： 設(shè)判定樹(shù)有葉結(jié)點(diǎn)設(shè)判定樹(shù)有葉結(jié)點(diǎn)x位于位于k層，層，k d 1。因。因dt有有d層，故必層，故必有葉結(jié)點(diǎn)有葉結(jié)點(diǎn)z1，z2在在d層，其父結(jié)點(diǎn)層，其父結(jié)點(diǎn)y在在d 1層。層。 61對(duì)判定樹(shù)對(duì)判定樹(shù)dt做一小的調(diào)整，

48、把葉結(jié)點(diǎn)做一小的調(diào)整，把葉結(jié)點(diǎn)z1，z2從父結(jié)點(diǎn)從父結(jié)點(diǎn)y上摘上摘下，掛到結(jié)點(diǎn)下，掛到結(jié)點(diǎn)x上（如上（如fig.2.15）。顯然它仍然是一個(gè)有）。顯然它仍然是一個(gè)有l(wèi)個(gè)葉個(gè)葉結(jié)點(diǎn)的判定樹(shù)結(jié)點(diǎn)的判定樹(shù)dt，但外部路長(zhǎng)，但外部路長(zhǎng)epl發(fā)生了變化。具體地說(shuō)有發(fā)生了變化。具體地說(shuō)有三條路長(zhǎng)發(fā)生了變化：三條路長(zhǎng)發(fā)生了變化：在在dt上，從根到上，從根到x，z1，z2的三條路長(zhǎng)為的三條路長(zhǎng)為k + 2d。在在dt上，從根到上，從根到z1，z2，y的三條路長(zhǎng)為的三條路長(zhǎng)為2(k+1)+d-1=2k+d+1。因。因k d 1，所以，所以2k+d+1 k+(d-1)+d+1 = k+2d，得證。得證。62引理引

49、理2.10 有有l(wèi)個(gè)葉結(jié)點(diǎn)的判定樹(shù)個(gè)葉結(jié)點(diǎn)的判定樹(shù)dt的最小的最小epl可表示為：可表示為： 1l = 2k，有上面引理可以斷定，最佳，有上面引理可以斷定，最佳dt為完全滿二叉樹(shù)，為完全滿二叉樹(shù)，即葉結(jié)點(diǎn)全在底層，顯然即葉結(jié)點(diǎn)全在底層，顯然 epl = llogl，即為上式。，即為上式。2若若l 2k，設(shè)，設(shè)dt深度為深度為d，全部葉結(jié)點(diǎn)在，全部葉結(jié)點(diǎn)在d層和層和d 1層，如層，如fig.2.16所示。這時(shí)，因所示。這時(shí)，因 ，因此有下面的定理：因此有下面的定理： )2l ( 2lloglllog llog1d )2l (2llogl)2l (2)1d( ld)1d( leplllog1d 層

50、層上上葉葉結(jié)結(jié)點(diǎn)點(diǎn)數(shù)數(shù)63定理定理2.11 任何任何n元比較排序算法在平均情形下的比較次數(shù)至少元比較排序算法在平均情形下的比較次數(shù)至少為為log(n!)，即，即a(n)log(n!)nlogn 1.443n證明：證明：因任一因任一n元比較排序算法的判定樹(shù)的葉結(jié)點(diǎn)數(shù)元比較排序算法的判定樹(shù)的葉結(jié)點(diǎn)數(shù)ln!，且，且所以所以 02lllog n443.1nlogn) !nlog(lloglepl)n(a 642.6 排序算法的有關(guān)研究排序算法的有關(guān)研究 比較排序算法的改進(jìn)與分析比較排序算法的改進(jìn)與分析 基數(shù)排序（基數(shù)排序（radix sorting） 例如當(dāng)元素關(guān)鍵字有三位十進(jìn)制整數(shù)組成時(shí)，算法如例如

51、當(dāng)元素關(guān)鍵字有三位十進(jìn)制整數(shù)組成時(shí)，算法如fig.2.17所示。所示。 外部排序算法外部排序算法 粗排序（粗排序（roughly sorting） 并行排序（并行排序（parallel sorting）第二章完第二章完6566算法算法 2.1 選擇排序算法選擇排序算法 selectsort template void selectsort ( key l , int n ) int i, j, k ; for ( i = 1 ; i n ; i + + ) for ( j = i + 1 , k = i ; j lj ) k = j ; swap ( li , lk ) ; return ;返

52、回返回67算法算法 2.2 插入排序算法插入排序算法 insertsort template void insertsort ( key l , int n ) int i , j ; key temp ; for ( i = 2 ; i 0 ; j - - ) if ( lj temp ) lj+1 = lj ; else lj+1 = temp ; break ; return ;返回返回68算法算法 2.3 起泡排序算法起泡排序算法 bubblesort template void bubblesort ( key l , int n ) int i , j ; for ( i = 1

53、; i i ; j - - ) if ( lj lj-1 ) swap( lj , lj-1 ) ; return ;返回返回69算法算法 2.4 起泡排序的改進(jìn)算法起泡排序的改進(jìn)算法 bsort template void bsort ( key l , int n ) int p = 1 ; int i , j ; for ( i = 1 ; ( i i ; j - - ) p = 0; if ( lj lj-1 ) p = 1 ; swap( lj , lj-1 ) ; return ;返回返回70算法算法 2.5 希爾排序算法希爾排序算法 shellsort template void

54、 shellsort ( key l , int n , int t , int h ) for ( int h = ht , s = t ; s = 1 ; s - - , h = hs ) for ( int k = 1 ; k = h ; k + + ) for ( int i = h + k ; i temp )&( j 0) ) lj+h = lj ; j - = h ; lj+h = temp ; return ;返回返回71算法算法 2.6 快速排序算法快速排序算法 quicksort template void quicksort ( key l , int first

55、 , int last ) if ( first last ) int split = partition ( l , first, last ) ; quicksort ( l , first , split 1 ) ; quicksort ( l , split + 1 , last ) ; return ;返回返回72算法算法 2.7 快速排序的劃分算法快速排序的劃分算法 partition template int partition ( key l , int first , int last ) int left = first ; int right = last ; key p

56、ivot = lfirst ; while ( left = pivot ) right - - ; lleft+ = lright ; while ( lleft pivot ) left + + ; lright- = lleft ; lleft = pivot ; return left ;返回返回73算法算法 2.8 快速排序的改進(jìn)算法快速排序的改進(jìn)算法 qstacksort template void qstacksort ( key l , int n ) int f , 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 有序序列的合并算法有序序列的合并算法 merge template void merge ( key s , int l, int m, int r ) key t ; int i = l ; int j