數(shù)據(jù)結(jié)構(gòu)第八章排序(2016)

1、第八章 排序12基本排序插入排序34交換排序選擇排序5歸并排序6分配排序8.1 基本排序排序：排序：給定一組給定一組記錄記錄的集合的集合r1, r2, , rn，其相應(yīng)，其相應(yīng)的關(guān)鍵字分別為的關(guān)鍵字分別為k1, k2, , kn，排序是將這些記錄，排序是將這些記錄排列成順序為排列成順序為rs1, rs2, , rsn的一個序列，使得相的一個序列，使得相應(yīng)的關(guān)鍵字滿足應(yīng)的關(guān)鍵字滿足ks1ks2ksn（稱為升序）或（稱為升序）或ks1ks2ksn（稱為降序）。（稱為降序）。正序：正序：待排序序列中的記錄已按關(guān)鍵字排好序。待排序序列中的記錄已按關(guān)鍵字排好序。逆序（反序）：逆序（反序）：待排序序列中記

2、錄的排列順序與排好待排序序列中記錄的排列順序與排好序的順序正好相反。序的順序正好相反。注注: 沒有特別說明沒有特別說明,均按遞增順序排序均按遞增順序排序.排序算法的排序算法的穩(wěn)定性：穩(wěn)定性：假定在待排序的記錄集中，存在假定在待排序的記錄集中，存在多個多個具有具有相同鍵值相同鍵值的記錄，若的記錄，若經(jīng)過排序經(jīng)過排序，這些記錄的，這些記錄的相對次序相對次序仍然仍然保持不變保持不變，即在原序列中，即在原序列中，ki=kj且且ki在在kj之前，而在排序后的序列中，之前，而在排序后的序列中，ki仍在仍在kj之前，則稱這種之前，則稱這種排序算法是排序算法是穩(wěn)定的穩(wěn)定的；否則否則稱為稱為不穩(wěn)定不穩(wěn)定的。的。

3、 排序的分類排序的分類1.1. 內(nèi)部排序：內(nèi)部排序：在排序的整個過程中，待在排序的整個過程中，待排序的所有排序的所有記錄記錄全部全部被放置在被放置在內(nèi)存內(nèi)存中。中。2. 2. 外部排序外部排序：由于待排序的記錄個數(shù)太多，不能同由于待排序的記錄個數(shù)太多，不能同時放置在內(nèi)存，而需要將時放置在內(nèi)存，而需要將一部分記錄一部分記錄放置放置在內(nèi)存在內(nèi)存，另另一部分記錄一部分記錄放置放置在外存上在外存上，整個排序過程需要在內(nèi)外，整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。重點重點8.1 基本排序1. 內(nèi)排序在排序過程中的內(nèi)排序在排序過程中的基本操作基本操

4、作：比較比較：關(guān)鍵字之間的比較；：關(guān)鍵字之間的比較；移動移動：記錄從一個位置移動到另一個位置。：記錄從一個位置移動到另一個位置。 2. 輔助存儲空間輔助存儲空間。3.算法本身的復(fù)雜程度算法本身的復(fù)雜程度。 排序算法的排序算法的性能性能文件存儲結(jié)構(gòu)文件存儲結(jié)構(gòu) typedef struct int key; datatype other; rectype; rectype Rn;8.2 插入排序插入排序有多種具體實現(xiàn)算法：插入排序有多種具體實現(xiàn)算法： 1) 1) 直接插入排序直接插入排序 2) 2) 希爾排序希爾排序簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。簡言之，邊插入邊排序，保證子

5、序列中隨時都是排好序的。8.2.1 直接插入排序新元素插入到哪里？新元素插入到哪里？思想思想: :假設(shè)待排記錄存于假設(shè)待排記錄存于RnRn( (R1-Rn-1R1-Rn-1共共n-1n-1個元素個元素),),若若排序的某一時刻排序的某一時刻R R被分為兩個子區(qū)被分為兩個子區(qū): : R1 R1Ri-1Ri-1和和RiRiRn-1Rn-1關(guān)鍵關(guān)鍵: :如何將如何將RiRi插入到當(dāng)前有序區(qū)的適當(dāng)位置插入到當(dāng)前有序區(qū)的適當(dāng)位置? ? 假設(shè)只有一個記錄的有序表是有序的假設(shè)只有一個記錄的有序表是有序的, ,在在已形成的已形成的有序表中進行比較有序表中進行比較，并在適當(dāng)位置插入，把原來位，并在適當(dāng)位置插入，

