0-1開(kāi)課

數(shù)據(jù)結(jié)構(gòu)與算法DATASTRUCTURE&ALGORITHM天津理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院第九章排序1基本概念2插入排序3交換排序4選擇排序5歸并排序6基數(shù)排序7外排序9.1排序的基本概念排序的定義排序的基本概念排序算法的性能排序的定義女李爽0005女齊梅0004女劉楠0003男張亮0002男王剛0001性別姓名職工號(hào)5635573548年齡1982.92003.71979.92003.71990.4工作時(shí)間排序是對(duì)線性結(jié)構(gòu)的一種操作排序：給定一組記錄的集合{r1,r2,…,rn}，其相應(yīng)的關(guān)鍵碼分別為{k1,k2,…,kn}，將這些記錄排列為{rs1,rs2,…,rsn}的序列，使得相應(yīng)的關(guān)鍵碼滿足ks1≤ks2≤…≤ksn（或ks1≥ks2≥…≥ksn）。數(shù)據(jù)元素、結(jié)點(diǎn)、頂點(diǎn)升序（非降序）降序（非升序）排序碼：排序的依據(jù)，簡(jiǎn)單起見(jiàn)，也稱關(guān)鍵碼。排序的數(shù)據(jù)模型是什么？排序的定義排序：給定一組記錄的集合{r1,r2,…,rn}，其相應(yīng)的關(guān)鍵碼分別為{k1,k2,…,kn}，將這些記錄排列為{rs1,rs2,…,rsn}的序列，使得相應(yīng)的關(guān)鍵碼滿足ks1≤ks2≤…≤ksn（或ks1≥ks2≥…≥ksn）。數(shù)據(jù)元素、結(jié)點(diǎn)、頂點(diǎn)升序（非降序）降序（非升序）排序碼：排序的依據(jù)，也稱關(guān)鍵碼。（1）進(jìn)行升序排序本章約定：（3）排序數(shù)據(jù)存為順序表，且下標(biāo)從1開(kāi)始（2）記錄只有一個(gè)排序碼正序、逆序正序：待排序序列中的記錄已按關(guān)鍵碼排好序。1234512345逆序（反序）：待排序序列中記錄的順序與排好序的順序相反。5432112345深刻理解趟的含義能夠更好地掌握排序方法的思想和過(guò)程趟：在排序過(guò)程中，將待排序的記錄序列掃描一遍稱為一趟。算法的穩(wěn)定性排序算法的穩(wěn)定性：假定在待排序的記錄序列中存在多個(gè)具有相同關(guān)鍵碼的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，則稱這種排序算法穩(wěn)定，否則稱為不穩(wěn)定。學(xué)號(hào)姓名高數(shù)英語(yǔ)語(yǔ)文0001王軍85880002李明64920003湯曉影8586………687278……學(xué)號(hào)姓名高數(shù)英語(yǔ)語(yǔ)文0001王軍64880002李明85920003湯曉影8586………687278……排序算法的穩(wěn)定性只是算法的一種屬性，且由具體算法決定排序的分類根據(jù)排序過(guò)程中所有記錄是否全部放在內(nèi)存中，排序方法分為：（1）內(nèi)排序：在排序的整個(gè)過(guò)程中，待排序的所有記錄全部放在內(nèi)存中（2）外排序：待排序的記錄個(gè)數(shù)較多，整個(gè)排序過(guò)程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果根據(jù)排序方法是否建立在關(guān)鍵碼比較的基礎(chǔ)上，排序方法分為：（1）基于比較：主要通過(guò)關(guān)鍵碼之間的比較和記錄的移動(dòng)實(shí)現(xiàn)（2）不基于比較：根據(jù)待排序數(shù)據(jù)的特點(diǎn)所采取的其他方法①插入排序；②交換排序；③選擇排序；④歸并排序直接插入排序希爾排序起泡排序快速排序簡(jiǎn)單選擇排序堆排序二路歸并遞歸算法二路歸并非遞歸算法—基數(shù)排序排序算法的性能（1）時(shí)間性能：排序算法在各種情況（最好、最壞、平均）下的時(shí)間復(fù)雜度。例如，基于比較的內(nèi)排序在排序過(guò)程中的基本操作：①比較：關(guān)鍵碼之間的比較；

②移動(dòng)：記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。（2）空間性能：排序過(guò)程中占用的輔助存儲(chǔ)空間。輔助存儲(chǔ)空間是除了存放待排序記錄占用的存儲(chǔ)空間之外，執(zhí)行算法所需要的其他存儲(chǔ)空間。（3）穩(wěn)定性：（4）簡(jiǎn)單性：如何衡量排序算法的性能？9.2插入排序(InsertSorting)直接插入排序的基本思想：依次將待排序序列中的每一個(gè)記錄插入到已排好序的序列中，直到全部記錄都排好序。運(yùn)行實(shí)例2420101812122420101812242010181224201018122420101812待排序序列第一趟排序結(jié)果第二趟排序結(jié)果第三趟排序結(jié)果第四趟排序結(jié)果算法描述242010181212待排序序列for(i=2;i<=n;i++){

}

