數(shù)據(jù)結(jié)構(gòu)課件chap9

Chapter09Internalsorting

第九章內(nèi)部排序Prof.QingWangProf.Q.WangContentDefinitionandnotationsofsortingInsertionbasedsortingSwapbasedsortingSelectionbasedsortingMergingbasedsortingRadixsortingConclusionProf.Q.Wang1)Internalsorting(內(nèi)部排序)

和externalsorting(外部排序)

排序的確切定義：假設(shè)含n個記錄的序列為{R1,R2,…,Rn}，其相應(yīng)的關(guān)鍵字序列為

{K1,K2,…,Kn}

需確定1,2,…,n的一種排列p1,p2,…,pn，使其相應(yīng)的關(guān)鍵字滿足如下的非遞減（或非遞增）關(guān)系。使序列成為一個按關(guān)鍵字有序的序列的過程稱為排序。這樣一種操作稱為排序。 9.1DefinitionandnotationsProf.Q.Wang

上述排序中的關(guān)鍵字可以是主關(guān)鍵字，也可以是次關(guān)鍵字，如果是主關(guān)鍵字，則排序結(jié)果是唯一的；若是次關(guān)鍵字排序結(jié)果可能不是唯一的。假設(shè)Ki=Kj(1<=i,j<=n,i

j)，且在排序前的序列中Ri領(lǐng)先于Rj(即i<j)，若在排序后的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是Stable(穩(wěn)定)的，否則是Unstable(不穩(wěn)定)的。例如：排序前：204825972725*102338排序后：3202525*27384897102(穩(wěn)定的) 32025*2527384897102(不穩(wěn)定的)9.1DefinitionandnotationsProf.Q.Wang多關(guān)鍵字問題Prof.Q.WangSolution(1)Prof.Q.WangSolution(2)Prof.Q.Wang2)排序中的基本操作：比較關(guān)鍵字大小移動記錄（交換數(shù)據(jù)） 前一種基本操作對大多數(shù)的排序方法是必須的，而后一個操作可以通過改變記錄的存儲方式來予以避免。9.1DefinitionandnotationsProf.Q.Wang3)待排序記錄的存儲方式：順序表：存放在地址連續(xù)的一組存儲單元中，記錄之間的關(guān)系由存儲位置決定，排序必須移動記錄；靜態(tài)鏈表：記錄之間的關(guān)系由指針指示，排序不用移動記錄，指向修改指針；鏈表排序附加地址：待排序記錄本身存儲在一組地址連續(xù)的存儲單元內(nèi)，同時附設(shè)一個指示記錄存儲位置的地址向量，排序過程中不移動記錄，而移動地址向量中這些記錄的地址，在排序結(jié)束后，再按照地址向量中的值調(diào)整記錄的存儲位置。地址排序9.1DefinitionandnotationsProf.Q.Wang4)順序存儲結(jié)構(gòu)#defineMAXNUM100typedefintKeyType;typedefintDataType;typedefstruct{ KeyTypekey; DataTypeInfo;}RecordNode;typedefstruct{ RecordNoderecord[MAXNUM+1]; intn;/*記錄個數(shù)*/}SortObject;9.1DefinitionandnotationsProf.Q.Wang5)排序評價標(biāo)準(zhǔn)

Runningtime(執(zhí)行時間)Comparisontimes(比較次數(shù))Movementtimes(移動次數(shù))Space(所需附加空間)Complexity(算法復(fù)雜程度)9.1DefinitionandnotationsProf.Q.WangFivetypicalinternalsortingmethods 1.Insertionbasedsorting 2.Swapbasedsorting 3.Selectionbasedsorting 4.Mergingbasedsorting 5.Radixsorting 6.PerformancecomparisonandanalysisProf.Q.WangPrinciple：每步將一個待排序的記錄按其關(guān)鍵字大小插入到前面已排序表中的適當(dāng)位置，直到全部插入完為止。CategoriesStraightinsertingbasedsorting(直接插入排序)Dichotomyinsertingbasedsorting(折半插入排序)Twowayinsertingbasedsorting(二路插入排序)Shellsorting(希爾排序)9.2InsertionbasedsortingProf.Q.WangvoidinsertSort(SortObject*pvector) /*按遞增序進(jìn)行直接插入排序*/{ inti,j; RecordNode temp; for(i=2;i<=pvector->n;i++) {

temp=pvector->record[i]; j=i-1; while((temp.key<pvector->record[j].key)&&(j>=1)) { pvector->record[j+1]=pvector->record[j]; j--; }

if(j!=(i-1))pvector->record[j+1]=temp; }}9.2.1DirectinsertingbasedsortingCompareMovementProf.Q.Wang各趟排序結(jié)果21254925*16080123456012345621254925*160825i=2觀察哨ExampleOriginaldataProf.Q.Wang21254925*1608i=425*012345621254925*1608i=516012345621254925*160849i=30123456Prof.Q.Wang21254925*1608完成12345621254925*1608i=6080123456Prof.Q.WangAlgorithmanalysis空間效率：只需要一個記錄的輔助空間。時間效率： 基本操作有：比較和移動記錄 比較記錄的次數(shù)為：最小：n-1次； 最大：n(n-1)/2次 移動記錄的次數(shù)： 最小：2n