6、把原來位置上的元素向后置上的元素向后順移順移。分析分析: :與當(dāng)前有序區(qū)中最后一個記錄與當(dāng)前有序區(qū)中最后一個記錄RjRj進行比較進行比較: : 若若Ri.keyRj.key,Ri.key=Rj.key,Ri.key=Rj.key,則則j+1j+1為為RiRi插入位置插入位置. .8.2.1 直接插入排序例：例：關(guān)鍵字序列關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），）， 請寫出直接插入排序的中間過程序列。請寫出直接插入排序的中間過程序列。 【13】, 6, 3, 31, 9, 27, 5, 11第一趟第一趟【6, 13】, 3, 31, 9, 27, 5, 11第二趟第二趟【3,

7、6, 13】, 31, 9, 27, 5, 11第三趟第三趟【3, 6, 13 , 31】, 9, 27, 5, 11第四趟第四趟【3, 6, 9, 13 , 31】, 27, 5, 11第五趟第五趟【3, 6, 9, 13 , 27, 31】, 5, 11第六趟第六趟【3, 5, 6, 9, 13 , 27, 31】, 11第七趟第七趟【3, 5, 6, 9, 11, 13 , 27, 31】 void insertort ( rectype Rn) int i,j; for(i=2;in;i+) R0=Ri; /*監(jiān)視哨監(jiān)視哨*/ j=i-1; while(R0.keyRj.key) Rj