插入第i個(gè)記錄，即第i趟直接插入排序；如何構(gòu)造初始的有序序列？將第1個(gè)記錄看成是初始有序序列，然后從第2個(gè)記錄起依次插入到有序序列中，直至將第n個(gè)記錄插入。解決方法：算法描述：直接插入排序在插入第i個(gè)記錄時(shí)，前面的i-1個(gè)記錄已經(jīng)排好序有序序列r1r2ri-1……無(wú)序序列rirnri+1……關(guān)鍵問(wèn)題如何將第i

個(gè)記錄插入到有序序列中的合適位置？用R[i]的關(guān)鍵字與R[i-1],R[i-2],…的關(guān)鍵字順序進(jìn)行比較，若比R[i]的關(guān)鍵字大，就后移一個(gè)位置，如此重復(fù)，直到找到適當(dāng)?shù)牟迦胛恢茫磳[i]插入。算法描述voidInsertSort(RecordTypeR[],intn){/*對(duì)待排序序列R[1..n]用直接插入方法排序，n為待排序列長(zhǎng)度*/inti,j;for(i=2;i<=n;i++)if(R[i].key<R[i-1].key)/*條件成立時(shí)，將R[i]插入有序表*/{R[0]=R[i];

/*R[0]作監(jiān)測(cè)哨兵*/ for(j=i-1;R[0].key<R[j].key;j--) R[j+1]=R[j];/*記錄后移*/R[j+1]=R[0]; /*將R[i]插入到適當(dāng)位置*/}}比較次數(shù)：n-1次移動(dòng)次數(shù)：2(n-1)次O(n)比較次數(shù)：次移動(dòng)次數(shù)：次O(n2)時(shí)間性能最好情況：正序最壞情況：逆序平均情況：隨機(jī)排列，O(n2)

暫存單元、監(jiān)視哨空間性能r[0]作用是什么？

空間性能：O(1)

穩(wěn)定性：穩(wěn)定改進(jìn)的著眼點(diǎn)（1）若待排序記錄按關(guān)鍵碼基本有序，直接插入排序的效率較高；（2）若待排序記錄數(shù)量

n

較小，直接插入排序的效率也很高。在待排序序列正序時(shí)，直接插入排序的時(shí)間性能是O(n)。當(dāng)待排序的記錄個(gè)數(shù)較多時(shí)，大量的比較和移動(dòng)操作使直接插入排序算法的效率降低。改進(jìn)的著眼點(diǎn)：待排序記錄數(shù)量n

較大、并不是按關(guān)鍵碼基本有序，怎么辦？SHELL排序如何分割待排序序列，才能使整個(gè)序列逐步向基本有序發(fā)展？希爾排序的基本思想：將待排序序列分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待序列基本有序時(shí)，對(duì)全體記錄進(jìn)行直接插入排序。不能是逐段分割，而是將相距某個(gè)增量的記錄組成一個(gè)子序列先將整個(gè)待排序記錄以d1為步長(zhǎng)分成若干子序列，把所有相隔為d1的記錄放在同一組內(nèi)；在每個(gè)分組內(nèi)進(jìn)行直接插入排序；在將整個(gè)待排序記錄序列以d2(d2<d1<n)為步長(zhǎng)重新分組和在每組內(nèi)進(jìn)行直接插入排序；重復(fù)上步，直至dt=1，即所有記錄放進(jìn)一個(gè)組中進(jìn)行直接插入排序舉例取d3=1三趟分組：13

4

4838

274955659776三趟排序：4132738484955657697

初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76取d1=5一趟分組：49

38

65

97

76

13

27

48

55

4二趟排序：13

4

48

38

27

49

55

65

97

76取d2=3二趟分組：13

27

48

55

4

49

38

65

97

76關(guān)鍵問(wèn)題（1）希爾最早提出的方法是，且增量序列互質(zhì)（2）后來(lái)knuth提出取di+1=

di-1

/3

顯然最后一個(gè)增量必須等于1——縮小增量排序如何分割待排序序列，才能使整個(gè)序列逐步向基本有序發(fā)展？希爾排序的特點(diǎn)：在shell排序初始時(shí)，步長(zhǎng)d值較大，分組較多，每組內(nèi)記錄數(shù)較少，在每組內(nèi)進(jìn)行直接插入排序速度較快；并且對(duì)整個(gè)序列而言，關(guān)鍵字較小記錄呈跳躍式前移。隨著排序進(jìn)展，d值逐漸變小，每組內(nèi)記錄數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，所以在每組內(nèi)進(jìn)行直接插入排序速度仍然很快。時(shí)空性能（1）希爾排序的時(shí)間性能取決于增量序列，復(fù)雜的數(shù)學(xué)問(wèn)題；（2）研究表明，希爾排序的時(shí)間性能在O(n2)和O(nlog2n)之間；希爾排序是平均時(shí)間性能好于O(n2)的第一批算法之一（1959年）（3）如果選定合適的增量序列，希爾排序的時(shí)間性能可以達(dá)到O(n1.25)

。

時(shí)間性能：O(n2)~

O(nlog2n)

空間性能：O(1)——暫存單元