最大：(n+2)(n-1)/2

平均情況：比較O(n2)，移動O(n2)直接插入排序是一種穩(wěn)定的排序方法。Prof.Q.Wang9.2.2Dichotomyinsertingbasedsorting由于插入排序的基本操作是在有序表中進(jìn)行查找和插入，而查找的過程是可以用折半查找來實(shí)現(xiàn)的。由此實(shí)現(xiàn)的排序稱為折半插入排序。性能分析：空間效率：同上時間效率：僅減少了比較次數(shù)，移動記錄次數(shù)不變。折半插入排序是一個穩(wěn)定的排序方法。Prof.Q.WangvoidbinSort(SortObject*pvector)/*按遞增序進(jìn)行二分法插入排序*/{ inti,j,left,mid,right; RecordNodetemp;

for(i=1;i<pvector->n;i++) { temp=pvector->record[i]; left=0;right=i–1; while(left<=right) { mid=(left+right)/2; if(temp.key<pvector->record[mid].key) right=mid-1; else left=mid+1; } for(j=i-1;j>=left;j--) pvector->record[j+1]=pvector->record[j]; if(left!=i)pvector->record[left]=temp; }}CompareProf.Q.Wang9.2.3Twowayinsertingbasedsorting2-路插入排序基本思想是：另設(shè)一個和pvector同類型的數(shù)組d，首先將pvector[1]賦值給d[1]，并將d[1]看成是在排好序的序列中處于中間位置的記錄，然后從pvector中第2個記錄起依次插入到d[1]之前或之后的有序序列中。2-路插入排序的例子設(shè)兩個指針first和final分別指示排序過程中得到的有序序列中的第一個記錄和最后一個記錄在d中的位置。Prof.Q.Wang初始關(guān)鍵字： 4938659776132749*i=1: (49)firstfinali=2: (49) (38)finalfirsti=3: (4965) (38)finalfirsti=4: (496597) (38)finalfirstProf.Q.Wangi=5: (49657697) (38)finalfirst初始關(guān)鍵字： 4938659776132749*i=6: (49657697) (1338)finalfirsti=7: (49657697) (132738)finalfirsti=8: (4949*657697132738)finalfirstProf.Q.WangAlgorithmanalysis在2-路插入排序中，移動記錄的次數(shù)約為n2/8。2-路插入排序需要n個輔助存儲空間。注意：pvector[1]若是待排序記錄中關(guān)鍵字最小或最大的記錄，2-路插入排序就退化為直接插入排序。QuickreviewInternalsoringConceptKeyelementsTimeSpaceStabilitybasicimprovedProf.Q.WangProf.Q.Wang

又稱“縮小增量排序”。從直接插入排序的分析可知，當(dāng)待排記錄序列為“正序”時，其時間復(fù)雜度可提高到O(n)，由此可設(shè)想，若待排記錄序列按關(guān)鍵字“基本有序”時，直接插入排序的效率也比較高；另外，由于直接插入排序算法簡單，在n值很小時效率也較高。因此從這兩點(diǎn)出發(fā)設(shè)計一種算法就可以提高排序的效率。先將整個待排記錄序列分割成若干個子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序“時，再對全體記錄進(jìn)行一次直接插入排序，就可以完成整個的排序工作。

9.2.4ShellsortingProf.Q.Wang

對于希爾排序，當(dāng)增量序列是形如2i3j且小于n時，平均比較次數(shù)為n(log2n)2。但應(yīng)注意使增量序列中的值沒有除1以外的公因子，并且最后一個增量必須等于1。例如：待排序序列為49,38,65,97,13,76,27,49*，請用Shell排序法排序。原始序列4938659713762749*1.d=4

2.d=213382749*49766597

3.d=113382749*49766597