8、+1=Rj-; Rj+1=R0; 小結(jié)：直接插入排序是一種小結(jié)：直接插入排序是一種穩(wěn)穩(wěn)定定的排序算法。的排序算法。8.2.1 直接插入排序直接插入排序直接插入排序算法性能分析算法性能分析最好最好情況下（情況下（正序正序）：）： 時間復(fù)雜度為時間復(fù)雜度為O(n)。比較次數(shù)：比較次數(shù)：Cmin=n-1移動次數(shù)：移動次數(shù)：Mmin=2(n-1) 最壞最壞情況下（情況下（逆序或反序逆序或反序）：）： 2) 1)(2(2maxnniCni比較次數(shù)：比較次數(shù)：移動次數(shù)：移動次數(shù)：ninniM2max2) 1)(4() 21(時間復(fù)雜度為時間復(fù)雜度為O(n2)。 平均時間復(fù)雜度為平均時間復(fù)雜度為O(n2)空

9、間復(fù)雜度空間復(fù)雜度:O(1)8.2.2 希爾排序（又稱縮小增量排序）（又稱縮小增量排序）基本思想基本思想：先取先取一個一個正整數(shù)正整數(shù)d d1 1nn, ,把把全部記錄分成全部記錄分成d d1 1個個組組，所有，所有距離為距離為d d1 1倍數(shù)的記錄倍數(shù)的記錄放在一組放在一組，在各組內(nèi)在各組內(nèi)進行進行直接插入排序直接插入排序；然后；然后取取d d2 2dd1 1，重復(fù)上述，重復(fù)上述分組和排序分組和排序工工作，作，直至取直至取d d1 1=1=1，即所有記錄放在一組中排序為止。即所有記錄放在一組中排序為止。技巧技巧：希爾排序中增量：希爾排序中增量di有多種有多種取法取法，我們可選取如，我們可選取

10、如d1=n/2,di+1=di/2。優(yōu)點優(yōu)點：讓：讓關(guān)鍵字小關(guān)鍵字小的元素的元素很快前移很快前移，且序列若，且序列若基本有基本有序時序時，再用直接插入排序處理，再用直接插入排序處理，時間效率會高很多時間效率會高很多。8.2.2 希爾排序1 2 3 4 5 6 7 8 9初始序列初始序列d = 4d = 2d = 18.2.2 希爾排序算法分析：算法分析：每組都需要一個監(jiān)視哨每組都需要一個監(jiān)視哨,則共取最大值則共取最大值d1個個,存儲于存儲于R0-Rd1-1中中,只需讓其值小于所有關(guān)鍵字即可。只需讓其值小于所有關(guān)鍵字即可。算法描述：算法描述：rectype Rn+d1; /*Rd1-Rn+d1-

11、1存放存放n個待排記錄個待排記錄*/int dt; /*增量序列增量序列 d0=d1*/void SHELLSORT(rectype R,int d) int i,j,k,h; rectype temp; for(i=0;id0;i+) Ri.key=0; /*設(shè)監(jiān)視哨設(shè)監(jiān)視哨,小于所有小于所有key*/ 8.2.2 希爾排序 k=0; do h=dk; for(i=h+d1;in+d1;i+) temp=Ri; j=i-h; while(temp.keyRj.key) Rj+h=Rj; j=j-h; Rj+h=temp; k+; /*取下一增量取下一增量*/ while(h!=1)8.2.2

12、 希爾排序希爾排序算法的希爾排序算法的時間性能：時間性能：希爾排序希爾排序算法的時間性能是所取算法的時間性能是所取增量增量的函數(shù)，而的函數(shù)，而到目前為止尚未有人求得一種最好的增量序列。到目前為止尚未有人求得一種最好的增量序列。 研究表明，希爾排序的時間性能研究表明，希爾排序的時間性能在在O(n2)和和O(nlog2n)之間之間。當(dāng)。當(dāng)n在某個特定范圍內(nèi)，希爾排序所需的比較次在某個特定范圍內(nèi)，希爾排序所需的比較次數(shù)和記錄的移動次數(shù)數(shù)和記錄的移動次數(shù)約為約為O(n1.3 ) 。 分析：分析：開始時開始時dk 的值較大，子序列中的記錄較少，排序速度較的值較大，子序列中的記錄較少，排序速度較快；隨著排

13、序進展，快；隨著排序進展，dk 值逐漸變小，子序列中記錄個數(shù)值逐漸變小，子序列中記錄個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)記錄已基本有逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)記錄已基本有序，所以排序速度仍然很快。序，所以排序速度仍然很快。小結(jié)：希爾排序是一種小結(jié)：希爾排序是一種不穩(wěn)定不穩(wěn)定的排序算法。的排序算法。8.3 交換排序交換交換 兩兩比較兩兩比較待排序記錄的關(guān)鍵字，如果待排序記錄的關(guān)鍵字，如果發(fā)生逆序發(fā)生逆序（即排列順序與排序后的次序正好相反），則（即排列順序與排序后的次序正好相反），則交換之交換之，直到所有記錄都排好序為止。直到所有記錄都排好序為止。交換排序的主要算法有：交換排序的主要

14、算法有： 1) 起泡排序起泡排序 2) 快速排序快速排序8.3.1 起泡排序基本思路：基本思路：將待排記錄將待排記錄縱向排列縱向排列, ,自下而上兩兩比自下而上兩兩比較較相鄰記錄關(guān)鍵字相鄰記錄關(guān)鍵字k kj j與與k kj-1j-1的值的值, ,若若反序反序則二則二者者交換交換位置位置, ,繼續(xù)比較繼續(xù)比較k kj-1j-1與與k kj-2j-2, ,直到全部記直到全部記錄比較一遍，則一趟結(jié)束。錄比較一遍，則一趟結(jié)束。優(yōu)點：優(yōu)點：每趟結(jié)束時，不僅能使當(dāng)前最小關(guān)鍵字上升每趟結(jié)束時，不僅能使當(dāng)前最小關(guān)鍵字上升到其應(yīng)該所在位置，還能同時部分理順其他到其應(yīng)該所在位置，還能同時部分理順其他元素。元素。例