穩(wěn)定性：不穩(wěn)定9.3交換排序(ExchangeSort)無(wú)序區(qū)r1r2ri-1…有序區(qū)rirnri+1…反序則交換起泡排序的基本思想：兩兩比較相鄰記錄，如果反序則交換，直到?jīng)]有反序的記錄為止。運(yùn)行實(shí)例2420101812待排序序列第一趟排序結(jié)果第二趟排序結(jié)果第三趟排序結(jié)果1210201824241012182024101218208888一趟起泡排序沒(méi)有記錄交換，則結(jié)束排序過(guò)程

設(shè)置變量exchange記載交換，一趟排序中若無(wú)交換法傷，則排序結(jié)束。解決方法：基本過(guò)程將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類推，直至第n-1個(gè)記錄和第n個(gè)記錄比較為止——第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄上。對(duì)前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個(gè)記錄位置。重復(fù)上述過(guò)程，直到“在一趟排序過(guò)程中沒(méi)有進(jìn)行過(guò)交換記錄的操作”為止。C實(shí)現(xiàn)voidBubbleSort(intr[],intn)/*r[0]用作交換的臨時(shí)單元*/{ inti,j,exchange=1;for(i=n;i>1&&exchange;i--){

}}

exchange=0；

for(j=1;j<i;j++)

{}if(r[j].key>r[j+1].key){r[0]=r[j];r[j]=r[j+1];r[j+1]=r[0];

exchange=1；/*做“發(fā)生了交換”標(biāo)志*/}比較次數(shù)：n-1次移動(dòng)次數(shù)：0次O(n)O(n2)比較次數(shù)：

次移動(dòng)次數(shù)：次時(shí)間性能最好情況：正序最壞情況：逆序平均情況：隨機(jī)排列，O(n2)空間性能

暫存單元r[0]作用是什么？

空間性能：O(1)

穩(wěn)定性：穩(wěn)定改進(jìn)的著眼點(diǎn)5143245352551記錄的比較在相鄰單元中進(jìn)行每次交換只能右移一個(gè)單元總的比較次數(shù)和移動(dòng)次數(shù)較多較大記錄從前面直接移到后面，較小記錄從后面直接移到前面？快速排序均≤ri'r1'ri-1'…ri'rn'ri+1'…r1ri-1…rirnri+1…均≥ri'基本思想：選一個(gè)樞軸值，將待排序記錄劃分成兩部分，左側(cè)記錄均小于或等于樞軸值，右側(cè)記錄均大于或等于樞軸值，然后分別對(duì)這兩部分重復(fù)上述過(guò)程，直到整個(gè)序列有序。10283216242030待排序序列第一趟排序結(jié)果第二趟排序結(jié)果第三趟排序結(jié)果102832162420301028321620301028322010283216242030最終排序結(jié)果運(yùn)行實(shí)例關(guān)鍵問(wèn)題決定兩個(gè)子序列的長(zhǎng)度決定排序的時(shí)間性能（1）第一個(gè)記錄；（2）隨機(jī)選取；（3）比較三個(gè)記錄取值居中者；簡(jiǎn)單起見(jiàn)，取第一個(gè)記錄作為軸值10283216242030待排序序列10283216242030一次劃分結(jié)果解決方法：如何選擇軸值——比較的基準(zhǔn)？選取不同軸值有什么后果?關(guān)鍵問(wèn)題10283216242030待排序序列10283216242030一次劃分結(jié)果記錄的比較和移動(dòng)從兩端向中間進(jìn)行較小的記錄一次就能從后面移到前面（較大的記錄？）減少了總的比較次數(shù)和移動(dòng)次數(shù)如何實(shí)現(xiàn)一次劃分——較大的記錄移到后面，較小記錄移到前面？運(yùn)行實(shí)例10283216242030待排序序列jij從后向前掃描直到r[j]<r[i]10283216242030ji交換r[j]和r[i]i++10283216242030待排序序列j從后向前掃描直到r[j]<r[i]10283216242030ji交換r[j]和r[i]i++i從前向后掃描直到r[j]<r[i]交換r[j]和r[i]j--10283216242030ji重復(fù)上述過(guò)程，直到i等于j運(yùn)行實(shí)例intPartition(RecordTypeR[],ints,intt){/*對(duì)R[[s..t]中元素進(jìn)行一次劃分（一趟排序），并返回樞軸記錄的位置*/inti=s,j=t;R[0]=R[i]; /*用區(qū)間的第一個(gè)記錄作為樞軸記錄，并暫存于R[0]中*/while(i<j){while(R[j].key>R[0].key&&i<j)j--;//自右向左掃描if(i<j){R[i]=R[j]; i++;}//將較小記錄交換到前面while(R[i].key<=R[0].key&&i<j)i++;//自左向右掃描if(i<j){R[j]=R[i];j--;}//將較大記錄交換到后面}R[i]=R[0]; /*樞軸記錄最后定位*/returni; /*返回樞軸位置*/}