排序結(jié)果13273849*49657697Prof.Q.Wang希爾排序的一個特點(diǎn)是：子序列的構(gòu)成不是簡單地“逐段分割”，而是將相隔某個增量的記錄組成一個子序列。voidshellSort(SortObject*pvector,intd)/*按遞增序進(jìn)行Shell排序*/{inti,j,increment;RecordNodetemp;for(increment=d;increment>0;increment/=2){ for(i=increment;i<pvector->n;i++){temp=pvector->record[i];j=i-increment;while(j>=0&&temp.key<pvector->record[j].key){ pvector->record[j+increment]=pvector->record[j]; j-=increment;}pvector->record[j+increment]=temp;}}}Back希爾排序不穩(wěn)定。Prof.Q.Wang9.3SwapbasedsortingPrinciple:兩兩比較待排序?qū)ο蟮年P(guān)鍵碼k[i]和K[i+1]，如果發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之，直到所有對象都排好序?yàn)橹埂ategoriesBubblesorting(冒泡排序)Quicksorting(快速排序)Prof.Q.WangvoidbubbleSort(SortObject*pvector){inti,j,noswap;RecordNodetemp;for(i=0;i<pvector->n-1;i++){ /*做n-1次起泡*/

noswap=TRUE;for(j=0;j<pvector->n-i-1;j++)if(pvector->record[j+1].key<pvector->record[j].key){temp=pvector->record[j];pvector->record[j]=pvector->record[j+1];pvector->record[j+1]=temp;

noswap=FALSE;}

if(noswap)break;}}9.3.1BubblesortingCompare&SwapProf.Q.WangAlgorithmanalysis在對象的初始排列已經(jīng)按關(guān)鍵碼從小到大排好序時，此算法只執(zhí)行一趟起泡，做n-1次關(guān)鍵碼比較，不移動對象。這是最好的情形。最壞的情形是算法執(zhí)行了n-1趟起泡，第i

趟做了n-i

次關(guān)鍵碼比較，執(zhí)行了n-i

次對象交換。這樣在最壞情形下總的關(guān)鍵碼比較次數(shù)KCN和對象移動次數(shù)RMN為：Prof.Q.WangAlgorithmanalysis冒泡排序需要一個附加對象以實(shí)現(xiàn)對象值的對換。冒泡排序是一個穩(wěn)定的排序方法。Prof.Q.Wang9.3.2QuicksortingPrinciple:通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。Prof.Q.WangQuickSortingalgorithm快速排序過程：首先任意選取一個記錄作為樞軸(或支點(diǎn),Pivot)，然后按下述原則重新排列其一記錄：將所有關(guān)鍵字小于它的記錄都安置在它之前，將所有關(guān)鍵字大于它的記錄安置在它之后。于是以該樞軸記錄所在的位置

i作分界線，將整個序列分成兩個子序列。這個過程稱為一趟快速排序。然后分別對于兩個子序列作同樣的操作，重復(fù)這個過程，直到子序列不可再分就完成了記錄的排序工作。Prof.Q.WangImplementationofquicksorting一趟快速排序的具體過程：附設(shè)兩個指針low和high，它們的初值分別是一個序列的第一個和最后一個記錄的位置，設(shè)樞軸記錄的關(guān)鍵字為pivotKey。首先從high所指位置起向前搜索直到第一個關(guān)鍵字小于pivotKey的記錄和樞軸記錄交換，然后從low所指位置起向后搜索，找到第一個關(guān)鍵字大于pivotKey的記錄和樞軸記錄互相交換，重復(fù)交替這兩步直到low=high為止。Prof.Q.WangPivotKey4938659776132749*2738659776134949*2738499776136549*2738139776496549*Example273813

76976549*49lowhighSwapProf.Q.Wang27381376976549*4913273849*6576974913273849*6576974913273849*65769749SortedresultProf.Q.WangTheessenceofquicksorting4938659776132749*Original13273849*657697494927769749*381365ResultProf.Q.Wang算法描述QuickSort(List){if(List的長度大于1){

將序列List劃分為兩個子序列LeftList和

RightList;

QuickSort(LeftList);

QuickSort(RightList);

將兩個子序列

LeftList和

RightList合并為 一個序列List;}}Prof.Q.WangvoidquickSort(SortObject*pvector,intl,intr) {inti,j;RecordNodetemp;if(l>=r)return;i=l;j=r;temp=pvector->record[i];while(i!=j){ while((pvector->record[j].key>=temp.key)&&(j>i))j--;if(i<j)pvector->record[i++]=pvector->record[j];while((pvector->record[i].key<=temp.key)&&(j>i))i++;if(i<j)pvector->record[j--]=pvector->record[i];}pvector->record[i]=temp;

quickSort(pvector,l,i-1);

quickSort(pvector,i+1,r);}用第一個對象作為基準(zhǔn)對象快速排序退化的例子

08

16212525*4908012345pivot初始

16212525*49

0816

212525*4921

081625

2525*49

081621

25*4925*

0816212549

