《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C語(yǔ)言版）》課件第8章 排序

第8章排序本章中主要介紹下列內(nèi)容：排序的概念插入排序方法：直接插入排序和希爾排序交換排序方法：冒泡排序和快速排序選擇排序方法：直接選擇排序和堆排序歸并排序方法本章目錄8.1排序的基本概念18.2插入排序28.3交換排序38.4選擇排序48.5歸并排序58.6本章小結(jié)6結(jié)束8.1排序的基本概念8.1.1排序的定義8.1.2相關(guān)概念返回到總目錄8.1.1排序的定義有n個(gè)記錄的序列{R1，R2，…，Rn}，其相應(yīng)關(guān)鍵字的序列是{K1，K2，…，Kn}，相應(yīng)的下標(biāo)序列為1，2，…，n。通過排序，要求找出當(dāng)前下標(biāo)序列1，2，…，n的一種排列p1，p2，…，pn，使得相應(yīng)關(guān)鍵字滿足如下的非遞減（或非遞增）關(guān)系，即：Kp1≤Kp2≤…≤Kpn

，這樣就得到一個(gè)按關(guān)鍵字有序的記錄序列：{Rp1，Rp2，…，Rpn}。這樣一種操作稱為排序。簡(jiǎn)單的說，就是將無(wú)序序列按記錄中的關(guān)鍵字排成以該關(guān)鍵字有序的序列過程就是排序。返回到本節(jié)目錄關(guān)鍵字Ki可以是記錄Ri的主關(guān)鍵字，也可以是記錄Ri的次主關(guān)鍵字。若Ki是記錄Ri的主關(guān)鍵字，則任何一個(gè)記錄的無(wú)序序列經(jīng)過排序后得到的結(jié)果是唯一的；若Ki是記錄Ri的次主關(guān)鍵字，則經(jīng)過排序后得到的結(jié)果可能不一唯一。這是因?yàn)樵诖判虻挠涗浶蛄兄锌赡艽嬖趦蓚€(gè)或兩個(gè)以上關(guān)鍵字相等的記錄。返回到本節(jié)目錄8.1.2相關(guān)概念1．內(nèi)部排序整個(gè)排序過程完全在內(nèi)存中進(jìn)行，稱為內(nèi)部排序。2．外部排序由于待排序記錄數(shù)據(jù)量太大，內(nèi)存無(wú)法容納全部數(shù)據(jù)，排序需要借助外部存儲(chǔ)設(shè)備才能完成，稱為外部排序。3．穩(wěn)定排序和不穩(wěn)定排序假設(shè)Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，若在排序前的序列中Ri領(lǐng)先于Rj(即i<j)，經(jīng)過排序后得到的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的；反之，若相同關(guān)鍵字的先后次序在排序過程中發(fā)生變化者，則稱所用的排序方法是不穩(wěn)定的。返回到本節(jié)目錄本章主要介紹的是內(nèi)部排序。內(nèi)部排序主要分為插入排序法、交換排序法、選擇排序法和歸并排序法。我們假定待排序的記錄均是以順序存儲(chǔ)結(jié)構(gòu)存放的，且假定記錄的關(guān)鍵字均為整數(shù)。另外，假定待排序的記錄是按遞增順序進(jìn)行排序。其排序記錄的數(shù)據(jù)類型定義如下：返回到本節(jié)目錄#defineMaxSize100/*查找表中最大元素個(gè)數(shù)*/typedefintKeyType;/*重定義關(guān)鍵字類型為整型，也可以為其它類型*/typedefcharElemType;/*重定義數(shù)據(jù)項(xiàng)類型為字符型*/typedefstruct{KeyTypeKey;/*關(guān)鍵字域*/ElemTypedata;/*其他數(shù)據(jù)項(xiàng)*/}LineList;/*線性查找表類型*/返回到本節(jié)目錄8.2插入排序8.2.1直接插入排序8.2.2希爾排序返回到總目錄8.2.1直接插入排序1．直接插入排序的基本思想直接插入排序是一種最簡(jiǎn)單的排序方法，它的基本思想是依次將記錄序列中的每一個(gè)記錄插入到有序段中，使有序段的長(zhǎng)度不斷地?cái)U(kuò)大。有n個(gè)記錄的無(wú)序序列具體的排序過程可以描述如下：（1）首先將待排序記錄序列中的第一個(gè)記錄作為一個(gè)有序段，此時(shí)這個(gè)有序段中只有一個(gè)記錄。（2）從第2個(gè)記錄起到最后一個(gè)記錄，依次將記錄和前面子序列中的記錄比較，確定記錄插入的位置。返回到本節(jié)目錄（3）將記錄插入到子序列中，子序列中的記錄個(gè)數(shù)加1，直至子序列長(zhǎng)度和原來(lái)待排序列長(zhǎng)度一致時(shí)排序結(jié)束。一共經(jīng)過n-1趟就可以將初始序列的n個(gè)記錄重新排列成按關(guān)鍵字值從小到大排列的有序序列。為了防止在比較過程中數(shù)組下標(biāo)的溢出，我們?cè)O(shè)一個(gè)監(jiān)視哨r[0]，即先將要比較的關(guān)鍵字存入監(jiān)視哨r[0]中，然后再用r[0]從后向前進(jìn)行比較。若r[0]小于所比較的關(guān)鍵字，則將該關(guān)鍵字向后移一位，并且繼續(xù)向前比較，直到r[0]大于等于所比較的關(guān)鍵字時(shí)結(jié)束。因?yàn)槲覀兪沁叡容^邊移動(dòng)記錄的，所以在當(dāng)前比較記錄的后面位置是空出來(lái)的，直接將r[0]存入即可。返回到本節(jié)目錄【例8.1】設(shè)待排序的記錄序列有n=7個(gè)記錄，其關(guān)鍵字的初始序列為：{32，15，6，48，19，21，49}，請(qǐng)給出直接插入排序的過程。在序列中有兩個(gè)相同關(guān)鍵字15，我們用方框?qū)⒑笠粋€(gè)15框上加以區(qū)分。解：直接插入排序過程如圖8-1所示。就是對(duì)此記錄序列進(jìn)行直接插入排序的過程示意圖。其中括號(hào)內(nèi)部的關(guān)鍵字為已排好序的部分。返回到本節(jié)目錄圖8-1直接插入排序過程返回到本節(jié)目錄2．直接插入排序的算法如算法8.1所示算法8.1voidInsertSort(LineListr[],intn){inti,j;for(i=2;i<=n;i++)/*一共需要比較n-1趟*/{r[0]=r[i];/*將r[0]賦為監(jiān)視哨*/j=i-1;返回到本節(jié)目錄while(r[0].Key<r[j].Key)/*搜索插入位置*/{r[j+1]=r[j];j=j-1;}r[j+1]=r[0];/*將原來(lái)r[i]中的記錄放入第j+1個(gè)位置*/}}該算法的主函數(shù)同后面希爾排序的主函數(shù)，只是將調(diào)用語(yǔ)句改為InsertSort(r,n);即可。返回到本節(jié)目錄3．直接插入排序算法分析：從空間角度來(lái)看，它只需要一個(gè)輔助空間r[0]。