算法描述關(guān)鍵問(wèn)題10283216242030待排序序列10283216242030遞歸執(zhí)行快速排序一次劃分結(jié)果voidQuickSort(intr[],intfirst,intend){

intpivot=Partition(r,first,end);QuickSort(r,first,pivot-1);QuickSort(r,pivot+1,end);}解決方法：算法描述：如何處理一次劃分得到的兩個(gè)待排序子序列？運(yùn)行實(shí)例10283216242030待排序序列第一趟排序結(jié)果第二趟排序結(jié)果10283216242030102832162030若待排序序列只有一個(gè)記錄，即待劃分區(qū)間長(zhǎng)度為1if(first==end)return;遞歸何時(shí)結(jié)束？解決方法：算法描述voidQuickSort(intr[],intfirst,intend){ }else{intpivot=Partition(r,first,end);QuickSort(r,first,pivot-1);QuickSort(r,pivot+1,end);}if(first==end)return;

/*區(qū)間長(zhǎng)度為1，遞歸結(jié)束*/O(nlog2n)排序趟數(shù)：log2n一趟排序：O(n)n個(gè)元素……

log2n

層n/2或n/2-1個(gè)元素n/2或n/2-1個(gè)元素劃分時(shí)間為O(n)時(shí)間性能最好情況：每次劃分的軸值均是中值排序趟數(shù)：n-1一趟排序：O(n)O(n2)O(nlog2n)n個(gè)元素n-1個(gè)元素n-2個(gè)元素┇n層劃分時(shí)間為O(n)對(duì)于n較大的平均情況而言，快速排序是“快速”的，但是當(dāng)n很小時(shí)，這種排序方法往往比其它簡(jiǎn)單排序方法還要慢。時(shí)間性能O(nlog2n)排序趟數(shù)：log2n一趟排序：O(n)最好情況：每次劃分的軸值均是中值最壞情況：正序、逆序平均情況：空間性能O(log2n)~O(n)一次劃分：O(1)遞歸深度：O(log2n)~O(n)

空間性能：

穩(wěn)定性：不穩(wěn)定改進(jìn)的著眼點(diǎn)有一種改進(jìn)辦法：取每個(gè)待排序?qū)ο笮蛄械牡谝粋€(gè)對(duì)象、最后一個(gè)對(duì)象和位置接近正中的3個(gè)對(duì)象，取其關(guān)鍵字居中者作為基準(zhǔn)對(duì)象。改進(jìn)的著眼點(diǎn)：若能更合理地選擇基準(zhǔn)對(duì)象，使得每次劃分所得的兩個(gè)子序列中的對(duì)象個(gè)數(shù)盡可能地接近，可以加速排序速度，但是由于對(duì)象初始排列次序是隨機(jī)的，這個(gè)要求很難辦到。9.4選擇排序(SelectionSort)有序區(qū)無(wú)序區(qū)minr1ri-1…rirn……r1ri-1…ri'ri+1rn…簡(jiǎn)單選擇排序的基本思想：第

i

趟（1≤i≤n-1）排序在待排序序列r[i]～r[n]

中選取最小記錄，并和第

i個(gè)記錄交換。運(yùn)行實(shí)例2420101812待排序序列第一趟排序結(jié)果第二趟排序結(jié)果第三趟排序結(jié)果第四趟排序結(jié)果1012242018122420181018241220102018241210關(guān)鍵問(wèn)題for(i=1;i<n;i++){

}

第i趟簡(jiǎn)單選擇排序；n-1趟有序區(qū)無(wú)序區(qū)minr1ri-1…rirn……簡(jiǎn)單選擇排序進(jìn)行多少趟？算法描述：（1）在r[i]~r[n]中找最小值（2）將最小記錄與r[i]交換

index=i; for(j=i+1;j<=n;j++)if(r[j].key<r[index].key)index=j;