0816212525*i=1i=2i=3i=4i=5Prof.Q.Wang快速排序的平均時間為Tavg(n)=knlnn，其中k為常數(shù)。經(jīng)驗(yàn)表明，在所有同數(shù)量級的排序方法中，快速排序是常數(shù)因子最小的，即其平均性能是最好的。但是，若初始記錄序列按關(guān)鍵字有序或基本有序時，快速排序?qū)⑼懟癁槊芭菖判?。改進(jìn)的方法是用“三者取中”的方法來選取樞軸記錄。經(jīng)驗(yàn)表明該方法可以有效地改善在最壞情況下的性能。但即使如此也不能使快速排序在待排記錄有序的情況下達(dá)到O(n)的時間復(fù)雜度。AlgorithmanalysisProf.Q.Wang修改劃分算法：在指針high增1和low減1的同時進(jìn)行冒泡操作，即在相鄰兩個記錄處于逆序時進(jìn)行互換。同時，在算法中附設(shè)兩個布爾型變量，分別指示low和high從兩端向中間的移動過程中是否進(jìn)行過交換記錄的操作。如果low的移動過程中沒有發(fā)生交換，則不需對低端子序列進(jìn)行排序；高端也類似。這樣可以進(jìn)一步改善平均性能。AlgorithmanalysisProf.Q.Wang對于快速排序，由于使用了遞歸方法，所以需要附加棧空間，當(dāng)每一趟排序都將記錄均勻地分成兩部分時，棧的最大深度為

log2n

+1，但如果每趟排序后樞軸位置偏向一端，則為最壞情況，此時的棧的最大深度為n。因此可以改進(jìn)算法，使在一趟排序之后比較分割所得兩部分的長度，且先對長度短的子序列中的記錄進(jìn)行快速排序，則棧的最大深度可降為(logn)。AlgorithmanalysisProf.Q.WangKeyfeaturesofquicksorting函數(shù)quicksort的平均計算時間也是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就平均計算時間而言，快速排序是我們所討論的所有內(nèi)部排序方法中最好的一個。快速排序是遞歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)。最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為

log2(n+1)

。因此，快速排序的存儲開銷為O(log2n)。Prof.Q.WangKeyfeaturesofquicksorting快速排序是一種不穩(wěn)定的排序方法。對于n較大的平均情況而言，快速排序是“快速”的，但是當(dāng)n

很小時，這種排序方法往往比其它簡單排序方法還要慢。BackProf.Q.Wang9.4SelectionbasedsortingPrinciple:每一趟在n-i+1個記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個記錄。CategoriesSimpleselectionbasedsorting(簡單選擇排序)Treeselectionbasedsorting(樹型選擇排序)Heapsorting(堆排序)Prof.Q.WangvoidselectSort(SortObject*pvector)/*按遞增序進(jìn)行直接選擇排序*/{inti,j,k;RecordNodetemp;for(i=0;i<pvector->n-1;i++){k=i;for(j=i+1;j<pvector->n;j++)if(pvector->record[j].key<pvector->record[k].key)

k=j;if(k!=i){temp=pvector->record[i];pvector->record[i]=pvector->record[k];pvector->record[k]=temp;}}}9.4.1SimpleselectionbasedsortingCompare&SelectProf.Q.Wang算法分析直接選擇排序的時間復(fù)雜度：移動：最好時：0

最壞時：3(n-1)比較：n(n-1)/2總的時間復(fù)雜度：O(n2)穩(wěn)定性：不穩(wěn)定

(why?)Prof.Q.Wang9.4.2Treeselectionbasedsorting樹形選擇排序(TreeSelectionSorting)，又稱錦標(biāo)賽排序(TournamentSorting)。方法：首先對n個記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在

n/2個較小者之間再進(jìn)行兩兩比較，如此重復(fù)直到選出最小關(guān)鍵字的記錄為止。然后對剩下的記錄作同樣的操作，選出具有次小關(guān)鍵字的記錄。這個過程可以用一個完全二叉樹來表示。如下圖。每次兩兩比較的結(jié)果是把關(guān)鍵碼小者作為優(yōu)勝者上升到雙親結(jié)點(diǎn)，稱這種比賽樹為勝者樹。Prof.Q.Wang133813386513274938659776132788ExampleofTreeSelectionSortingExample如果n不是2的k次冪，則讓葉結(jié)點(diǎn)數(shù)補(bǔ)足到滿足2k-1<n

2k的2k個。葉結(jié)點(diǎn)上面一層的非葉結(jié)點(diǎn)是葉結(jié)點(diǎn)關(guān)鍵碼兩兩比較的結(jié)果。最頂層是樹的根。08Winner2108086325*2121254925*160863tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]

tree[15]tree[1]tree[2]tree[3]tree[4]tree[5]tree[6]tree[7]勝者樹的概念每次兩兩比較的結(jié)果是把關(guān)鍵碼小者作為優(yōu)勝者上升到雙親結(jié)點(diǎn)，稱這種比賽樹為勝者樹。位于最底層的葉結(jié)點(diǎn)叫做勝者樹的外結(jié)點(diǎn)，非葉結(jié)點(diǎn)稱為勝者樹的內(nèi)結(jié)點(diǎn)。每個結(jié)點(diǎn)除了存放對象的關(guān)鍵碼data外，還存放了此對象是否要參選的標(biāo)志active

和此對象在滿二叉樹中的序號index。勝者樹最頂層是樹的根，表示最后選擇出來的具有最小關(guān)鍵碼的對象。08Winner(勝者)2108086325*2121254925*160863