從時(shí)間耗費(fèi)角度來(lái)看，主要時(shí)間耗費(fèi)在關(guān)鍵字比較和移動(dòng)元素上。算法執(zhí)行時(shí)間在最壞的情況下是O(n2)。在這種插入過程中兩個(gè)15先后位置沒有發(fā)生變化，所以直接插入排序是一種穩(wěn)定排序方法。返回到本節(jié)目錄8.2.2希爾排序1．希爾排序的基本思想希爾排序又稱為縮小增量排序，其基本思想是：先將待排序的記錄劃分為幾組，從而減小參與直接插入排序的數(shù)據(jù)量，當(dāng)經(jīng)過幾次分組排序后，記錄的排列已經(jīng)基本有序，最后再對(duì)所有的記錄實(shí)施直接插入排序。希爾排序的具體方法如下：返回到本節(jié)目錄

（1）取定一個(gè)正整數(shù)d1<n，把d1作為間隔值，把全部記錄從第一個(gè)記錄起進(jìn)行分組，所有距離為dk1倍數(shù)的記錄放在一組中，在各組內(nèi)進(jìn)行直接插入排序。（2）取定一個(gè)正整數(shù)d2<d1，重復(fù)上述分組和排序工作，直至取di=1為止，即所有記錄在一個(gè)組中進(jìn)行直接插入排序。希爾提出的d1=，di+1=。返回到本節(jié)目錄【例8.2】已知待排序的一組記錄的關(guān)鍵字初始排列為{25，36，12，68，45，16，37，22}，請(qǐng)給出希爾排序的過程。解：其希爾排序的過程如圖8-2所示。圖8-2希爾排序的過程返回到本節(jié)目錄2．希爾排序的算法（1）希爾排序如算法8.2所示。算法8.2voidShellSort(LineListr[],intn){inti,j,d;d=n/2;/*初始步長(zhǎng)為表長(zhǎng)的一半*/while(d>0){for(i=d;i<=n;i++){r[0]=r[i];/*設(shè)監(jiān)視哨*/

j=i-d;返回到本節(jié)目錄while(j>=0&&r[0].Key<r[j].Key){r[j+d]=r[j];j=j-d;}r[j+d]=r[0];j=j-d;}d=d/2;}}返回到本節(jié)目錄8.3交換排序交換排序的基本方法是：通過兩兩比較待排序記錄的關(guān)鍵字，若有不滿足次序要求的一對(duì)數(shù)據(jù)則交換，直到全部滿足為止。本節(jié)主要介紹冒泡排序和快速排序兩種排序方法。8.3.1冒泡排序8.3.2快速排序返回到總目錄8.3.1冒泡排序1．冒泡排序的基本思想冒泡排序是交換排序中一種簡(jiǎn)單的排序方法。它的基本思想是對(duì)所有相鄰記錄的關(guān)鍵字值進(jìn)行比較，如果是逆序（r[j]>r[j+1]），則將其交換，最終達(dá)到有序化。其處理過程為：（1）將整個(gè)待排序的記錄序列劃分成有序區(qū)和無(wú)序區(qū)。初始狀態(tài)有序區(qū)為空，無(wú)序區(qū)包括所有待排序的記錄。返回到本節(jié)目錄（2）對(duì)無(wú)序區(qū)從前向后依次將相鄰記錄的關(guān)鍵字進(jìn)行比較，若逆序則將其交換，從而使得關(guān)鍵字值小的記錄向上“飄”（左移），關(guān)鍵字值大的記錄向下“沉”（右移）。每經(jīng)過一趟冒泡排序，都使無(wú)序區(qū)中關(guān)鍵字值最大的記錄進(jìn)入有序區(qū)，對(duì)于由n個(gè)記錄組成的記錄序列，最多經(jīng)過n-1趟冒泡排序，就可以將這n個(gè)記錄重新按關(guān)鍵字順序排列。返回到本節(jié)目錄【例8.3】已知有10個(gè)待排序的記錄，它們的關(guān)鍵字序列為{43，12，35，18，26，57，7，21，43，46}，給出冒泡排序法進(jìn)行排序的過程。（兩個(gè)相同的關(guān)鍵字43，后面的43用方框框上）解：冒泡排序的過程如圖8-3所示。其中括號(hào)內(nèi)表示有序區(qū)。返回到本節(jié)目錄圖8-3冒泡排序的過程返回到本節(jié)目錄2．冒泡排序算法（1）基本的冒泡排序算法對(duì)由n個(gè)記錄組成的記錄序列，最多經(jīng)過（n-1）趟冒泡排序，就可以使記錄序列成為有序序列，第一趟定位第n個(gè)記錄，此時(shí)有序區(qū)只有一個(gè)記錄；第二趟定位第n-1個(gè)記錄，此時(shí)有序區(qū)有兩個(gè)記錄；以此類推，直到最后所有的記錄都進(jìn)入有序區(qū)，排序結(jié)束。完整的冒泡排序算法如算法8.3所示。返回到本節(jié)目錄算法8.3voidBubbleSort1(LineListr[],intn){inti,j;LineListtemp;for(i=n-1;i>0;i--)/*i為每趟排序的數(shù)組最大下標(biāo)值*/for(j=0;j<=i-1;j++)/*一趟交換排序*/ if(r[j].Key>r[j+1].Key)/*若逆序*/{temp=r[j];r[j]=r[j+1];r[j+1]=temp;}}返回到本節(jié)目錄（2）改進(jìn)的冒泡排序算法在冒泡排序過程中，一旦發(fā)現(xiàn)某一趟沒有進(jìn)行交換操作，就表明此時(shí)待排序記錄序列已經(jīng)成為有序序列，冒泡排序再進(jìn)行下去已經(jīng)沒有必要，應(yīng)立即結(jié)束排序過程。如例8.1題中，在第六趟排序后，序列已經(jīng)成為有序序列，從第七次到第九次排序就沒有必要。為實(shí)現(xiàn)這一方法我們?cè)谘h(huán)體內(nèi)設(shè)一個(gè)查看是否有記錄交換的變量，在每趟比較時(shí)查看是否有交換，如果沒有，則提前結(jié)束循環(huán)。改進(jìn)的冒泡排序算法如算法8.4所示。返回到本節(jié)目錄算法8.4voidBubbleSort2(LineListr[],intn){inti,j,exchange;/*exchange為標(biāo)記是否交換的標(biāo)識(shí)變量*/LineListtemp; for(i=n-1;i>0;i--)/*i為每趟排序的數(shù)組最大下標(biāo)值*/ {exchange=0;

返回到本節(jié)目錄for(j=0;j<=i-1;j++)/*一趟交換排序*/ if(r[j].Key>r[j+1].Key)/*若逆序*/ {temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=1;} if(exchange==0)return; }}返回到本節(jié)目錄8.3.2快速排序快速排序（QuickSort）是對(duì)起泡排序的一種改進(jìn)。1．快速排序的基本思想快速排序又稱為分區(qū)交換排序，通過一趟排序?qū)⒋判虻挠涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可以分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。返回到本節(jié)目錄具體過程是：首先將待排序記錄序列中的所有記錄作為當(dāng)前待排序區(qū)域，從中任選取一個(gè)記錄（通常選取第一個(gè)記錄）作為支點(diǎn)（或樞軸），并以該記錄的關(guān)鍵字值為基準(zhǔn)，從位于待排序記錄序列左右兩端開始，逐漸向中間靠攏，交替與基準(zhǔn)記錄的關(guān)鍵字進(jìn)行比較、交換。每次比較，若遇左側(cè)記錄的關(guān)鍵字值大于基準(zhǔn)記錄的關(guān)鍵字，則將其與基準(zhǔn)記錄交換，使其移到基準(zhǔn)記錄的右側(cè)；若遇右側(cè)記錄的關(guān)鍵字值小于基準(zhǔn)值，則將其與基準(zhǔn)記錄交換，使其移至基準(zhǔn)記錄的左側(cè)，最后讓基準(zhǔn)記錄到達(dá)它的最終位置。返回到本節(jié)目錄此時(shí)，基準(zhǔn)記錄將待排序記錄分成了左右兩個(gè)區(qū)域，位于基準(zhǔn)記錄左側(cè)的記錄都小于或等于基準(zhǔn)記錄的關(guān)鍵字，位于基準(zhǔn)記錄右側(cè)的所有記錄的關(guān)鍵字都大于或等于基準(zhǔn)記錄的關(guān)鍵字，這就是一趟快速排序。一趟快速排序之后，再分別對(duì)左右兩個(gè)區(qū)域進(jìn)行快速排序，以此類推，直到每個(gè)分區(qū)域都只有一個(gè)記錄為止。此時(shí)整個(gè)待排序記錄按關(guān)鍵值有序排列，至此排序結(jié)束。返回到本節(jié)目錄【例8.2】已知一個(gè)無(wú)序序列，其關(guān)鍵字值為{32，42，7，48，15，48，12，18}的記錄序列，給出進(jìn)行快速排序的過程。（其中有兩個(gè)相同的關(guān)鍵字48，后一個(gè)用括號(hào)括起）解：冒泡排序的過程如圖8-4所示（小括號(hào)（）內(nèi)的關(guān)鍵字表示支點(diǎn)，中括號(hào)[]內(nèi)關(guān)鍵字為待排序區(qū)間）。返回到本節(jié)目錄返回到本節(jié)目錄（b）完整的快速排序過程圖8-4快速排序過程示意圖返回到本節(jié)目錄2．快速排序的算法（1）快速排序的算法如算法8.5所示。算法8.5voidQuickSort(LineListr[],intfirst,intend){inti,j;LineListtemp;i=first;j=end;temp=r[i];/*初始化*/while(i<j)返回到本節(jié)目錄{while(i<j&&temp.Key<=r[j].Key)j--;r[i]=r[j];while(i<j&&r[i].Key<=temp.Key)i++;r[j]=r[i];}r[i]=temp;if(first<i-1)QuickSort(r,first,i-1);/*對(duì)左側(cè)分區(qū)域進(jìn)行快速排序*/if(i+1<end)QuickSort(r,i+1,end);/*對(duì)右側(cè)分區(qū)域進(jìn)行快速排序*/}返回到本節(jié)目錄8.4選擇排序選擇排序是指在排序過程序中，依次從待排序的記錄序列中選擇出關(guān)鍵字值最小的記錄、關(guān)鍵字值次小的記錄、……，并分別將它們定位到序列左側(cè)的第1個(gè)位置、第2個(gè)位置、……，最后剩下一個(gè)關(guān)鍵字值最大的記錄位于序列的最后一個(gè)位置，從而使待排序的記錄序列成為按關(guān)鍵字值由小到大排列的的有序序列。8.4.1直接選擇排序8.4.2堆排序返回到總目錄8.4.1直接選擇排序1．直接選擇排序的基本思想簡(jiǎn)單選擇排序的基本思想是：每一趟在n-i+1(i=1,2,3,...,n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個(gè)記錄。它的具體實(shí)現(xiàn)過程為：（1）將整個(gè)記錄序列劃分為有序區(qū)域和無(wú)序區(qū)域，有序區(qū)域位于最左端，無(wú)序區(qū)域位于右端，初始狀態(tài)有序區(qū)域?yàn)榭眨瑹o(wú)序區(qū)域含有待排序的所有n個(gè)記錄。（2）設(shè)置一個(gè)整型變量index，用于記錄在一趟的比較過程中，當(dāng)前關(guān)鍵字值最小的記錄位置。返回到本節(jié)目錄開始將它設(shè)定為當(dāng)前無(wú)序區(qū)域的第一個(gè)位置，即假設(shè)這個(gè)位置的關(guān)鍵字最小，然后用它與無(wú)序區(qū)域中其他記錄進(jìn)行比較，若發(fā)現(xiàn)有比它的關(guān)鍵字還小的記錄，就將index改為這個(gè)新的最小記錄位置，隨后再用a[index].key與后面的記錄進(jìn)行比較，并根據(jù)比較結(jié)果，隨時(shí)修改index的值，一趟結(jié)束后index中保留的就是本趟選擇的關(guān)鍵字最小的記錄位置。（3）將index位置的記錄交換到有序區(qū)域的第一個(gè)位置，使得有序區(qū)域擴(kuò)展了一個(gè)記錄，而無(wú)序區(qū)域減少了一個(gè)記錄。不斷重復(fù)（2）、（3），直到無(wú)序區(qū)域剩下一個(gè)記錄為止。此時(shí)所有的記錄已經(jīng)按關(guān)鍵字從小到大的順序排列就位。返回到本節(jié)目錄（1）直接選擇排序的程序如算法8.6所示。算法8.6voidSelectSort(LineListr[],intlength)/*對(duì)記錄數(shù)組r做簡(jiǎn)單選擇排序，length為數(shù)組的長(zhǎng)度*/{inti,j,k,n;LineListx;n=length;2．直接選擇排序的算法返回到本節(jié)目錄for(i=0;i<n;++i){k=i;for(j=i+1;j<=n;++j)if(r[j].Key<r[k].Key)k=j;if(k!=i){x=r[i];r[i]=r[k];r[k]=x;}}}/*SelectSort*/返回到本節(jié)目錄8.4.2堆排序1．堆的定義堆排序是另一種基于選擇的排序方法。我們先介紹一下什么是堆？然后再介紹如何利用堆進(jìn)行排序。堆定義：由n個(gè)元素組成的序列{k1，k2，……，kn-1，kn}，當(dāng)且僅當(dāng)滿足如下關(guān)系時(shí)，稱之為堆。返回到本節(jié)目錄若將堆看成是一棵以k1為根的完全二叉樹，則這棵完全二叉樹中的每個(gè)非終端結(jié)點(diǎn)的值ki均不大于（或不小于）其左、右孩子結(jié)點(diǎn)的值。由此可以看出，若一棵完全二叉樹是堆，則根結(jié)點(diǎn)一定是這n個(gè)結(jié)點(diǎn)中的最小者或最大者。一般的，堆頂元素為最小值，該堆成為小根堆；堆頂元素為最大值，該堆成為大根堆。例如，下列A、B兩個(gè)序列為堆，對(duì)應(yīng)的完全二叉樹如圖8-5所示。序列A={56，32，28，22，16，7，13，18}構(gòu)成的是大根堆；序列B={5，13，18，22，35，24}構(gòu)成的是小根堆。返回到本節(jié)目錄（a）堆頂元素取最大值，為大根堆（b）堆頂元素取最小值，為小根堆圖8-5堆的示例返回到本節(jié)目錄2．堆排序的方法堆排序的基本思想是：首先將待排序的記錄序列構(gòu)造一個(gè)堆，此時(shí)，選出了堆中所有記錄的最小者或最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次?。ɑ虼未螅┑挠涗?，以此類推，直到堆中只有一個(gè)記錄為止，每個(gè)記錄出堆的順序就是一個(gè)有序序列。因此，堆排序的關(guān)鍵步驟有兩個(gè)：一是構(gòu)造堆，即如何將一個(gè)無(wú)序序列建成初始堆；第二是調(diào)整堆，即如何在輸出堆的根結(jié)點(diǎn)之后，調(diào)整剩余元素成為一個(gè)新的堆。首先考慮第二個(gè)問題，調(diào)整堆；然后再考慮第一個(gè)問題，構(gòu)造堆。返回到本節(jié)目錄（1）調(diào)整堆假設(shè)有一個(gè)小根堆，當(dāng)輸出堆頂元素（根結(jié)點(diǎn)）后，以堆中最后一個(gè)元素替代它。此時(shí)根結(jié)點(diǎn)的左子樹和右子樹均為堆，則只需自上而下進(jìn)行調(diào)整即可。首先將堆頂元素與其左、右子樹根結(jié)點(diǎn)的值進(jìn)行比較，如果堆頂元素比它的兩個(gè)子結(jié)點(diǎn)都小，則已經(jīng)是堆；否則，讓堆頂元素與其中較小的孩子結(jié)點(diǎn)交換，先讓堆頂滿足堆的性質(zhì)?？赡芤?yàn)榻粨Q，使交換后的結(jié)點(diǎn)為根的子樹不再滿足堆的性質(zhì)，則重復(fù)向下調(diào)整，當(dāng)調(diào)整使新的更小子樹依舊滿足堆的性質(zhì)時(shí)，重新建堆的過程結(jié)束。這種自上而下的建堆過程稱為結(jié)點(diǎn)向下的“篩選”。圖8-6是一個(gè)小根堆的排序輸出過程。