if(index!=i){

交換r[i]和r[index];}有序區(qū)無(wú)序區(qū)minr1ri-1…rirn……關(guān)鍵問(wèn)題第i趟簡(jiǎn)單選擇排序完成什么工作？算法描述：算法描述voidSelectSort(RecordTypeR[],intn){/*功能：對(duì)待排序序列R[1..n]采用簡(jiǎn)單選擇排序，n為待排序列長(zhǎng)度*/inti,j,k;for(i=1;i<n;i++)//第i趟排序(1≤i≤n){k=i; //每一趟均設(shè)第i個(gè)記錄（無(wú)序區(qū)第一個(gè)記錄）關(guān)鍵字最小for(j=i+1;j<=n;j++)/*在當(dāng)前無(wú)序區(qū)中選key最小的記錄R[k]*/if(R[j].key<R[k].key)k=j;/*k記下目前找到的最小關(guān)鍵字所在的位置*/if(k!=i)//如果k不是無(wú)序區(qū)第一個(gè)記錄，交換R[i]和R[k]{R[0]=R[i]; //R[0]作暫存單元R[i]=R[k];R[k]=R[0];}}}時(shí)間性能最壞情況：3(n-1)次

空間性能：O(1)O(n2)比較次數(shù)：

移動(dòng)次數(shù)：最好、最壞、平均情況：O(n2)

穩(wěn)定性：不穩(wěn)定最好情況：0次改進(jìn)的著眼點(diǎn)對(duì)無(wú)序序列掃描一趟（n-1次比較）只做了一件事——找最小值利用每趟比較后的結(jié)果查找最小值的同時(shí)找出并保存較小值減少后面選擇所用的比較次數(shù)提高整個(gè)排序的效率缺點(diǎn)：簡(jiǎn)單選擇排序的時(shí)間主要耗費(fèi)在哪了呢？?jī)?yōu)點(diǎn)：移動(dòng)次數(shù)較少，最壞情況O(n)改進(jìn)的著眼點(diǎn)：利用簡(jiǎn)單選擇排序的思想，同時(shí)減少比較次數(shù)堆的定義堆的定義：n個(gè)元素的序列(R1,R2,…Rn),對(duì)應(yīng)的關(guān)鍵字序列為(k1,k2,……kn)，若此關(guān)鍵字序列滿足下列關(guān)系，則稱該元素序列為堆。或(i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+150例(96,83,27,38,11,9）例(13,38,27,50,76,65,49,97)962791138831327384965765097可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中n個(gè)元素的最小值或最大值堆與序列的關(guān)系5038453236402018282812367541098

5038453236402820182812345678910順序存儲(chǔ)，以編號(hào)作為下標(biāo)堆采用順序存儲(chǔ)，則對(duì)應(yīng)一個(gè)（無(wú)序）序列基本思想r1…rirn…rn-i+1無(wú)序區(qū)，調(diào)整為大根堆有序區(qū)第i趟堆排序?qū)[1]~r[i]調(diào)整成大根堆，再將堆頂與r[i]交換堆排序的基本思想：首先將待排序序列構(gòu)造成一個(gè)大根堆，即選出了堆中所有記錄的最大者，將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個(gè)記錄。堆排序的思路：將整個(gè)待排序記錄分為有序區(qū)和無(wú)序區(qū)，初始時(shí)有序區(qū)為空，無(wú)序區(qū)為[R1,R2,…Rn]將無(wú)序區(qū)中記錄看作一棵順序存放的完全二叉樹上的結(jié)點(diǎn)，對(duì)該完全二叉樹按照堆定義要求進(jìn)行調(diào)整，使關(guān)鍵字最小(大)的記錄成為二叉樹的根(存在R[1]中)——初建堆將根結(jié)點(diǎn)中記錄與無(wú)序區(qū)中最后一個(gè)結(jié)點(diǎn)交換，并將無(wú)序區(qū)中最后一個(gè)記錄劃入有序區(qū)內(nèi)。無(wú)序區(qū)中記錄所構(gòu)成的二叉樹中，根結(jié)點(diǎn)的左、右子樹均滿足堆定義，故經(jīng)過(guò)適當(dāng)調(diào)整后可將無(wú)序區(qū)中記錄重建成堆，無(wú)序區(qū)當(dāng)前最小(大)成為根。——堆調(diào)整重復(fù)上述過(guò)程，直到無(wú)序區(qū)為空(即執(zhí)行n-1次)。基本思想關(guān)鍵問(wèn)題第二個(gè)問(wèn)題解決方法——篩選堆調(diào)整：在一棵完全二叉樹中，根結(jié)點(diǎn)的左右子樹均是堆，調(diào)整根結(jié)點(diǎn)使整個(gè)完全二叉樹成為一個(gè)堆的過(guò)程。方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過(guò)程為“堆篩選”堆排序需解決的兩個(gè)問(wèn)題：如何由一個(gè)無(wú)序序列建成一個(gè)堆？如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？關(guān)鍵問(wèn)題——堆調(diào)整13273849657650979749382765765013輸出：13273849502765769713輸出：13276549502738769713輸出：1327389727384965765013輸出：132749389765765013輸出：13堆調(diào)整——自上而下的篩選4965502738769713輸出：1327387665502738499713輸出：132738495065762738499713輸出：132738499765762738495013輸出：13273849506597762738495013輸出：13273849509765762738495013輸出：1327384950657665972738495013輸出：1327384950659765762738495013輸出：132738495065769765762738495013輸出：1327384950657697關(guān)鍵問(wèn)題——堆調(diào)整關(guān)鍵問(wèn)題——初建堆如何將一個(gè)無(wú)序序列建成一個(gè)大根堆——初始建堆？需要調(diào)整葉子結(jié)點(diǎn)嗎？分支結(jié)點(diǎn)中編號(hào)最大的是多少？解決辦法：從編號(hào)最大的分支結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行調(diào)整。因?yàn)闊o(wú)序序列所對(duì)應(yīng)完全二叉樹的最后一個(gè)非終端結(jié)點(diǎn)是第n/2個(gè)元素，所以篩選要從第n/2個(gè)元素開(kāi)始向上進(jìn)行。依次對(duì)無(wú)序序列的第n/2，n/2-1,…,直至第1個(gè)元素作為根的子樹進(jìn)行堆調(diào)整。初建堆舉例：含8個(gè)元素的待排序序列(49,38,65,97,76,13,27,50)49653827137697504965382713765097491338276576509749133827657650971327384965765097時(shí)間性能初始建堆：O(nlog2n)O(log2i)

最好、最壞、平均情況：O(nlog2n)1433*243*312

重建堆次數(shù)：n-1

重建堆：

空間性能：O(1)

穩(wěn)定性：不穩(wěn)定9.5歸并排序(MergeSort)歸并：是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。兩路歸并多路歸并歸并方法：設(shè)兩個(gè)有序表A和B的對(duì)象個(gè)數(shù)(表長(zhǎng))分別為

