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

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

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

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

5、空間的大小與記錄數限的額外空間。如果額外空間的大小與記錄數n無關，則稱為無關，則稱為原址排序。原址排序。7. 基于關鍵字比較的排序算法：基于關鍵字比較的排序算法：這類排序算法中僅對關鍵字進行比較和移動操作，因此關鍵這類排序算法中僅對關鍵字進行比較和移動操作，因此關鍵字的比較和移動是算法的基本操作。字的比較和移動是算法的基本操作。62.2 o(n2)階的排序算法階的排序算法 v2.2.1 選擇排序（選擇排序（selection sorting） 1. 選擇排序的思想：選擇排序的思想：把待排序的把待排序的l1. n視為兩個部分：視為兩個部分： 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的執行次數。另外，函數的執行次數。另外，函數swap( )需要需要3次次移動，共移動，共3( n 1 )次。因此，選擇排序算法的平均移動次數會次。因此，選擇排序算法的平均移動次數會比較小，而最好情形則為比較小，而最好情形則為3( n 1 )。當數據記錄比較大時，移。當數據記錄比較大時，移動代價大于比較代價，選擇排序也可能有較好的性能。動代價大于比較代價，選擇排序也可能有較好的性能。 )n(2)1n(n)n

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

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

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

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

11、t的比較次數是確定的：的比較次數是確定的：移動次數與數據比較相對應，交換函數移動次數與數據比較相對應，交換函數swap需要三次數據移需要三次數據移動，在最壞情形下是比較次數的三倍，而在最好情形下不需動，在最壞情形下是比較次數的三倍，而在最好情形下不需要移動。要移動。)n(2)1n(n)n(b)n(a)n(w)n(t2 13bubblesort是穩定的、原址排序算法。是穩定的、原址排序算法。bubblesort的一種實用改進算法是在程序中設一標記位，當的一種實用改進算法是在程序中設一標記位，當一遍掃描中沒有交換發生，則排序停止。一遍掃描中沒有交換發生，則排序停止。 算法算法 2.4 起泡排序的改

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

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

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

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

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

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

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

19、，一個較好的選擇是：應事先確定，一個較好的選擇是：h1 = 1, hs+1 = 3hs + 1其中其中1st 使使ht+1 1時，時，在在h-sort過程中，一次比較和交換可以至多消除過程中，一次比較和交換可以至多消除2ht -3個逆序。個逆序。關于關于shell排序的研究至今仍在繼續，因為對于已知的排序的研究至今仍在繼續，因為對于已知的n，怎樣，怎樣的增量的增量h序列使算法性能最佳，其最優時間復雜度如何，目前序列使算法性能最佳，其最優時間復雜度如何，目前尚不清楚。一些比較好的成果指出，適當選取增量序列，尚不清楚。一些比較好的成果指出，適當選取增量序列，shell排序算法的復雜度可以達到排序算

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

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

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

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

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

25、的所有不同排列，以等可能即相等的概率出現在輸入序列中，因此，劃分元的最終位置序列中，因此，劃分元的最終位置i也以相等概率分別取值為也以相等概率分別取值為1, ,n。quicksort的平均比較次數的平均比較次數a(n)應滿足遞歸方程：應滿足遞歸方程： )n(2)1n(n)1k()n(w2n2k n1i1n),in(a)1i (a(n11n1n, 0)n(a26可簡化為：可簡化為： （公式（公式2.4.1） 在最好情形時劃分元總是處于序列的中間，遞歸方程可大致在最好情形時劃分元總是處于序列的中間，遞歸方程可大致簡化成：簡化成： 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的平均數據比較次數為的平均數據比較次數為: 其中其中c 0為一常數。為一常數。證明方法證明方法1：采用歸納法采用歸納法 當當n = 1時，時， a(n) = 0，cn lnn = 0，命題成立；，命題成立；假設當假設當1 k n， a(k) ck lnk 成立；成立； 由公式由公式2.4.1和假設得：和假設得： 根據積分的性質：根據積

27、分的性質：)nlogn(onlncn)n(a 1n1k1n1iklnckn21n) i (an21n)n(a)414nnlnn21( c1n)4x2xlnx( cxdxlnxcklnck2222n11n1k 28于是，當于是，當n1取取c = 2時，時， a(n) 2n lnn 成立。成立。推論推論2.3 在輸入序列的不同排序均勻分布的假設條件下，算法在輸入序列的不同排序均勻分布的假設條件下，算法quicksort的平均數據比較次數為的平均數據比較次數為: 證明方法證明方法2：為了簡化關于為了簡化關于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推出：推出：為了消除過多的為了消除過多的a(i)項，計算項，計算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這是一個較為簡單的遞

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

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

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

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

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

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

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

36、.2可以簡化為：可以簡化為： 直接推導得：直接推導得： 該算法平均情形比較次數該算法平均情形比較次數a(n) =(nlogn)。其空間代價較大，需要大小為其空間代價較大，需要大小為o(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. 關于合并排序算法的討論：關于合并排序算法的討論： 1）對于時間復雜度而言，在最壞情形下大大優于快速排序，對于時間復雜度而言，在最壞情形下大大優于快速排序，但在平均情況下不一定優于

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

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

39、，算法把待排序的數組數組l1.n視為一個二叉樹，視為一個二叉樹，數組元素依次按廣度第一的數組元素依次按廣度第一的順序與二叉樹的結點相對應。順序與二叉樹的結點相對應。結點間的鏈接利用下標來計結點間的鏈接利用下標來計算。對于結點算。對于結點i，如果，如果2i n，則則i為葉結點，否則，為葉結點，否則，2i為其為其左兒子下標，左兒子下標，2i+1為其右兒為其右兒子下標。子下標。 39這樣的二叉樹的所有的葉結點位于樹的最底層即這樣的二叉樹的所有的葉結點位于樹的最底層即d層或層或d 1層，層，在最底層的葉結點位于左端。在最底層的葉結點位于左端。算法由兩部分組成，第一部分稱為算法由兩部分組成，第一部分稱為

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

41、到堆的修復過程，就是每次把兩個兒子中的較大者上升，直到元素元素li降到適當的位置為止。這一降到適當的位置為止。這一delete fix過程至多重復過程至多重復n次，每次修復所需的比較次數不會大于樹高，而平衡二叉樹次，每次修復所需的比較次數不會大于樹高，而平衡二叉樹的高不會大于的高不會大于logn（n為結點數），故此算法應有較好的性能。為結點數），故此算法應有較好的性能。 2. 算法的描述：算法的描述： 算法算法2.12 堆排序算法堆排序算法 heapsort 41423. 算法的分析算法的分析 ： 令令n = 2d 1 且且 n/2 n n ，并把建堆過程寫成遞歸形式，并把建堆過程寫成遞歸形式

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

43、時間復雜度為線性階。對于算法的第二部分，因為對于有對于算法的第二部分，因為對于有k個結點的堆進行修復，至個結點的堆進行修復，至多需要多需要 次比較，即全部比較次數至多為：次比較，即全部比較次數至多為： )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在最壞情形下的數據比較次數為在最壞情形下的數據比較次數為w(n) = 2nlogn + o(n)，即，即heapsort是一個是一個(nlog

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

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

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

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

48、把葉結點做一小的調整，把葉結點z1，z2從父結點從父結點y上摘上摘下，掛到結點下，掛到結點x上（如上（如fig.2.15）。顯然它仍然是一個有）。顯然它仍然是一個有l個葉個葉結點的判定樹結點的判定樹dt，但外部路長，但外部路長epl發生了變化。具體地說有發生了變化。具體地說有三條路長發生了變化：三條路長發生了變化：在在dt上，從根到上，從根到x，z1，z2的三條路長為的三條路長為k + 2d。在在dt上，從根到上，從根到z1，z2，y的三條路長為的三條路長為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個葉結點的判定樹個葉結點的判定樹dt的最小的最小epl可表示為：可表示為： 1l = 2k，有上面引理可以斷定，最佳，有上面引理可以斷定，最佳dt為完全滿二叉樹，為完全滿二叉樹，即葉結點全在底層，顯然即葉結點全在底層，顯然 epl = llogl，即為上式。，即為上式。2若若l 2k，設，設dt深度為深度為d，全部葉結點在，全部葉結點在d層和層和d 1層，如層，如fig.2.16所示。這時，因所示。這時，因 ，因此有下面的定理：因此有下面的定理： )2l ( 2lloglllog llog1d )2l (2llogl)2l (2)1d( ld)1d( leplllog1d 層

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

51、當元素關鍵字有三位十進制整數組成時，算法如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 起泡排序的改進算法起泡排序的改進算法 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 快速排序的改進算法快速排序的改進算法 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