形成初始勝者樹（最小關(guān)鍵碼上升到根）a[1]關(guān)鍵碼比較次數(shù):6Step1:tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]

tree[15]16Winner(勝者)2116166325*2121254925*1663輸出冠軍并調(diào)整勝者樹后樹的狀態(tài)a[2]關(guān)鍵碼比較次數(shù):2Step2:tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]

tree[15]21Winner(勝者)21636325*2121254925*63輸出亞軍并調(diào)整勝者樹后樹的狀態(tài)a[3]關(guān)鍵碼比較次數(shù):2Step3:tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]

tree[15]25Winner(勝者)25636325*25254925*63輸出第三名并調(diào)整勝者樹后樹的狀態(tài)a[4]關(guān)鍵碼比較次數(shù):2Step4:tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]

tree[15]25*Winner(勝者)25*636325*4925*63輸出第四名并調(diào)整勝者樹后樹的狀態(tài)a[5]關(guān)鍵碼比較次數(shù):2Step5:tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]

tree[15]49Winner(勝者)496363494963輸出第五名并調(diào)整勝者樹后樹的狀態(tài)a[6]關(guān)鍵碼比較次數(shù):2Step6:tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]

tree[15]63Winner(勝者)636363全部比賽結(jié)果輸出時樹的狀態(tài)a[7]關(guān)鍵碼比較次數(shù):2Step7:tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]

tree[15]勝者樹數(shù)據(jù)結(jié)點(diǎn)類的定義template<classType>classDataNode{public:Typedata;//數(shù)據(jù)值

intindex;//結(jié)點(diǎn)在滿二叉樹中順序號

intactive;//參選標(biāo)志：=1,參選,=0,不參選}錦標(biāo)賽排序的算法template<classType>voidTournamentSort(Type

a[],intn){DataNode<Type>*tree;

DataNode<Type>

item;

參考程序

int

bottomRowSize=PowerOfTwo(n);//乘冪值

int

TreeSize=2*bottomRowSize-1;//總結(jié)點(diǎn)個數(shù)

int

loadindex=bottomRowSize-1;//內(nèi)結(jié)點(diǎn)個數(shù)

tree=new

DataNode<Type>[TreeSize];

int

j=0;//從

a向勝者樹外結(jié)點(diǎn)復(fù)制數(shù)據(jù)

for(inti=loadindex;

i<TreeSize;i++){

tree[i].index=i;

if(j<n)

{

tree[i].active=1;tree[i].data=a[j++];} else

tree[i].active=0;

}Constructtree

i=loadindex; //進(jìn)行初始比較選擇最小的項(xiàng)

while(i){

j=i;

while(j<2*i){

if(!tree[j+1].active||

tree[j].data<=tree[j+1].data)

tree[(j-1)/2]=tree[j]; //勝者送入雙親

else

tree[(j-1)/2]=tree[j+1];

j+=2;

}

i=(i-1)/2;//i退到雙親,直到i==0為止

}

for(i=0;

i<n-1;i++){ //處理其它n-1個數(shù)據(jù)

a[i]=tree[0].data; //送出最小數(shù)據(jù)

tree[tree[0].index].active=0;

//失去參選資格

UpdateTree(tree,tree[0].index);//調(diào)整

}

a[n-1]=tree[0].data;}錦標(biāo)賽排序中的調(diào)整算法 template<classType>voidUpdateTree(DataNode<Type>*tree,inti){

if(i%2==0)

tree[(i-1)/2]=tree[i-1]; //i偶數(shù),對手左結(jié)點(diǎn)

else

tree[(i-1)/2]=tree[i+1]; //i奇數(shù),對手右結(jié)點(diǎn)

i=(i-1)/2; //向上調(diào)整

while(i){ //直到

i==0

if(i%2==0)j=i-1;

else

j=i+1;

if(!tree[i].active

||!tree[j].active)

if(tree[i].active)

tree[(i-1)/2]=tree[i]; //i可參選,i上

else

tree[(i-1)/2]=tree[j]; //否則,j上

else //兩方都可參選

if(tree[i].data<tree[j].data)

tree[(i-1)/2]=tree[i]; //關(guān)鍵碼小者上

else

tree[(i-1)/2]=tree[j];

i=(i-1)/2; //i上升到雙親

}}Prof.Q.WangAlgorithmanalysis錦標(biāo)賽排序構(gòu)成的樹是滿的完全二叉樹，其深度為

log2(n+1)

，其中n為待排序元素個數(shù)。除第一次選擇具有最小關(guān)鍵碼的對象需要進(jìn)行n-1次關(guān)鍵碼比較外，重構(gòu)勝者樹選擇具有次小、再次小關(guān)鍵碼對象所需的關(guān)鍵碼比較次數(shù)均為O(log2n)?？傟P(guān)鍵碼比較次數(shù)為O(nlog2n)。對象的移動次數(shù)不超過關(guān)鍵碼的比較次數(shù)，所以錦標(biāo)賽排序總的時間復(fù)雜度為O(nlog2n)。Prof.Q.Wang這種排序方法雖然減少了許多排序時間，但是使用了較多的附加存儲。如果有n個對象，必須使用至少2n-1個結(jié)點(diǎn)來存放勝者樹。最多需要找到滿足2k-1<n