al

和

bl，變量i

和j

分別是表A和表B的當(dāng)前檢測(cè)指針。設(shè)表C是歸并后的新有序表，變量

k

是它的當(dāng)前存放指針。二路歸并排序基本思想：設(shè)初始待排序序列含有n個(gè)記錄，則可看成n個(gè)有序的子序列，每個(gè)子序列長(zhǎng)度為1。把這n個(gè)記錄兩兩二路歸并，得到

n/2個(gè)有序子序列，每個(gè)子序列的長(zhǎng)度為2或1(n為奇數(shù))。——一趟歸并排序再對(duì)n/2個(gè)有序子序列進(jìn)行兩兩二路歸并，……如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。運(yùn)行實(shí)例初始關(guān)鍵字：[49][38][65][97][76][13][27]一趟歸并后：[3849][6597][1376][27]二趟歸并后：[38496597][132776]三趟歸并后：[13273849657697]關(guān)鍵問(wèn)題smm+1tr[]voidMerge(intr[],ints,intm,intt){}如何表示兩個(gè)相鄰的子序列？一次合并：合并兩個(gè)相鄰的有序子序列算法描述：20254050152130smm+1tr[]ijk

r1[]15

while(i<=m&&j<=t)if(r[i].key<=r[j].key)r1[k++]=r[i++];elser1[k++]=r[j++];關(guān)鍵問(wèn)題一次合并：合并兩個(gè)相鄰的有序子序列合并可以就地進(jìn)行嗎？算法描述：20254050152130smm+1tr[]ijk

r1[]15202130

while(i<=m)r1[k++]=r[i++];while(j<=t)r1[k++]=r[j++];4050

關(guān)鍵問(wèn)題一次合并：合并兩個(gè)相鄰的有序子序列某個(gè)子序列比較完畢，做什么？算法描述：執(zhí)行過(guò)程25204015301018

202525154020301018

1540

103018待排序序列第一趟歸并結(jié)果第二趟歸并結(jié)果第三趟歸并結(jié)果

15202540

10183010151820253040構(gòu)造初始有序子序列h=1h=2h=4h=n子序列長(zhǎng)度有什么規(guī)律？在一趟歸并中有幾種情況？

2025

1540

103018

15202540hihhn-2h+1nwhile(i<=n-2*h+1)//i+2*h-1<=n{Merge(r,i,i+h-1,i+2*h-1);

i+=2*h;}hvoidMerge(intr[],ints,intm,intt)執(zhí)行過(guò)程設(shè)i

指向待歸并序列的第一個(gè)記錄，歸并的步長(zhǎng)是2h情況1：i≤n-2h+1，則相鄰兩個(gè)有序子序列的長(zhǎng)度均為h子序列長(zhǎng)度有什么規(guī)律？在一趟歸并中有幾種情況？算法描述：

2025

1540

103018hihn-h+1nif(i<n-h+1)//

i+h-1<n{

Merge(r,i,i+h-1,n);}<h

101830voidMerge(intr[],ints,intm,intt)執(zhí)行過(guò)程子序列長(zhǎng)度有什么規(guī)律？在一趟歸并中有幾種情況？設(shè)i

指向待歸并序列的第一個(gè)記錄，歸并的步長(zhǎng)是2h情況2：i＜n-h+1，則相鄰有序子序列一個(gè)長(zhǎng)度為h，另一個(gè)長(zhǎng)度小于h算法描述：

2025

1540

1030hihn-h+1n執(zhí)行過(guò)程子序列長(zhǎng)度有什么規(guī)律？在一趟歸并中有幾種情況？設(shè)i

指向待歸并序列的第一個(gè)記錄，歸并的步長(zhǎng)是2h情況3：i

≥

n-h+1，則表明只剩下一個(gè)有序子序列時(shí)間性能

2025

1540

103018第一趟歸并結(jié)果第二趟歸并結(jié)果

15202540

101830二路歸并執(zhí)行多少趟？每一趟的時(shí)間性能是多少？執(zhí)行趟數(shù)：log2n

每一趟：將記錄掃描一遍，O(n)最好、最壞、平均情況：O(nlog2n)空間性能

2025

20*40

103018第一趟歸并結(jié)果第二趟歸并結(jié)果

2020*2540

101830while(i<=m&&j<=t)if(r[i].key<=r[j].key)r1[k++]=r[i++];elser1[k++]=r[j++];空間性能：合并不能就地進(jìn)行，O(n)穩(wěn)定性：穩(wěn)定如果將判斷條件改為(r[i].key<r[j].key)，仍然是穩(wěn)定的嗎？9.6基數(shù)排序(RadixSort)基數(shù)：若任一記錄的關(guān)鍵字ki

可以看成由d個(gè)分量ki1,ki2,…kid組成，且每個(gè)分量的取值范圍相同：C1≤kij≤Crd