15、：例：關(guān)鍵字序列關(guān)鍵字序列 T=(49, 38, 65, 97, 76, 13, 27, 49*），請寫出冒），請寫出冒泡排序的具體實現(xiàn)過程。泡排序的具體實現(xiàn)過程。4938659776132749*初態(tài)初態(tài) 第第1趟趟 第第2趟趟 第第3趟趟 第第4趟趟 第第5趟趟1349386597762749*1327493865977649*1327384949*6597761327384949*6576971327384949*657697起泡排序需多少趟起泡排序需多少趟,每趟需比較次數(shù)每趟需比較次數(shù)?第第1趟趟:n-1次次第第2趟趟:n-2次次(至多至多)第第n-1趟趟:1次次一旦下趟沒有交換發(fā)一旦

16、下趟沒有交換發(fā)生，還可以提前結(jié)束生，還可以提前結(jié)束排序排序。如何確定何時結(jié)束排序？如何確定何時結(jié)束排序？ 設(shè)標志位設(shè)標志位noswap來表示每一趟是否有交換：來表示每一趟是否有交換： 即：每趟開始之前，設(shè)即：每趟開始之前，設(shè)noswap=1，若交換則改，若交換則改noswap=0；只需每趟結(jié)束后觀察只需每趟結(jié)束后觀察noswap的值即可。的值即可。8.3.1 起泡排序void BUBBLESORT( rectype R) /*R0-Rn-1共共n個記錄個記錄*/ int i,j,noswap; rectype temp; for(i=0;i=i;j-) if(Rj+1.keyRj.key) t

17、emp=Rj+1; Rj+1=Rj; Rj=temp; noswap=0; if(noswap=1) break; n-2n-18.3.1 起泡排序冒泡排序的算法分析冒泡排序的算法分析時間效率時間效率：O O（n n2 2) ) 空間效率空間效率：O O（1 1） 只在交換時用到一個緩沖單元只在交換時用到一個緩沖單元穩(wěn)穩(wěn) 定定 性性： 穩(wěn)定穩(wěn)定詳細分析：詳細分析：最好情況：最好情況：初始排列已經(jīng)有序，只執(zhí)行一趟起泡，初始排列已經(jīng)有序，只執(zhí)行一趟起泡，做做 n- -1 次關(guān)鍵碼比較，不移動對象。次關(guān)鍵碼比較，不移動對象。O(n)最壞情形：最壞情形：初始排列逆序，初始排列逆序，算法要執(zhí)行算法要執(zhí)行