返回到本節(jié)目錄圖8-6一個(gè)小根堆的排序過程返回到本節(jié)目錄（2）構(gòu)造堆為了構(gòu)造初始堆，可以在已是堆的兩個(gè)子序列中面加上它們的根結(jié)點(diǎn)，并且作必要的調(diào)整使之成為更大的堆。加上根結(jié)點(diǎn)后，可以不滿足堆的定義，則可以用前面所述的“篩選”方法，使之成為堆。所以，一個(gè)無(wú)序序列構(gòu)造堆的過程就是反復(fù)“篩選”的過程。返回到本節(jié)目錄若將n個(gè)待排序記錄的關(guān)鍵字序列看成是一個(gè)完全二叉樹，則最后一個(gè)非葉子結(jié)點(diǎn)是第

個(gè)元素。首先，將n個(gè)葉子結(jié)點(diǎn)看成是n個(gè)堆，然后從第

個(gè)結(jié)點(diǎn)開始，依次將第

個(gè)結(jié)點(diǎn)，第

-1個(gè)結(jié)點(diǎn)，…，第1個(gè)結(jié)點(diǎn)按照堆的定義逐一加到它們的子結(jié)點(diǎn)上，直到建成一個(gè)完全的堆。返回到本節(jié)目錄例如，圖8-7（a）中的完全二叉樹表示一個(gè)有8個(gè)元素的無(wú)序序列：{49，38，65，97，76，13，27，49}（相同的兩個(gè)關(guān)鍵字49，其中后面一個(gè)用49表示），則構(gòu)造堆的過程如圖8-7（b）~（f）所示。返回到本節(jié)目錄圖8-7無(wú)序完全二叉樹構(gòu)造堆的過程返回到本節(jié)目錄3．堆排序算法（1）篩選過程如算法8.7所示。算法8.7voidSift(LineListr[],intlow,inthigh)/*假設(shè)r[k..high]是以r[k]為根的完全二叉樹,且分別以r[2k]和r[2k+1]為根的左、右子樹為大根堆,調(diào)整r[k],使整個(gè)序列r[k..high]滿足堆的性質(zhì)*/{inti=low,j=2*i;LineListtmp=r[i];/*暫存“根”記錄r[k]*/返回到本節(jié)目錄while(j<=high){if(j<high&&r[j].Key<r[j+1].Key) j=j+1;/*若存在右子樹,且右子樹根的關(guān)鍵字大,則沿右分支“篩選”*/if(tmp.Key<r[j].Key){r[i]=r[j]; i=j; j=2*i;}/*繼續(xù)篩選*/elsebreak;}r[i]=tmp;/*r[k]填入到恰當(dāng)?shù)奈恢?/}/*sift*/返回到本節(jié)目錄（2）堆排序的算法如算法8.8所示。算法8.8voidHeapSort(LineListr[],intn)/*對(duì)記錄數(shù)組r建堆,n為數(shù)組的長(zhǎng)度*/{inti;LineListtmp;for(i=n/2;i>=1;i--)Sift(r,i,n);for(i=n;i>=1;i--)/*自第n個(gè)記錄開始進(jìn)行篩選建堆*/{tmp=r[1];r[1]=r[i];r[i]=tmp;Sift(r,1,i-1);

}}返回到本節(jié)目錄8.5歸并排序1．歸并排序的基本思想歸并排序是另一類排序方法。所謂歸并是指將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。歸并排序的基本思想是：首先，將r[0..n-1]看成是n個(gè)長(zhǎng)度為1的有序表，將相鄰的有序表成對(duì)歸并，得到n/2個(gè)長(zhǎng)度為2的有序表。然后，再將這些有序表成對(duì)歸并，得到n/4個(gè)長(zhǎng)度為4的有序表，如此反復(fù)進(jìn)行下去，最后得到一個(gè)長(zhǎng)度為n的有序表。返回到總目錄由于歸并是在相鄰的兩個(gè)有序表中進(jìn)行的，因此，上述排序方法也叫二路歸并排序。如果歸并操作在相鄰的多個(gè)有序表中進(jìn)行，則叫多路歸并排序。在此只討論二路歸并排序（簡(jiǎn)稱歸并排序）。2．歸并排序過程示例

【例8.3】對(duì)具有初始輸入序列{26，5，77，1，61，11，59，15，48，19}的記錄采用歸并排序法進(jìn)行排序，序列在每遍掃描時(shí)合并的情況如圖8-8所示。其中h為歸并排序的有序表中元素個(gè)數(shù)，n為表總長(zhǎng)度。初始h=1，以后hi+1=2hi，當(dāng)n>h時(shí)進(jìn)行歸并排序，當(dāng)n<h時(shí)結(jié)束歸并排序。返回到本節(jié)首頁(yè)圖8-8歸并排序過程返回到本節(jié)首頁(yè)3．歸并排序的算法（1）一次歸并算法在上面所示的過程中，有兩個(gè)過程，一個(gè)是每?jī)蓚€(gè)有序表的歸并，然后是多次歸并操作，最后實(shí)現(xiàn)整個(gè)歸并過程。先介紹將兩個(gè)有序表歸并為一個(gè)有序表的算法Merge()。設(shè)兩個(gè)有序表存放在同一數(shù)組中相鄰的位置上：r[low..mid]，r[mid+1..high]。先將它們合并到一個(gè)局部的暫存數(shù)組r1中，待合并完成后將r1復(fù)制回r中。為了簡(jiǎn)便，稱r[low..mid]為第一段，r[mid+1..high]為第2段。每次從兩個(gè)段中取出一個(gè)記錄進(jìn)行關(guān)鍵字的比較，將較小者放入r1中，最后將各段中余下的部分直接復(fù)制到r1中。這樣r1是一個(gè)有序表，再將其復(fù)制回r中。算法如算法8.9所示。返回到本節(jié)首頁(yè)算法8.9voidMerge(LineListr[],intlow,intmid,inthigh){LineList*r1;inti=low,j=mid+1,k=0;/*k是r1的下標(biāo),i,j分別為第1,2段的下標(biāo)*/r1=(LineList*)malloc((high-low+1)*sizeof(LineList));while(i<=mid&&j<=high)if(r[i].Key<=r[j].Key){r1[k]=r[i];i++;k++;}返回到本節(jié)首頁(yè)e