(1≤j≤d)，則稱rd為基數(shù)。十進(jìn)制數(shù)rd=10C1=0,C10=9小寫字母rd=26C1=‘a(chǎn)’,C26=‘z’基數(shù)排序是采用“分配”與“收集”的辦法，用對(duì)多關(guān)鍵字進(jìn)行排序的思想實(shí)現(xiàn)對(duì)單關(guān)鍵字進(jìn)行排序的方法。多關(guān)鍵字排序排序后形成的有序序列叫做詞典有序序列多關(guān)鍵字排序：以撲克牌排序?yàn)槔Ｃ繌垞淇伺朴袃蓚€(gè)“關(guān)鍵字”：花色和面值。其有序關(guān)系為：

花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A如果我們把所有撲克牌排成以下次序：

2,…,

A,

2,…,

A,

2,…,

A,

2,…,

A基數(shù)排序是按最低位優(yōu)先排序多關(guān)鍵字排序多關(guān)鍵字排序：實(shí)現(xiàn)多關(guān)鍵字排序有兩種常用的方法

最高位優(yōu)先MSD(MostSignificantDigitfirst)最低位優(yōu)先LSD(LeastSignificantDigitfirst)MSD與LSD不同特點(diǎn)

最高位優(yōu)先MSD是一個(gè)遞歸的過(guò)程，必須將序列逐層分割成若干子序列，然后對(duì)各子序列分別排序。最低位優(yōu)先LSD不必分成子序列，對(duì)每個(gè)關(guān)鍵字都是整個(gè)序列參加排序；并且可不通過(guò)關(guān)鍵字比較，而通過(guò)若干次分配與收集實(shí)現(xiàn)排序。基數(shù)排序基本思想：實(shí)現(xiàn)多關(guān)鍵字排序有兩種常用的方法

設(shè)置rd個(gè)箱子首先按

分量的取值，將記錄“分配”到不同箱子中去。然后掃描n個(gè)紀(jì)錄，按箱子的序號(hào)依次將各非空箱子中的記錄“收集”起來(lái)，這樣所有對(duì)象按取值排序完成。——一趟箱排序依次按Kid-1,Kid-2,…,Ki1的值重復(fù)上步，直到最后一趟對(duì)Ki1“分配”、“收集”完成后，所有對(duì)象就按其關(guān)鍵字的值從小到大排好序了。鏈?zhǔn)交鶖?shù)排序運(yùn)行實(shí)例初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：505008109930063269278083184589二趟收集：083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集：鏈?zhǔn)交鶖?shù)排序運(yùn)行實(shí)例008063083109184269278505589930三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589二趟收集：鏈?zhǔn)交鶖?shù)排序運(yùn)行實(shí)例性能分析

時(shí)間復(fù)雜度：若每個(gè)關(guān)鍵字有d位，需要重復(fù)執(zhí)行d趟“分配”與“收集”。每趟對(duì)n個(gè)對(duì)象進(jìn)行“分配”，對(duì)rd個(gè)箱子進(jìn)行“收集”。總時(shí)間復(fù)雜度為：O(d(n+rd))

空間復(fù)雜度：基數(shù)排序需要增加n+2rd個(gè)附加鏈接指針：O(n+2rd)