18、n-1 1趟起泡，第趟起泡，第i趟趟(1 i n) 做了做了n- i 次關(guān)鍵碼比較，執(zhí)行了次關(guān)鍵碼比較，執(zhí)行了n-i 次對象交換。次對象交換。此時的比較總次數(shù)和記錄移動次數(shù)為：此時的比較總次數(shù)和記錄移動次數(shù)為：11111233121nininninMnninC)()()()(maxmaxO（n2）O（n2）8.3.1 起泡排序分析：分析：設(shè)變量設(shè)變量exchange記載記錄交換的位置，則一趟排記載記錄交換的位置，則一趟排序后，序后，exchange記載的一定是這一趟排序中記錄的最后記載的一定是這一趟排序中記錄的最后一次交換位置，且從此位置以后的所有記錄均已有序一次交換位置，且從此位置以后的所有

19、記錄均已有序。 每趟掃描時，記錄最后一次交換位置每趟掃描時，記錄最后一次交換位置k，則下一趟只需，則下一趟只需掃描到掃描到 k處即可，而不必到處即可，而不必到i。分析：分析：由于一般起泡排序在記錄正序時只作一趟，而反由于一般起泡排序在記錄正序時只作一趟，而反序時作序時作n-1趟。則可考慮每次將從上到下掃描和從下到上趟。則可考慮每次將從上到下掃描和從下到上掃描交替進行，即：從下往上升小的，從上往下降大的。掃描交替進行，即：從下往上升小的，從上往下降大的。（2） 雙向起泡雙向起泡8.3.2 快速排序 假設(shè)待排記錄假設(shè)待排記錄Rl-Rh,Rl-Rh,任取一個記錄任取一個記錄 ( (通常取無序區(qū)通常取

20、無序區(qū)第一個記錄第一個記錄) ) 作為比較的作為比較的基準基準temptemp，以其關(guān)鍵字的值為分界點將全部記錄劃分為兩部以其關(guān)鍵字的值為分界點將全部記錄劃分為兩部分分: :所有所有比它小比它小的元素均位于分界點的元素均位于分界點左側(cè)左側(cè)(Rl-(Rl-Ri-1)Ri-1)，所有，所有比它大比它大的元素的元素均位于分界點均位于分界點右側(cè)右側(cè)(Ri+1-Rh)(Ri+1-Rh), ,則基準則基準temptemp就位于其最終正確位就位于其最終正確位置置Ri;Ri;然后再分別對這兩部分無序區(qū)重復(fù)上述過然后再分別對這兩部分無序區(qū)重復(fù)上述過程，直到程，直到每一部分均只剩一個記錄為止每一部分均只剩一個記錄

21、為止。 ( (又稱劃分交換排序又稱劃分交換排序) )基本思想：基本思想：8.3.2 快速排序解決方法：解決方法：設(shè)待劃分的序列是設(shè)待劃分的序列是Rl-RhRl-Rh，設(shè)指針，設(shè)指針i i，j j分別指向該區(qū)域左、右兩端的下標分別指向該區(qū)域左、右兩端的下標l l和和h h，令，令RlRl為為基準基準temp.temp.（1 1）j j向左向左掃描掃描:j-:j-，找到第一個比基準小的記錄，找到第一個比基準小的記錄RjRj，與，與RiRi交換；交換；（2 2）i i向右向右掃描掃描:i+:i+，找到第一個比基準大的記錄，找到第一個比基準大的記錄RiRi，與，與RjRj交換；交換；（3 3）重復(fù)上述

22、過程，直到）重復(fù)上述過程，直到i=ji=j, ,此時此時i i便為基準最終所便為基準最終所在位置。在位置。關(guān)鍵問題：如何實現(xiàn)一次劃分？關(guān)鍵問題：如何實現(xiàn)一次劃分？快速排序算法分析快速排序算法分析(了解了解)例：例：關(guān)鍵字序列關(guān)鍵字序列 T=(49, 38, 65, 97, 76, 13, 27, 49）8.3.2 快速排序int Partition( rectype R, int l, int h) /*RlRh*/ int i,j; rectype temp; i=l; j=h; temp=Ri; /*初始化初始化*/ do while ( ) j-; /*j向左掃描向左掃描*/ if (i

23、j) Ri+=Rj; while ( ) i+;/*i向右掃描向右掃描*/ if (ij) Rj- -=Ri; while(i!=j) Ri=temp; /*i為基準的最終位置為基準的最終位置*/ retutn i;i= temp.keyij & Ri.key= temp.key8.3.2 快速排序調(diào)用方法：調(diào)用方法：Quicksort(R,0,n-1);Quicksort(R,0,n-1);關(guān)鍵問題：如何處理劃分后得到的兩個待排序子序列？關(guān)鍵問題：如何處理劃分后得到的兩個待排序子序列？ void QuickSort (rectype R, int s1, int t1 ) int i; if

24、 (s1 t1) i= Partition (R,s1, t1); QuickSort (R, s1, i-1); QuickSort ( R, i+1, t1); 解決方法：解決方法：對劃分得到的兩個子序列遞歸地執(zhí)行快速對劃分得到的兩個子序列遞歸地執(zhí)行快速排序。排序。8.3.2 快速排序例：例：49,38,65,97,76,13,27,49的快速排序遞歸樹如下：的快速排序遞歸樹如下：快速排序的快速排序的遞歸執(zhí)行過程遞歸執(zhí)行過程可以用遞歸樹描述?？梢杂眠f歸樹描述?？焖倥判虻男阅芊治隹焖倥判虻男阅芊治?927769749653838138.3.2 快速排序快速排序算法快速排序算法效率分析效率分析

25、：空間復(fù)雜度空間復(fù)雜度: :遞歸調(diào)用時每次的指針遞歸調(diào)用時每次的指針, ,參數(shù)需用棧存放參數(shù)需用棧存放, ,則與遞則與遞歸樹的深度一致歸樹的深度一致. . 最好情況最好情況: :每次劃分將文件均分為兩部分每次劃分將文件均分為兩部分最壞情況最壞情況: :遞歸深度為遞歸深度為n,n,一邊倒一邊倒, ,則則 O(n)O(n)時間復(fù)雜度時間復(fù)雜度: : 最好情況最好情況: :每次都均等分每次都均等分最壞情況最壞情況: :一邊倒一邊倒, ,每次劃分無序區(qū)記錄只少一個每次劃分無序區(qū)記錄只少一個, ,需進行需進行n-1n-1趟排序趟排序, ,每趟每趟n-in-i次比較次比較, ,則則C Cmaxmax= O

26、(n= O(n2 2) ) 小結(jié)小結(jié): :平均時間復(fù)雜度平均時間復(fù)雜度: :快速排序是一種快速排序是一種不穩(wěn)定不穩(wěn)定的排序算法的排序算法. .8.4 選擇排序選擇排序有多種具體實現(xiàn)算法：選擇排序有多種具體實現(xiàn)算法： 1) 1) 直接選擇排序直接選擇排序 2) 2) 堆排序堆排序基本思想基本思想：每一趟從待排記錄中選取關(guān)鍵字最小的記每一趟從待排記錄中選取關(guān)鍵字最小的記錄錄, ,順序放在已排好序的記錄序列后面順序放在已排好序的記錄序列后面, ,直至全部記錄直至全部記錄排完為止。排完為止。8.4.1 直接選擇排序思路簡單：思路簡單：每經(jīng)過每經(jīng)過一趟一趟比較就比較就找出一個最小值找出一個最小值，與待與