2k的k，使用2*2k-1個結(jié)點(diǎn)。每個結(jié)點(diǎn)包括關(guān)鍵碼、對象序號和比較標(biāo)志三種信息。錦標(biāo)賽排序是一個穩(wěn)定的排序方法。Prof.Q.Wang9.4.3Heapsorting選擇排序的主要操作是比較，要提高它的速度必須減少比較的次數(shù)。而實(shí)際上如果能利用以前的比較結(jié)果則可以提高排序速度。Prof.Q.Wang

錦標(biāo)賽排序的時間復(fù)雜度為O(nlog2n)。缺點(diǎn)是使用了較多的輔助空間，并且和“最大值”進(jìn)行了多余的比較。1964年Willioms提出了堆排序。

堆的定義：n個元素的序列{k1,k2,…,kn}當(dāng)且僅當(dāng)滿足如下關(guān)系時，稱之為堆。

ki

k2i

ki

k2i

ki

k2i+1

ki

k2i+1

或(i=1,2,…,n/2)DefinitionofHeapProf.Q.Wang

若將和此序列對應(yīng)的一維數(shù)組看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結(jié)點(diǎn)的值均不大于（或不小于）其左右孩子結(jié)點(diǎn)的值。由此，若序列{k1,k2,…,kn}

是堆，則堆頂元素必為序列中n個元素的最小值（或最大值）。如果在輸出堆頂?shù)淖钚≈岛?，使得剩余n-1個元素的序列重新又建成一個堆，則得到次小值。反復(fù)執(zhí)行此過程便能得到所有記錄的有序序列，這個過程稱為堆排序。HeapsortingProf.Q.Wang

現(xiàn)在需要研究兩個問題：（1）如何由一個無序序列建成一個堆；解決方案：自下而上調(diào)整

（2）如何在輸出堆頂元素后，調(diào)整剩余元素使之成為一個新的堆。解決方案：自上而下調(diào)整

堆排序的相關(guān)問題Prof.Q.WangMethod(1)

第2個問題：如何在輸出堆頂元素后，調(diào)整剩余元素使之成為一個新的堆。解決方案：自上而下調(diào)整在輸出堆頂元素后，用堆中最后一個元素替代，此時根結(jié)點(diǎn)的左右子樹均為堆，則僅需自上而下進(jìn)行調(diào)整即可。首先堆頂元素和其左右孩子的值比較，把最小的值（假設(shè)為左孩子結(jié)點(diǎn)）調(diào)到根結(jié)點(diǎn)的位置，由于左子樹的根結(jié)點(diǎn)發(fā)生了改變，因此需要對左子樹進(jìn)行上述一樣的調(diào)整，直至葉子結(jié)點(diǎn)。這個自堆頂至葉子的調(diào)整過程稱為“篩選”。Prof.Q.WangMethod(2)

第1個問題：如何由一個無序序列建成一個堆。解決方案：自下而上調(diào)整從一個無序序列建堆的過程就是一個反復(fù)“篩選”的過程。若將此無序序列看成是一個完全二叉樹，則最后一個非終端結(jié)點(diǎn)就是第

n/2個元素，因此篩選只需從第n/2個元素起，篩選到第1個元素（即堆頂元素）。自下向上逐步調(diào)整為最小堆將一組用數(shù)組存放的任意數(shù)據(jù)調(diào)整成堆i=4i=3i=3i=4自下向上逐步調(diào)整為最小堆堆的構(gòu)造（續(xù)）i=2i=2i=2自下向上逐步調(diào)整為最小堆堆的構(gòu)造（續(xù)）i=1i=1i=1自下向上逐步調(diào)整為最小堆i=1i=1最小堆的向上調(diào)整(插入新的數(shù)據(jù))堆排序舉例建立初始的最大堆212525*491608123456i212525*164908136542i21254925*1608初始關(guān)鍵碼集合21254925*1608i=2時的局部調(diào)整212525*491608123456i492525*16210813654221254925*160849252125*1608i=1時的局部調(diào)整形成最大堆i=1時的局部調(diào)整建立最大堆492525*211608123456082525*16214913654249252125*160808252125*1649交換1

號與6號對象,6號對象就位初始最大堆開始排序2525*082116491234561625*082521491365422525*210816491625*210825

49交換1

號與5號對象,5號對象就位從1號到5號重新調(diào)整為最大堆排序中25*1608212549123456081625*25214913654225*16210825

4908162125*

25

49交換1

號與4號對象,4號對象就位從1號到4號重新調(diào)整為最大堆排序中211625*082549123456081625*25214913654221160825*

25

49081621

25*

25

49交換1