穩(wěn)定性：穩(wěn)定9.7各種排序方法的比較時(shí)間性能空間性能穩(wěn)定性及簡(jiǎn)單性關(guān)鍵碼的分布情況記錄本身的信息量時(shí)間性能排序方法平均情況最好情況最壞情況直接插入排序O(n2)O(n)O(n2)希爾排序O(nlog2n)~O(n2)O(n1.3)O(n2)起泡排序O(n2)O(n)O(n2)快速排序O(nlog2n)O(nlog2n)O(n2)簡(jiǎn)單選擇排序O(n2)O(n2)O(n2)堆排序O(nlog2n)O(nlog2n)O(nlog2n)歸并排序O(nlog2n)O(nlog2n)O(nlog2n)基數(shù)排序O(d(n+rd)O(d(n+rd)O(d(n+rd)時(shí)間性能排序方法平均情況直接插入排序O(n2)希爾排序O(nlog2n)~O(n2)起泡排序O(n2)快速排序O(nlog2n)簡(jiǎn)單選擇排序O(n2)堆排序O(nlog2n)歸并排序O(nlog2n)（1）直接插入排序、簡(jiǎn)單選擇排序和起泡排序?qū)儆谝活悾瑫r(shí)間復(fù)雜度為O(n2)；快速排序是目前最快的一種排序方法在待排序記錄個(gè)數(shù)較多的情況下，歸并排序比堆排序更快（3）希爾排序的時(shí)間性能取決于增量序列，介于O(n2)和O(nlog2n)之間。（2）堆排序、快速排序和歸并排序?qū)儆谝活悾瑫r(shí)間復(fù)雜度為O(nlog2n)；基數(shù)排序O(d(n+rd)從平均情況看時(shí)間性能排序方法最好情況直接插入排序O(n)希爾排序O(n1.3)起泡排序O(n)快速排序O(nlog2n)簡(jiǎn)單選擇排序O(n2)堆排序O(nlog2n)歸并排序O(nlog2n)（1）直接插入排序和起泡排序最好，O(n)；（2）其他排序算法的最好情況與平均情況相同。如果待排序序列接近正序，首選起泡排序和直接插入排序基數(shù)排序O(d(n+rd)從最好情況看時(shí)間性能排序方法最壞情況直接插入排序O(n2)希爾排序O(n2)起泡排序O(n2)快速排序O(n2)簡(jiǎn)單選擇排序O(n2)堆排序O(nlog2n)歸并排序O(nlog2n)（1）快速排序的時(shí)間復(fù)雜度為O(n2)；（3）最壞情況對(duì)直接選擇排序、堆排序和歸并排序影響不大。（2）直接插入排序和起泡排序雖然與平均情況相同，但系數(shù)大約增加一倍，所以運(yùn)行速度將降低一半；如果待排序序列接近正序或逆序，不使用快速排序基數(shù)排序O(d(n+rd)從最壞情況看空間性能排序方法輔助空間直接插入排序O(1)希爾排序O(1)起泡排序O(1)快速排序O(log2n)~O(n)簡(jiǎn)單選擇排序O(1)堆排序O(1)歸并排序O(n)（1）歸并排序的空間復(fù)雜度為O(n)；（2）快速排序的空間復(fù)雜度為O(log2n)~O(n)；（3）其它排序方法的空間復(fù)雜度為O(1)。基數(shù)排序O(n+rd)從空間性能看穩(wěn)定性與簡(jiǎn)單性（1）穩(wěn)定：包括直接插入排序、起泡排序、歸并排序和基數(shù)排序；（1）簡(jiǎn)單算法：包括直接插入排序、簡(jiǎn)單選擇排序和起泡排序，（2）不穩(wěn)定：包括希爾排序、簡(jiǎn)單選擇排序、快速排序和堆排序。（2）改進(jìn)算法，較復(fù)雜：包括希爾排序、堆排序、快速排序和歸并排序。從穩(wěn)定性看從算法簡(jiǎn)單性看記錄本身信息量記錄本身信息量越大，占用的存儲(chǔ)空間就越多，移動(dòng)記錄所花費(fèi)的時(shí)間就越多，所以對(duì)記錄的移動(dòng)次數(shù)較多的算法不利。記錄個(gè)數(shù)不多且記錄本身的信息量較大時(shí)，首選簡(jiǎn)單選擇排序算法記錄本身信息量的大小對(duì)改進(jìn)算法的影響不大。排序方法最好情況最壞情況平均情況直接插入排序O(n)O(n2)O(n2)起泡排序0O(n2)O(n2)簡(jiǎn)單選擇排序0O(n)O(n)從記錄本身信息量的大小看關(guān)鍵碼的分布（1）當(dāng)待排序記錄按關(guān)鍵碼有序時(shí)，插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度；對(duì)于快速排序而言，這是最壞情況，時(shí)間性能蛻化為O(n2)；（2）簡(jiǎn)單選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵碼的分布而改變。各種排序算法各有優(yōu)缺點(diǎn)，應(yīng)該根據(jù)實(shí)際情況選擇合適的排序算法從關(guān)鍵碼的分布看9.8外排序外排序概述磁盤排序——生成初始?xì)w并段磁盤排序——多路平衡歸并最佳歸并樹什么是外排序外排序：數(shù)據(jù)存放在外存中，數(shù)據(jù)排序時(shí)涉及內(nèi)、外存數(shù)據(jù)交換的排序方法。存儲(chǔ)在外存上的數(shù)據(jù)通常以文件為基本單位。排序數(shù)據(jù)存放在外存上排序結(jié)果存放在外存上排序過(guò)程借助內(nèi)存實(shí)現(xiàn)內(nèi)、外存數(shù)據(jù)交換（多）關(guān)鍵字比較（多）元素移動(dòng)（少）外排序時(shí)間=內(nèi)、外存數(shù)據(jù)交換+關(guān)鍵字比較外排序的基本方法外排序的基本方法是歸并排序法。它分為以下兩個(gè)步驟：（1）生成若干初始?xì)w并段：也稱為文件預(yù)處理，一種常規(guī)方法：把含有

n

個(gè)記錄的文件，按內(nèi)存大小

w

分成若干長(zhǎng)度為

w

的子文件

（歸并段）；分別將各子文件（歸并段）調(diào)入內(nèi)存，采用有效的內(nèi)排序方法排序后送回外存，產(chǎn)生n/w個(gè)初始?xì)w并段。待排序文件RL1...L2Ln內(nèi)存有序子文件（歸并段）外排序的基本方法外排序的基本方法是歸并排序法。它分為以下兩個(gè)步驟：（2）多路歸并：對(duì)這些初始?xì)w并段進(jìn)行多遍歸并，使得有序的歸并段逐漸擴(kuò)大，最后在外存上形成整個(gè)文件的單一歸并段，也就完成了這個(gè)文件的外排序。排好序文件內(nèi)存有序子文件（歸并段）...............磁盤排序過(guò)程Fin文件內(nèi)存讀寫Fout文件F1文件F2文件Fm文件…寫寫寫內(nèi)存讀讀讀

通過(guò)分割要排序的文件，生成若干初始?xì)w并段

對(duì)初始?xì)w并段進(jìn)行多路歸并，歸并成一個(gè)有序文件生成初始?xì)w并段常規(guī)方法：內(nèi)存大小為

w，每次從外存