27、待排序列最前面的位置互換排序列最前面的位置互換即可。即可。首先，在首先，在n個記錄中選擇最小者放到個記錄中選擇最小者放到R0位置；然后，從位置；然后，從剩余的剩余的n-1個記錄中選擇最小者放到個記錄中選擇最小者放到R1位置；位置；如此進行下如此進行下去，直到全部有序為止。去，直到全部有序為止。優(yōu)點：優(yōu)點：實現(xiàn)簡單實現(xiàn)簡單缺點：缺點：每趟只能確定一個元素，表長為每趟只能確定一個元素，表長為n n時需要時需要n-1n-1趟趟8.4.1 直接選擇排序例：例：關(guān)鍵字序列關(guān)鍵字序列T= T= （2121，2525，4949，2525* *，1616，0808），），請給出請給出直接選擇排序直接選擇排序的

28、具體實現(xiàn)過程。的具體實現(xiàn)過程。原始序列：原始序列： 21，25，49，25*，16，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，25，49，25*，16，2108，16, 49，25*，25，2108，16, 21，25*，25，4908，16, 21，25*，25，4908，16, 21，25*，25，49算法的算法的穩(wěn)定性穩(wěn)定性：因為排序時，因為排序時，2525* *到了到了2525的前面。的前面。最小值最小值 0808 與與R0R0交換位置交換位置8.4.1 直接選擇排序void selectSort ( rectype R ) /*R0Rn-1*/ int i,j,mi

29、n; rectype temp; for (int i=0; in-1; i+) /*n-1 趟趟*/ min=i; for ( j=i+1; jn; j+) /*找最小找最小*/ if (Rj.keyn/2in/2的結(jié)點是葉子結(jié)點的結(jié)點是葉子結(jié)點. .即具即具有有n n個結(jié)點的完全二叉樹個結(jié)點的完全二叉樹, ,有有 個葉子結(jié)點個葉子結(jié)點. .2)2)從從最后一個非葉子結(jié)點最后一個非葉子結(jié)點開始開始, ,即即i=n/2i=n/2( (注注: :整除整除),),以其為以其為根根, ,將該將該子樹調(diào)整為堆子樹調(diào)整為堆; ;再調(diào)下一個非葉子結(jié)再調(diào)下一個非葉子結(jié)點點, ,逐個調(diào)整至以逐個調(diào)整至以第一個

30、非葉子結(jié)點第一個非葉子結(jié)點為根的樹調(diào)整為根的樹調(diào)整為堆為堆, ,則就完成了初始化堆的過程則就完成了初始化堆的過程. .2/n8.4.2 堆排序思想：思想：由于其左右子樹均為堆由于其左右子樹均為堆,則以則以Ri為根的樹中的為根的樹中的最大值只能在最大值只能在Ri與其左右孩子結(jié)點中選擇與其左右孩子結(jié)點中選擇.(1) 若若Ri.key最大最大,則無須調(diào)整則無須調(diào)整,即為大根堆即為大根堆;(2) 若左右孩子結(jié)點之一最大若左右孩子結(jié)點之一最大(假設(shè)假設(shè)R2i.key最大最大),則則Ri與與R2i交換；但交換后可能導(dǎo)致以交換；但交換后可能導(dǎo)致以R2i為為根的子樹被破壞不再是堆，由于以根的子樹被破壞不再是堆