號與3號對象,3號對象就位從1號到3號重新調(diào)整為最大堆排序中160825*212549123456081625*25214913654216082125*

25

490816

21

25*

25

49交換1

號與2號對象,2號對象就位從1號到2號重新調(diào)整為最大堆排序中排序結(jié)束Prof.Q.Wang#defineleftChild(i)2*(i)voidsift(SortObject*pvector,inti,intn){intchild;RecordNodetemp;

temp=pvector->record[i];child=leftChild(i);while(child<=n){if((child<=n-1)&&(pvector->record[child].key <pvector->record[child+1].key))child++;if(temp.key<pvector->record[child].key){pvector->record[i]=pvector->record[child];i=child;child=leftChild(i);}elsebreak;}pvector->record[i]=temp;}Prof.Q.WangvoidheapSort(SortObject*pvector) { inti,n; RecordNode temp; n=pvector->n; for(i=n/2;i>=1;i--)

sift(pvector,i,n); for(i=n;i>1;i--) { temp=pvector->record[1]; pvector->record[1]=pvector->record[i]; pvector->record[i]=temp;

sift(pvector,1,i-1); }}堆排序適用于n值較大的情況。其比較次數(shù)為：<2n(

log2n

).在最壞的情況下，時間復(fù)雜度也是O(nlogn)。且僅需一個記錄大小的輔助空間。Prof.Q.WangAlgorithmanalysis堆排序的時間復(fù)雜性為O(nlog2n)。該算法的附加存儲主要是在第二個for循環(huán)中用來執(zhí)行對象交換時所用的一個臨時對象。因此，該算法的空間復(fù)雜性為O(1)。堆排序是一個不穩(wěn)定的排序方法。BackProf.Q.WangQuickreviewSelectionbasedsortingTournamentsortingHeapsortingMergingbasedsortingRecursivealgorithm…Prof.Q.Wang9.5Mergingsorting歸并的含義：歸并是將兩個或兩個以上的有序表合并成一個有序表。2－路歸并排序:假設(shè)初始的序列含有n個記錄，可以看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到

n/2個長度為2或1的有序子序列；再兩兩歸并，如此重復(fù)直到得到一個長度為n的有序序列為止。算法如下：Prof.Q.Wang例題∶初始序列為25,57,48,37,12,82,75,29,16，請用2-路歸并排序法排序。初始排序碼 25

57

48

37

12

82

75

29

16 \/ \/ \/ \/ │第一趟歸并后 2557

3748

1282

2975

16 \/ \ / │第二趟歸并后 2537 4857

1229 7582

16 \/ │第三趟歸并后 1225 2937 4857 7582

16 \ /第四趟歸并后 1216 2529 3748 5775 82排序后的結(jié)果為： 12,16,25,29,37,48,57,75,82迭代的歸并排序算法212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293len=1len=2len=4len=8len=16Prof.Q.Wang(兩路)歸并排序的主算法template<classType>voidMergeSort(datalist<Type>&list){//按對象關(guān)鍵碼非遞減的順序?qū)Ρ韑ist中對象排序

datalist<Type>&tempList(list.MaxSize);

intlen=1;

while(len<list.CurrentSize){

MergePass(list,tempList,len);len*=2;

MergePass(tempList,list,len);len*=2;

}

delete[]tempList;}Prof.Q.Wang//有序序列的合并voidmerge(RecordNode*r,RecordNode*r1,intlow,intm,inthigh){ inti,j,k; i=low; j=m+1;k=low; while((i<=m)&&(j<=high)) { if(r[i].key<=r[j].key) r1[k++]=r[i++]; else r1[k++]=r[j++]; } while(i<=m) r1[k++]=r[i++]; while(j<=high) r1[k++]=r[j++];}Prof.Q.Wang//一趟歸并voidmergePass(RecordNoder[],RecordNoder1[],intn,intlength){ inti,j; i=0; while(i+2*length-1<n) {

merge(r,r1,i,i+length-1,i+2*length-1); i+=2*length; } if(i+length-1<n-1)

merge(r,r1,i,i+length-1,n-1); else for(j=i;j<n;j++) r1[j]=r[j];}Prof.Q.Wang//2-路歸并排序voidmergeSort(SortObject*pvector){ RecordNode record[MAXNUM]; intlength; length=1; while(length<pvector->n) {

mergePass(pvector->record,record,pvector->n,length); length*=2;

mergePass(record,r->record,pvector->n,length); length*=2; }}遞歸的表歸并排序與快速排序類似，歸并排序也可以利用劃分為子序列的方法遞歸實(shí)現(xiàn)。在遞歸的歸并排序方法中，首先要把整個待排序序列劃分為兩個長度大致相等的部分，分別稱之為左子表和右子表。對這些子表分別遞歸地進(jìn)行排序，然后再把排好序的兩個子表進(jìn)行歸并。圖示：待排序?qū)ο笮蛄械年P(guān)鍵碼為{21,25,49,25*,16,08}，先是進(jìn)行子表劃分，待到子表中只有一個對象時遞歸到底。再是實(shí)施歸并，逐步退出遞歸調(diào)用的過程。歸并時采用靜態(tài)鏈表的存儲表示，可以得到一種有效的歸并排序算法。21254925*1608212549