31、，由于以R2i為根的為根的左右子樹仍為堆，則重復(fù)此過程，繼續(xù)向下篩左右子樹仍為堆，則重復(fù)此過程，繼續(xù)向下篩選。選。8.4.2 堆排序創(chuàng)建堆和調(diào)整堆的方法實例創(chuàng)建堆和調(diào)整堆的方法實例: (: (大根堆大根堆) )1.1.創(chuàng)建完全二叉樹創(chuàng)建完全二叉樹152011231310 1 2 3 4 5 61510201323111110,無需調(diào)整無需調(diào)整8.4.2 堆排序152011231310 1 2 3 4 5 61510201323112023,篩下篩下202.2.調(diào)整調(diào)整8.4.2 堆排序152311201310 1 2 3 4 5 61510231320111523,1523,篩下篩下15151

32、520,篩下篩4.2 堆排序231020131511初始建堆結(jié)果初始建堆結(jié)果:23 20 11 15 13 10:23 20 11 15 13 10232011151310 1 2 3 4 5 6例：例：關(guān)鍵字序列關(guān)鍵字序列 T=(42, 13, 91, 23, 24, 76, 05, 88）void SIFT (rectype R, int i, int m ) /*Ri-Rm*/ int j; rectype temp; temp=Ri; j=2*i; /*左孩子下標左孩子下標*/ while (j=m ) if (jm & Rj.keyRj+1.key) j+;

33、 if (temp.key=1; i-) SIFT(R,i,n) ; 關(guān)鍵問題：如何由一個無序序列建成一個堆？關(guān)鍵問題：如何由一個無序序列建成一個堆？注：注：最后一個結(jié)點（葉子）的序號是最后一個結(jié)點（葉子）的序號是n，則最后一個分支結(jié)點則最后一個分支結(jié)點(非葉子結(jié)點非葉子結(jié)點)即為結(jié)點即為結(jié)點n的雙親，的雙親，其序號是其序號是n/2。8.4.2 堆排序堆排序算法堆排序算法void HeapSort ( rectype R ) /*R1-Rn*/ int i; rectype temp; for (i=n/2; i=1; i-) /*初始化堆初始化堆*/ SIFT(R,i,n); for (i=

34、n; i1; i- ) /*n-1趟趟*/ temp=R1; /*交換交換*/ R1=Ri; Ri=temp; SIFT(R,1,i-1); /*重建堆重建堆*/ 8.4.2 堆排序SIFT( )8.5 歸并排序關(guān)鍵字序列關(guān)鍵字序列T= （21，25，49，25*，93，62，72，08，37，16，54），請給出歸并排序的具體），請給出歸并排序的具體實現(xiàn)過程。實現(xiàn)過程。關(guān)鍵問題：關(guān)鍵問題：如何將如何將兩個有序序列兩個有序序列合成合成一個有序序列一個有序序列？設(shè)設(shè)Rlow-RmidRlow-Rmid和和Rmid+1-RhighRmid+1-Rhigh為相鄰，歸并為相鄰，歸并成一個有序序列成一個

35、有序序列R1low - R1high R1low - R1high 。low m m+1 highR lowhigh R1 ijk若若Ri.key=Rj.key,Ri.keyRj.key, Ri.keyRj.key, 則則R1k=Rj;k+;j+; R1k=Rj;k+;j+; 8.5 歸并排序void Merge (rectype R , rectype R1 , int low, int mid, int high ) int i,j,k; i=low; j=mid+1; k=low; while (i=mid & j=high) if (Ri.key=Rj.key) R1k+=Ri+; else R1k+=Rj+; while (i=mid) R1k+=Ri+; while (j=high) R1k+=Rj+; 算法描述：僅實現(xiàn)一次歸并算法描述：僅實現(xiàn)一次歸并, ,且只歸并兩組且只歸并兩組. . 8.5 歸并排序void Mergepass (rectype R , r