25*16082125492549

2125*1608

25*160821254925*1608

25*1608212549

1608

25*2549

212125*16084925遞歸回退靜態(tài)鏈表的兩路歸并算法template<classType>int

ListMerge(staticlinklist<Type>&

list,constint

start1,constint

start2){

int

k=0,i=start1,j=start2;

while(i

&&

j) if(list.Vector[i].getKey()<=list.Vector[j].getKey()

){

list.Vector[k].setLink(i);

k=i;

i=list.Vector[i].getLink();

}else{

list.Vector[k].setLink(j);

k=j;

j=list.Vector[j].getLink();

}

if(!i)list.Vector[k].setLink(j);

else

list.Vector[k].setLink(i);

return

list.Vector[0].getLink();}Prof.Q.WangProf.Q.WangAlgorithmanalysis時間復(fù)雜度：O(nlog2n)空間復(fù)雜度：和待排記錄等量的空間特點(diǎn)：是一種穩(wěn)定的排序方法。但是，一般情況下很少用于內(nèi)部排序。BackQuickreviewSelectionbasedsortingTournamentsortingHeapsortingMergingbasedsortingRecursivealgorithm…Prof.Q.WangProf.Q.Wang9.6Radixsorting基數(shù)排序是一種與前面所述的排序法完全不同的一類排序法。前面排序法的基本操作是比較和移動記錄?；鶖?shù)排序則是一種借助于多關(guān)鍵字排序思想對單邏輯關(guān)鍵字進(jìn)行排序的方法，不需要進(jìn)行關(guān)鍵字的比較。Prof.Q.WangMulti-keywordsorting

什么是多關(guān)鍵字排序？以撲克牌為例，有花色和點(diǎn)數(shù)兩種關(guān)鍵字。

ClubDiamondHeartSpadeProf.Q.Wang問題Prof.Q.WangSolution(1)Prof.Q.WangSolution(2)Prof.Q.WangMulti-keywordsorting

一般情況下假設(shè)有n個記錄的序列{R1,R2,…,Rn}，且每個記錄Ri中含有d個關(guān)鍵字(Ki0,Ki1,…,Kid-1)，在該序列對關(guān)鍵字有序是指：對應(yīng)序列中任意兩個記錄Ri和Rj（1≤

i<j

≤

n)都滿足下列關(guān)系：

(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)其中K0稱為最主位關(guān)鍵字，Kd-1稱為最次位關(guān)鍵字。Prof.Q.Wang

通常有兩種方法：第一種方法是先對最主位關(guān)鍵字K0進(jìn)行排序，然后分別就每個子序列對關(guān)鍵字K1進(jìn)行排序，直到最后分別就每個子序列對Kd-1進(jìn)行排序，最后將所有子序列一次聯(lián)接在一起成為一個有序序列。這種方法稱為最高位優(yōu)先法(MostSignificantDigitFirst)；第二種方法是從最次位關(guān)鍵字Kd-1開始進(jìn)行排序，稱為最低位優(yōu)先法

(LeastSignificantDigitFirst)。兩種方法的特點(diǎn)：MSD算法需要逐層分成若干個子序列，而LSD算法進(jìn)行排序時，不必分成子序列，但對Ki(0≤

i

≤

d-1)進(jìn)行排序時，只能用穩(wěn)定的排序方法。Prof.Q.Wang

鏈?zhǔn)交鶖?shù)排序：基數(shù)排序是借助“分配”和“收集”兩種基本操作對單邏輯關(guān)鍵字進(jìn)行排序的一種內(nèi)部排序方法。有的邏輯關(guān)鍵字可以看成是若干個關(guān)鍵字復(fù)合而成的。例如數(shù)值和字符串。首先以靜態(tài)鏈表存儲n個待排記錄，并令表頭指針指向第一個記錄，如圖所示。

p→614→738→921→485→637→101→215→530→790→306

第一趟分配對最低數(shù)位關(guān)鍵字進(jìn)行，改變記錄指針值將鏈表中的記錄分配至10個鏈隊(duì)列中去，每個隊(duì)列中的記錄關(guān)鍵字的個位數(shù)相等；第一趟收集是改變所有非空隊(duì)列的隊(duì)尾的指針域，令其指向下一個非空隊(duì)列的隊(duì)頭記錄，重新將10個隊(duì)列中的記錄鏈成一個鏈表；第二趟分配和收集是針對十位數(shù)位進(jìn)行的，過程和個位數(shù)位相同。其他位數(shù)一樣。例子和算法如下：基數(shù)排序的“分配”與“收集”過程614921485637738101215530