8排序8.1排序概述8.2插入排序8.3簡(jiǎn)單選擇排序和冒泡排序8.4快速排序8.5堆排序8.6二路歸并排序8.7STL與排序8.8在線(xiàn)題目求解學(xué)習(xí)目標(biāo)1.記憶和理解排序的基本概念和術(shù)語(yǔ)。2.熟練掌握各種排序的方法。3.學(xué)會(huì)插入排序、快速排序、堆排序和二路歸并排序等排序算法的實(shí)現(xiàn)。4.能夠?qū)ε判蛩惴ㄗ骰镜臅r(shí)間/空間效率分析。5.學(xué)會(huì)運(yùn)用STL之sort和nth_element。8排序8.1排序概述排序的定義與術(shù)語(yǔ)排序是數(shù)據(jù)處理中一種很重要、很常用的操作，一般數(shù)據(jù)處理工

作25%的時(shí)間都在進(jìn)行排序。排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序”的記錄序列調(diào)整為“有序”的記錄序列。例如，將關(guān)鍵字序列(16,25,15,30,7,10,20,29,9,18)調(diào)整為(7,9,10,15,16,18,20,25,29,30)，就完成了關(guān)鍵字序列的升序排序。一般情況下，假設(shè)含n個(gè)記錄的序列為(R1,R2,…,Rn)，其相應(yīng)的關(guān)鍵字序列為(K1,K2,…,Kn)，這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在

的關(guān)系，將上述記錄序列重新排列為

的操作稱(chēng)作排序。8.1排序概述排序的定義與術(shù)語(yǔ)各不相同的關(guān)鍵字從小到大排列稱(chēng)為升序，當(dāng)有相同關(guān)鍵字時(shí)稱(chēng)為非遞減序；各不相同的關(guān)鍵字從大到小排列稱(chēng)為降序，當(dāng)有相同關(guān)鍵字時(shí)稱(chēng)為非遞增序。對(duì)關(guān)鍵字相同的數(shù)據(jù)元素，

若排序前后它們的領(lǐng)先關(guān)系保持不變，則稱(chēng)該排序方法是穩(wěn)定的，反之就是不穩(wěn)定的。

例如，對(duì)關(guān)鍵字序列(2,2,1)進(jìn)行簡(jiǎn)單選擇排序，得到非遞減序的關(guān)鍵字序列(1,2,2)，相同的關(guān)鍵字2的相對(duì)次序發(fā)生變化，因此可認(rèn)為簡(jiǎn)單選擇排序是不穩(wěn)定的。8.1排序概述排序的分類(lèi)若整個(gè)排序過(guò)程不需要訪問(wèn)外存便能完成，則稱(chēng)此類(lèi)排序方法為內(nèi)部排序；反之，若待排序記錄的數(shù)量很大，整個(gè)序列的排序過(guò)程不可能僅在內(nèi)存中完成，而需借助外存，則稱(chēng)此類(lèi)排序方法為外部排序。內(nèi)部排序的過(guò)程是一個(gè)逐步擴(kuò)大記錄的有序序列長(zhǎng)度的過(guò)程。基于不同的“擴(kuò)大”有序序列長(zhǎng)度的方法，內(nèi)部排序方法大致可分為插入類(lèi)、交換類(lèi)、選擇類(lèi)、歸并類(lèi)和分配類(lèi)等類(lèi)型。插入類(lèi)排序?qū)o(wú)序子序列中的一個(gè)記錄“插入”到有序序列中，從而增加記錄的有序子序列的長(zhǎng)度。直接插入排序、折半插入排序和希爾排序?qū)儆诓迦腩?lèi)排序。8.1排序概述排序的分類(lèi)交換類(lèi)排序通過(guò)“交換”無(wú)序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長(zhǎng)度。冒泡排序和快速排序?qū)儆诮粨Q類(lèi)排序。選擇類(lèi)排序從記錄的無(wú)序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長(zhǎng)度。簡(jiǎn)單選擇排序和堆排序?qū)儆谶x擇類(lèi)排序。歸并類(lèi)排序通過(guò)“歸并”兩個(gè)或兩個(gè)以上的記錄有序子序列，逐步增加記錄有序序列的長(zhǎng)度。二路歸并排序?qū)儆跉w并類(lèi)排序。分配類(lèi)排序主要通過(guò)“分配”和“收集”這兩個(gè)操作完成排序，不需進(jìn)行關(guān)鍵字的比較。桶排序和基數(shù)排序?qū)儆诜峙漕?lèi)排序。8.2插入排序直接插入排序直接插入排序算法思想

對(duì)n個(gè)元素進(jìn)行非遞減序排序，共進(jìn)行n-1趟，每趟插入排序（設(shè)待插入元素為R[i]，2≤i≤n）分三步進(jìn)行：（1）在R[1..i-1]中查找R[i]的插入位置，使得

R[1..j].key

≤

R[i].key<R[j+1..i-1].key；（2）將R[j+1..i-1]中的所有記錄均后移一個(gè)位置；（3）將R[i]插入（復(fù)制）到R[j+1]的位置上。8.2插入排序直接插入排序例8.2.1直接插入排序

對(duì)于關(guān)鍵字序列(16,25,15,30,7,10,20,29,9,18)，寫(xiě)出采用直接插入排序進(jìn)行升序排序的每趟結(jié)果。初態(tài)：(16)2515307102029918第一趟：(1625)15307102029918第二趟：(151625)307102029918第三趟：(15162530)7102029918第四趟：(715162530)102029918第五趟：(71015162530)2029918第六趟：(7101516202530)29918第七趟：(710151620252930)918第八趟：(7910151620252930)18第九趟：(791015161820252930)8.2插入排序直接插入排序直接插入排序算法實(shí)現(xiàn)

在直接插入排序的查找插入位置的過(guò)程中，對(duì)于那些關(guān)鍵字大于待插入記錄（元素）的記錄，可以在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)。typedefstringInfoType;

//其他數(shù)據(jù)項(xiàng)的類(lèi)型constintMaxSize=1000;

//待排順序表最大長(zhǎng)度structElemType{

//記錄類(lèi)型

intkey;

//關(guān)鍵字項(xiàng),關(guān)鍵字類(lèi)型默認(rèn)為整型

InfoTypeinfo;

//其他數(shù)據(jù)項(xiàng)};structSqList{

//順序表類(lèi)型

ElemTyper[MaxSize+1];

//r[0]閑置

intlength;

//順序表長(zhǎng)度};8.2插入排序直接插入排序直接插入排序算法實(shí)現(xiàn)//對(duì)順序表L作直接插入排序voidInsertSort(SqList&L){

for(inti=2;i<=L.length;i++){

if(L.r[i].key>=L.r[i-1].key)

continue;

L.r[0]=L.r[i];

//復(fù)制為監(jiān)視哨

intj;

for(j=i-1;L.r[0].key<L.r[j].key;j--)

L.r[j+1]=L.r[j];

//記錄后移

L.r[j+1]=L.r[0];

//插入到正確位置

}}8.2插入排序直接插入排序直接插入排序算法的結(jié)論（1）直接插入排序最好時(shí)間復(fù)雜度為O(n)（初始已升序排列，僅需比較n-1次），最壞時(shí)間復(fù)雜度為O(n2)（初始是降序序列，比較和移動(dòng)次數(shù)都等于1+2+3+…+(n-1)=n(n-1)/2），平均時(shí)間復(fù)雜度為O(n2)；（2）直接插入排序的空間復(fù)雜度為O(1)（使用R[0]作為輔助變量）；（3）穩(wěn)定，因?yàn)榇迦朐氐年P(guān)鍵字大于等于所比較的元素時(shí)結(jié)束移動(dòng)。8.2插入排序直接插入排序直接插入排序算法的簡(jiǎn)寫(xiě)由于排序是按關(guān)鍵字進(jìn)行比較，交換時(shí)直接交換整個(gè)記錄，其他數(shù)據(jù)項(xiàng)可以暫不考慮，此后討論的排序算法直接考慮整型關(guān)鍵字?jǐn)?shù)組。//對(duì)關(guān)鍵字?jǐn)?shù)組R作直接插入排序voidInsertSortSimple(intR[],intn){

for(inti=2;i<=n;i++){

if(R[i]>=R[i-1])continue;

R[0]=R[i];

//復(fù)制為監(jiān)視哨

intj;

for(j=i-1;R[0]<R[j];j--)

R[j+1]=R[j];

//記錄后移

R[j+1]=R[0];

//插入到正確位置

}}8.2插入排序折半插入排序在直接插入排序中，對(duì)于第i趟排序而言，下標(biāo)從1到i-1的記錄已按關(guān)鍵字非遞減序排列，因此查找第i個(gè)記錄的插入位置可用折半查找。如此可減少比較次數(shù)，從而提高算法時(shí)間效率。算法實(shí)現(xiàn)//折半插入排序，查找插入位置時(shí)采用折半查找voidInsertSortBs(intR[],intn){

for(inti=2;i<=n;i++){

R[0]=R[i];

intlow=1,high=i-1;

while(low<=high){

intmid=(low+high)/2;

if(R[0]>=R[mid])low=mid+1;

elsehigh=mid-1;

}8.2插入排序折半插入排序算法實(shí)現(xiàn)

for(intj=i-1;j>high;j--)

R[j+1]=R[j];

R[high+1]=R[0];}}折半插入排序找到插入位置后，移動(dòng)元素的次數(shù)與直接插入排序相同，因此折半插入排序的時(shí)間復(fù)雜度依然為O(n2)，而空間復(fù)雜度也依然為O(1)。折半查找效率高于順序查找，折半插入算法的時(shí)間效率較之直接插入排序一般情況下更高。8.2插入排序希爾排序直接插入排序在元素個(gè)數(shù)較少且待排序列基本有序時(shí)效率較高。希爾排序從“減少元素個(gè)數(shù)”和“序列基本有序”兩方面改進(jìn)直接插入排序。希爾排序，也稱(chēng)縮小增量排序。希爾排序的基本思想：采用分組插入的方法，先將待排序列按同一個(gè)增量分成若干組（例如，n=10時(shí)，第一趟以5為增量分成5組）分別進(jìn)行直接插入排序，再縮小增量重新分組（例如，n=10時(shí)，第二趟以3為增量分成3組）進(jìn)行直接插入排序，直到增量為1時(shí)進(jìn)行最后一次直接插入排序得到有序序列。8.2插入排序希爾排序例8.2.2希爾排序

對(duì)于關(guān)鍵字序列(16,25,15,30,7,10,20,29,9,18)，寫(xiě)出采用希爾排序（增量依次取5、3、1）進(jìn)行升序排序的每趟結(jié)果。對(duì)于每趟的準(zhǔn)備階段（含初態(tài)），下劃線(xiàn)相同（或不帶下劃線(xiàn)）的關(guān)鍵字為一組。8.2插入排序希爾排序算法實(shí)現(xiàn)//一趟希爾排序，對(duì)R數(shù)組中的n個(gè)關(guān)鍵字以d為增量進(jìn)行一趟希爾排序voidShellInsert(intR[],intn,intd){

for(inti=d+1;i<=n;i++){

if(R[i]>=R[i-d])continue;

R[0]=R[i];

intj;

for(j=i-d;j>0&&R[0]<R[j];j-=d)

R[j+d]=R[j];

R[j+d]=R[0];

}}8.2插入排序希爾排序算法實(shí)現(xiàn)//對(duì)存放在R數(shù)組中的n個(gè)關(guān)鍵字排序，deta是增量數(shù)組，共m個(gè)數(shù)組元素voidShellSort(intR[],intn,intdeta[],intm){

for(inti=0;i<m;i++){

ShellInsert(R,n,deta[i]);

}}希爾排序的結(jié)論（1）平均時(shí)間復(fù)雜度約為O(n1.3)；（2）空間復(fù)雜度為O(1)；（3）不穩(wěn)定，例如，待排關(guān)鍵字序列(22111)排序后得到(11122)。8.3簡(jiǎn)單選擇排序和冒泡排序簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序的基本思想：對(duì)n個(gè)關(guān)鍵字非遞減序排序，共進(jìn)行n-1趟排序；每一趟從待排序的數(shù)列中選出最小的一個(gè)關(guān)鍵字，放到待排序列的最前位置。

其中，對(duì)于第i（1≤i≤n-1）趟排序，先假設(shè)待排數(shù)列中最前面的關(guān)鍵字（下標(biāo)為i）最小，以假設(shè)的最小關(guān)鍵字（下標(biāo)為k，初值為i）與后面的關(guān)鍵字（下標(biāo)為j，且i<j≤n）比較，若后面的關(guān)鍵字小，則記錄其下標(biāo)到k中，即k=j，最后若實(shí)際最小關(guān)鍵字不在待排序列的最前位置，即k!=i，則交換下標(biāo)為k、i的兩個(gè)元素。8.3簡(jiǎn)單選擇排序和冒泡排序簡(jiǎn)單選擇排序例8.3.1簡(jiǎn)單選擇排序

對(duì)于關(guān)鍵字序列(16,25,15,30,7,10,20,29,9,18)，寫(xiě)出采用簡(jiǎn)單選擇排序進(jìn)行升序排序的每趟結(jié)果。第一趟：(7)25153016102029918第二趟：(79)1530161020292518第三趟：(7910)30161520292518第四趟：(791015)163020292518第五趟：(79101516)3020292518第六趟：(7910151618)20292530第七趟：(791015161820)292530第八趟：(79101516182025)2930第九趟：(7910151618202529)308.3簡(jiǎn)單選擇排序和冒泡排序簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序的算法實(shí)現(xiàn)//對(duì)記錄序列R[1..n]作簡(jiǎn)單選擇排序voidSelectSort(intR[],intn){

for(inti=1;i<n;i++){

//從區(qū)間R[i..n]之間選出最小的記錄

intk=i;

for(intj=i+1;j<=n;j++){

if(R[j]<R[k])k=j;

}

if(i!=k)swap(R[k],R[i]);

//與第i個(gè)記錄互換

}}8.3簡(jiǎn)單選擇排序和冒泡排序簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序的結(jié)論（1）最好、最壞和平均時(shí)間復(fù)雜度都為O(n2)；（2）空間復(fù)雜度為O(1)（交換需用一個(gè)輔助變量）；（3）不穩(wěn)定，例如，待排關(guān)鍵字序列(221)排序后得到(122)。8.3簡(jiǎn)單選擇排序和冒泡排序冒泡排序冒泡的基本思想：對(duì)n個(gè)關(guān)鍵字非遞減序排序，共進(jìn)行n-1趟排序；每一趟依次比較相鄰的兩個(gè)關(guān)鍵字，將小者放在前面，大者放在后面，每一趟排序結(jié)束時(shí)，將待排序列的最大關(guān)鍵字放到待排序列的最后位置。

其中，對(duì)于第i（1≤i<n）趟排序，從第一個(gè)數(shù)開(kāi)始依次比較相鄰的兩個(gè)關(guān)鍵字（由于待排序列中共有n-i+1個(gè)關(guān)鍵字，因此共需要進(jìn)行n-i次比較），若前面的關(guān)鍵字比后面的大，則交換這兩個(gè)關(guān)鍵字。8.3簡(jiǎn)單選擇排序和冒泡排序冒泡排序例8.3.2冒泡排序

對(duì)于關(guān)鍵字序列(16,25,15,30,7,10,20,29,9,18)，寫(xiě)出采用冒泡排序進(jìn)行升序排序的每趟結(jié)果。第一趟：1615257102029918(30)第二趟：15167102025918(2930)第三趟：157101620918(252930)第四趟：7101516918(20252930)第五趟：71015916(1820252930)第六趟：710915(161820252930)第七趟：7910(15161820252930)第八趟：79(1015161820252930)第九趟：7(91015161820252930)實(shí)際上，若某趟排序過(guò)程中未發(fā)生交換操作，則表現(xiàn)排序已完成，可提前結(jié)束排序。故本例只需寫(xiě)出前7趟結(jié)果即可。8.3簡(jiǎn)單選擇排序和冒泡排序冒泡排序冒泡排序的算法實(shí)現(xiàn)//對(duì)記錄序列R[1..n]作冒泡排序voidBubbleSort(intR[],intn){

for(inti=1;i<n;i++){

boolflag=false;

//

是否交換的標(biāo)記，初值為false

for(intj=1;j<=n-i;j++){

if(R[j+1]<R[j]){

swap(R[j],R[j+1]);

flag=true;

//

發(fā)生交換則修改標(biāo)記為true

}

}

if(flag==false)break;

//

若未發(fā)生交換，則提前結(jié)束排序

}}8.3簡(jiǎn)單選擇排序和冒泡排序冒泡排序冒泡排序的結(jié)論（1）最好時(shí)間復(fù)雜度為O(n)（初始是升序序列），最壞時(shí)間復(fù)雜度為O(n2)（初始是降序序列），平均時(shí)間復(fù)雜度為O(n2)；（2）空間復(fù)雜度為O(1)（交換操作需用一個(gè)輔助變量）；（3）穩(wěn)定，因?yàn)閮蓚€(gè)關(guān)鍵字相等時(shí)不作交換。8.4快速排序快速排序基礎(chǔ)快速排序的基本思想：n個(gè)記錄進(jìn)行非遞減序排序，共進(jìn)行若干趟劃分；每次劃分找一個(gè)記錄（一般設(shè)為第一個(gè)），以它作為“樞軸”（也稱(chēng)“支點(diǎn)”），凡關(guān)鍵字小于樞軸關(guān)鍵字的記錄均移動(dòng)至樞軸之前；凡關(guān)鍵字大于樞軸關(guān)鍵字的記錄均移動(dòng)至該記錄之后。從而使得一趟劃分把待排記錄序列R[s..t]以樞軸為界分割成兩個(gè)子序列：R[s..i-1]和R[i+1..t]，且它們滿(mǎn)足R[j].key≤R[i].key≤R[k].key，其中s≤j≤i-1，i+1≤k≤t。之后分別對(duì)分割所得的兩個(gè)子序列“遞歸”進(jìn)行快速排序，即對(duì)于樞軸前后的兩個(gè)子序列，繼續(xù)按相同方法進(jìn)行劃分，直到記錄數(shù)小于2。8.4快速排序快速排序基礎(chǔ)一趟快速排序（一次劃分）的基本思想：設(shè)立了兩個(gè)指針（實(shí)際上是下標(biāo)）low和high，它們的初值分別為s和t。從high所指記錄開(kāi)始與樞軸比較，把關(guān)鍵字小于樞軸的記錄“交換”到左邊的“空位”（low所指）；再?gòu)膌ow所指記錄開(kāi)始與樞軸比較，把關(guān)鍵字大于樞軸的記錄“交換”到右邊的“空位”（high所指）；如此反復(fù)執(zhí)行，直到low==high，在該處放置樞軸。由于在確定最終位置前把樞軸放到“空位”上沒(méi)有什么意義，因此這里的“交換”操作是指把需要調(diào)整位置的記錄直接放到“空位”上，如此可以?xún)H執(zhí)行一條賦值語(yǔ)句就完成“交換”操作，從而提高算法的時(shí)間效率。8.4快速排序快速排序基礎(chǔ)例8.4.1快速排序

對(duì)于關(guān)鍵字序列(16,25,15,30,7,10,20,29,9,18)，寫(xiě)出采用快速排序進(jìn)行升序排序的每趟結(jié)果。第一趟：[910157]16[3020292518]第二趟：[7]9[1510]16[3020292518]第三趟：79[10]1516[3020292518]第四趟：79101516[18202925]30第五趟：7910151618[202925]30第六趟：791015161820[2925]30第七趟：791015161820[25]2930把每次劃分視作一趟快速排序，且每次劃分以待排序列的首元素作為樞軸。每趟快速排序的結(jié)果如何得到？8.4快速排序快速排序算法實(shí)現(xiàn)快速排序的劃分算法//一趟快速排序（一次劃分）算法，待排序列R[low,high]intPartition(intR[],intlow,inthigh){

R[0]=R[low];

//樞軸（支點(diǎn)）暫存于R[0]

while(low<high){

//當(dāng)待排區(qū)間多于1個(gè)元素時(shí)重復(fù)執(zhí)行

while(low<high&&R[high]>=R[0])

high--;

//從右向左掃描，找一個(gè)關(guān)鍵字小于樞軸的記錄

R[low]=R[high];//把小于樞軸關(guān)鍵字的記錄“換”到左邊空位

while(low<high&&R[low]<=R[0])

low++;

//從左向右掃描，找一個(gè)關(guān)鍵字大于樞軸的記錄

R[high]=R[low];//把大于樞軸關(guān)鍵字的記錄“換”到右邊空位

}

R[low]=R[0];

//樞軸存入low（或high）所指存儲(chǔ)單元

returnlow;

//返回樞軸所在位置}8.4快速排序快速排序算法實(shí)現(xiàn)快速排序算法實(shí)現(xiàn)//快速排序，對(duì)記錄序列R[s..t]進(jìn)行快速排序voidQuickSort(intR[],ints,intt){

if(s>=t)return;

//待排區(qū)間長(zhǎng)度小于2

intk=Partition(R,s,t);//對(duì)R[s..t]進(jìn)行一次劃分

QuickSort(R,s,k-1);

//對(duì)左子序列R[s..k-1]遞歸快速排序

QuickSort(R,k+1,t);

//對(duì)右子序列R[k+1..t]遞歸快速排序}//調(diào)用QuickSort算法對(duì)記錄序列R[1..n]進(jìn)行快速排序voidQSort(intR[],intn){

QuickSort(R,1,n);}8.4快速排序快速排序算法實(shí)現(xiàn)通常認(rèn)為，在所有數(shù)量級(jí)為O(nlog2n)的排序方法中，快速排序的平均性能是最好的。快速排序算法在數(shù)據(jù)量極少（n≤20）的的情況下其性能不如插入排序?？焖倥判蛩惴ㄟm用于初始記錄無(wú)序且n較大的情況。8.4快速排序快速排序算法實(shí)現(xiàn)快速排序的結(jié)論（1）最好情況下，樞軸每次將待排序列分為左右大致均勻的兩半，快速排序遞歸樹(shù)的深度的數(shù)量級(jí)為O(log2n)，而n個(gè)元素時(shí)定位樞軸位置的時(shí)間數(shù)量級(jí)為O(n)，因此最好時(shí)間復(fù)雜度為O(nlog2n)。若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，對(duì)n個(gè)元素進(jìn)行劃分僅得到一個(gè)左區(qū)間或右區(qū)間，此時(shí)快速排序退化為冒泡排序，其時(shí)間復(fù)雜度為O(n2)。快速排序的平均時(shí)間復(fù)雜度為O(nlog2n)。（2）快速排序算法是遞歸算法，需要用一個(gè)棧保存相關(guān)數(shù)據(jù)，其空間復(fù)雜度與遞歸樹(shù)深度一致，最好為O(log2n)，最壞為O(n)。（3）不穩(wěn)定；例如，待排序列(211)排序后為(112)。8.5堆排序堆排序基礎(chǔ)堆是滿(mǎn)足下列性質(zhì)的數(shù)列(r1,r2,…，rn)：或大頂堆小頂堆例如，數(shù)列(12,36,27,65,40,34,98,81,73,55,49)是一個(gè)小頂堆

數(shù)列(12,36,27,65,40,14,98,81,73,55,49)不是堆

因?yàn)閞3=27>14=r6，r3=27<98=r7。8.5堆排序堆排序基礎(chǔ)若將數(shù)列按順序從上往下、從左往右建立二叉樹(shù)，則得到一棵完全二叉樹(shù)，其中，r2i是ri的左孩子，r2i+1是ri的右孩子。小頂堆不是堆(12,36,27,65,40,34,98,81,73,55,49)(12,36,27,65,40,14,98,81,73,55,49)

在小頂堆對(duì)應(yīng)的完全二叉樹(shù)中，任意一個(gè)非葉結(jié)點(diǎn)的關(guān)鍵字都不大于它的左、右孩子的關(guān)鍵字。8.5堆排序堆排序基礎(chǔ)堆排序就是利用堆的特性對(duì)記錄序列進(jìn)行排序的一種排序方法。堆排序的基本思想：若對(duì)n個(gè)記錄構(gòu)成的待排序列按關(guān)鍵字非遞減序排序，則先按待排記錄的關(guān)鍵字建立初始堆，再進(jìn)行n-1趟堆排序。對(duì)于每趟堆排序，交換根結(jié)點(diǎn)（堆頂元素）和待排序列中的最后一個(gè)結(jié)點(diǎn)，并把交換后的待排序列（不含原堆頂元素）重新調(diào)整為一個(gè)堆。對(duì)于初始堆，通常非遞減序排序時(shí)建大頂堆，非遞增序排序時(shí)建小頂堆。8.5堆排序堆排序基礎(chǔ)實(shí)現(xiàn)堆排序需要解決兩個(gè)問(wèn)題：（1）建初始堆：如何把一個(gè)無(wú)序序列建成一個(gè)堆？（2）篩選堆：如何去掉原堆頂元素之后，調(diào)整剩余元素成為一個(gè)新的堆？篩選堆指的是對(duì)一棵左、右子樹(shù)均為堆的完全二叉樹(shù)，“調(diào)整”根結(jié)點(diǎn)使整個(gè)二叉樹(shù)成為一個(gè)堆。篩選堆的算法思想：對(duì)于大頂堆，不斷地把根結(jié)點(diǎn)root與其左、右孩子中關(guān)鍵字大者進(jìn)行交換，直到把root放在合適的位置（最終二叉樹(shù)滿(mǎn)足堆的特性）；對(duì)于小頂堆，不斷地把根結(jié)點(diǎn)root與其左、右孩子中關(guān)鍵字小者交換，直到把root放在合適的位置。8.5堆排序堆排序基礎(chǔ)篩選堆示例大頂堆交換根結(jié)點(diǎn)98和最后一個(gè)結(jié)點(diǎn)12后，除98之外的其他結(jié)點(diǎn)不構(gòu)成大頂堆，但結(jié)點(diǎn)12的左、右子樹(shù)都是堆一趟篩選后的結(jié)果，在篩選過(guò)程中，12依次與81、73、64交換8.5堆排序堆排序基礎(chǔ)建初始堆實(shí)際上是一個(gè)從下往上反復(fù)篩選的過(guò)程。對(duì)于無(wú)序序列構(gòu)成的n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其最后一個(gè)非葉結(jié)點(diǎn)是第

個(gè)結(jié)點(diǎn)，篩選只需從第

個(gè)結(jié)點(diǎn)為根的子樹(shù)開(kāi)始篩選，使該子樹(shù)成為堆，然后依次向前對(duì)各結(jié)點(diǎn)為根的子樹(shù)進(jìn)行篩選，使之成為堆，直到根結(jié)點(diǎn)完成篩選過(guò)程為止。8.5堆排序堆排序基礎(chǔ)例8.5.1大頂堆的建立

請(qǐng)根據(jù)給定的關(guān)鍵字序列(40,55,49,73,12,27,98,81,64,36)建立初始大頂堆根據(jù)給定序列建立完全二叉樹(shù)初始堆，依次篩選以12、73、49、55、40為根的子樹(shù)8.5堆排序堆排序基礎(chǔ)例8.5.2堆排序

對(duì)于關(guān)鍵字序列(16,25,15,30,7,10,20,29,9,18)，寫(xiě)出采用堆排序進(jìn)行升序排序的每趟結(jié)果。初始堆：302920251810151697第一趟：2925201618101579(30)第二趟：25182016910157(2930)第三趟：201815169107(252930)第四趟：1816157910(20252930)第五趟：16101579(1820252930)第六趟：151097(161820252930)第七趟：1079(15161820252930)第八趟：97(1015161820252930)第九趟：7(91015161820252930)初始堆如何得到？每趟堆排序的過(guò)程如何？8.5堆排序堆排序算法實(shí)現(xiàn)篩選算法/*已知R[s..m]中記錄的關(guān)鍵字除R[s]之外均滿(mǎn)足堆的特征，函數(shù)自上而下調(diào)整R[s]的關(guān)鍵字，使R[s..m]也成為一個(gè)大頂堆*/voidHeapAdjust(intR[],ints,intm){intrc=R[s];

//暫存堆頂記錄R[s]（根）

//自上而下的篩選過(guò)程

for(intj=2*s;j<=m;j*=2){//s的左孩子為2s

//左、右子樹(shù)的“根”之間先相互比較,令j指向其中的關(guān)鍵字大者

if(j<m&&R[j]<R[j+1])j++;

if(rc>=R[j])break;//“根”和大的“子樹(shù)根”之間比較

R[s]=R[j];//左、右孩子中關(guān)鍵字大者調(diào)到父結(jié)點(diǎn)

s=j;

//s下移指向左、右孩子中關(guān)鍵字大的結(jié)點(diǎn)

}

R[s]=rc;

//將調(diào)整前的堆頂記錄插入到s位置}8.5堆排序堆排序算法實(shí)現(xiàn)堆排序算法

堆排序先建立初始堆，然后進(jìn)行n-1趟排序，每趟排序先交換堆頂元素和待排序列中的最后一個(gè)元素，再把待排序列重新調(diào)整為堆。//堆排序算法voidHeapSort(intR[],intn){

//對(duì)R[]進(jìn)行堆排序

for(inti=n/2;i>0;i--)//建大頂堆HeapAdjust(R,i,n);

for(int

i=n;i>1;i--){

//進(jìn)行n-1趟排序

//將堆頂記錄和待排序列R[1..i]中最后一個(gè)記錄R[i]交換

swap(R[1],R[i]);

//交換堆頂元素R[1]和R[i]

HeapAdjust(R,1,i-1);//將R[1..i-1]重新調(diào)整為大頂堆

}}8.5堆排序堆排序算法實(shí)現(xiàn)堆排序的結(jié)論（1）最好、最壞和平均時(shí)間復(fù)雜度都為O(nlog2n)；（2）空間復(fù)雜度為O(1)；（3）不穩(wěn)定，例如，關(guān)鍵字序列(11)排序后的序列為(11)。8.6二路歸并排序二路歸并排序基礎(chǔ)歸并排序?qū)蓚€(gè)或兩個(gè)以上的有序子序列“歸并”為一個(gè)有序序列。二路歸并排序是一種最常用的歸并排序，其基本思想：n個(gè)記錄進(jìn)行非遞減序排序，共進(jìn)行若干趟歸并；每趟歸并把位置相鄰的兩個(gè)有序子序列歸并為一個(gè)有序序列，如此反復(fù)歸并，直到最終得到一個(gè)長(zhǎng)度為n的有序序列。若采用迭代的二路歸并排序，則可假設(shè)每個(gè)記錄已有序，然后相鄰的兩個(gè)記錄歸并，共得到

個(gè)長(zhǎng)度為2或1的有序子序列，再相鄰的兩個(gè)有序子序列歸并，……，如此反復(fù)，直到得到一個(gè)長(zhǎng)度為n的有序序列。8.6二路歸并排序二路歸并排序基礎(chǔ)例8.6.1歸并排序（迭代法）

對(duì)于關(guān)鍵字序列(16,25,35,30,27,40,20,29,59,18)，寫(xiě)出采用迭代的二路歸并排序進(jìn)行升序排序的每趟結(jié)果。初始：

[16][25][35][30][27][40][20][29][59][18]第一趟：[1625][3035][2740][2029][1859]第二趟：[16253035][20272940][1859]第三趟：[1620252729303540][1859]第四趟：[16182025272930354059]8.6二路歸并排序二路歸并排序基礎(chǔ)若無(wú)序記錄序列R[s..t]所分成的兩部分R[s..m]和R[m+1..t]（m=(s+t)/2）已分別按關(guān)鍵字有序，則可很容易將它們歸并成為一個(gè)有序序列。由此，應(yīng)該先“遞歸”地分別對(duì)這兩部分進(jìn)行二路歸并排序。遞歸的二路歸并排序：對(duì)于給定的n個(gè)元素的待排序列，先進(jìn)行拆分，直到得到n個(gè)僅有一個(gè)元素的有序子序列，再進(jìn)行相鄰有序子序列的歸并，直到得到一個(gè)長(zhǎng)度為n的有序序列。遞歸的二路歸并排序要注意“在哪里拆分，就在哪里歸并”。8.6二路歸并排序二路歸并排序基礎(chǔ)例8.6.2歸并排序（遞歸法）

對(duì)于關(guān)鍵字序列(16,25,35,30,27,40,20,29,59,18)，寫(xiě)出采用遞歸的二路歸并排序進(jìn)行升序排序的每趟結(jié)果。先拆分：{1625353027}{4020295918}{162535}{3027}{402029}{5918}{1625}[35][30][27]{4020}[29][59][18][16][25][35][30][27][40][20][29][59][18]再歸并：第一趟：[1625][35][30][27][2040][29][59][18]第二趟：[162535][2730][202940][1859]第三趟：[1625273035][1820294059]第四趟：[16182025272930354059]8.6二路歸并排序二路歸并排序算法實(shí)現(xiàn)歸并算法

歸并算法是二路歸并的核心算法，其基本思想：逐個(gè)比較兩個(gè)有序子序列中元素，把其中的小者存放到結(jié)果數(shù)組中，直到其中一個(gè)子序列的所有記錄都存放好為止。此時(shí)，另一個(gè)子序列還包含一些剩余記錄，需把它們?cè)僦饌€(gè)復(fù)制到結(jié)果數(shù)組中。

歸并算法原型：voidMerge(intSR[],intTR[],inti,intm,intn);

實(shí)現(xiàn)將分別有序的記錄序列SR[i..m]和SR[m+1..n]歸并為有序的SR[i..n]，TR是輔助數(shù)組。8.6二路歸并排序二路歸并排序算法實(shí)現(xiàn)歸并算法

voidMerge(intSR[],intTR[],inti,intm,intn){

intj=m+1,k=i,s=i;

//i、j分別指向第一、二個(gè)有序子序列的開(kāi)始

while(i<=m&&j<=n){//當(dāng)兩個(gè)有序子序列都還有元素時(shí)比較并歸并

if(SR[i]<=SR[j])//把兩個(gè)有序子序列當(dāng)前的小者存放到TR[]中

TR[k++]=SR[i++];

else

TR[k++]=SR[j++];

}

while(i<=m)TR[k++]=SR[i++];//復(fù)制SR[i..m]的剩余部分到TR[]中

while(j<=n)TR[k++]=SR[j++];//復(fù)制SR[j..n]的剩余部分到TR[]中

while(s<=n){

//把TR[]復(fù)制回SR[]

SR[s]=TR[s];

s++;

}}8.6二路歸并排序二路歸并排序算法實(shí)現(xiàn)二路歸并排序算法二路歸并排序算法將無(wú)序記錄序列R[s..t]（s<t）分成兩部分R[s..m]和R[m+1..t]（m=(s+t)/2），并在對(duì)這兩個(gè)子序列分別遞歸進(jìn)行二路歸并排序后，調(diào)用歸并算法Merge進(jìn)行歸并。//對(duì)SR[s..t]進(jìn)行二路歸并排序,TR[]為輔助數(shù)組voidMergeSort(intSR[],intTR[],ints,intt){

if(s>=t)return;

//待排區(qū)間長(zhǎng)度小于2

intm=(s+t)/2;

//將SR[s..t]平分為SR[s..m]和SR[m+1..t]

MergeSort(SR,TR,s,m);//遞歸處理左半部分

MergeSort(SR,TR,m+1,t);//遞歸處理右半部分

Merge(SR,TR,s,m,t);

//進(jìn)行一次歸并}8.6二路歸并排序二路歸并排序算法實(shí)現(xiàn)對(duì)關(guān)鍵字序列R[1..n]排序可以調(diào)用二路歸并排序算法MergeSort

//對(duì)R[1..n]進(jìn)行二路歸并排序voidMSort(intR[],intLength){

int*TR=newint[Length+1];

//輔助數(shù)組

MergeSort(R,TR,1,Length);

delete[]TR;}8.6二路歸并排序二路歸并排序算法實(shí)現(xiàn)二路歸并排序的結(jié)論（1）二路歸并排序的最好、最壞和平均時(shí)間復(fù)雜度都為O(nlog2n)；（2）二路歸并空間復(fù)雜度為O(n)；（3）穩(wěn)定，因?yàn)閷?duì)于兩個(gè)相等關(guān)鍵字的記錄，位于前面的記錄先放入結(jié)果數(shù)組，因此相同關(guān)鍵字的記錄的相對(duì)位置不會(huì)發(fā)生改變。8.7STL與排序STL提供了較多的排序算法，包括sort、nth_element、stable_sort和partial_sort等，相應(yīng)的頭文件為algorithm。sort可能采用快速排序、堆排序或插入排序。nth_element采用快速排序。stable_sort采用歸并排序。partial_sort采用堆排序。8.7STL與排序STL之sortSTL中的sort算法，采用混合算法：（1）在數(shù)據(jù)量少的時(shí)候，算法轉(zhuǎn)入插入排序;（2）其他情況下則優(yōu)先采用快速排序;（3）針對(duì)快速排序最壞情況性能會(huì)下降到O(n2)，引入一個(gè)遞歸計(jì)數(shù)，當(dāng)遞歸深度超過(guò)一定閾值，則算法轉(zhuǎn)入一個(gè)相對(duì)較慢但最壞情況也是O(nlog2n)的算法，比如堆排序。sort的常用的方式：sort(first,last[,cmp]);

表示對(duì)待排的閉開(kāi)區(qū)間[first,last)內(nèi)的元素按可選的比較函數(shù)參數(shù)cmp所指定的比較規(guī)則進(jìn)行排序。若cmp參數(shù)省略，則默認(rèn)為非遞減序排序。first、last可以是迭代器或地址參數(shù)。8.7STL與排序STL之sort使用sort的簡(jiǎn)單示例#include<iostream>#include<algorithm>usingnamespacestd;voidPrint(inta[],intn);boolcmp(inta,intb);intmain(){

strings="0h2yn1y2r9y";

sort(s.begin(),s.end());

//

對(duì)字符串非遞減排序，參數(shù)為迭代器

cout<<s<<endl;

//輸出：01229hnryyy

intR[11]={0,16,25,15,30,7,10,20,29,9,18};

sort(R+1,R+11);//排序區(qū)間[&R[1],&R[10]+1)，參數(shù)為數(shù)組元素地址

Print(R,10);

//輸出：791015161820252930

sort(R+1,R+11,cmp);//排序區(qū)間[&R[1],&R[10]+1)8.7STL與排序STL之sort使用sort的簡(jiǎn)單示例

Print(R,10);

//輸出：302925201816151097

return0;}//比較函數(shù)，若作為sort的第三個(gè)參數(shù)，則將按降序排序

boolcmp(inta,intb){

returna>b;}voidPrint(inta[],intn){

//輸出函數(shù)

for(inti=1;i<=n;i++)

{

if(i>1)cout<<"";

cout<<a[i];

}

cout<<endl;}8.7STL與排序STL之sort結(jié)構(gòu)體數(shù)組排序#include<string>#include<algorithm>

//

頭文件structItem{

//結(jié)構(gòu)體類(lèi)型

intkey;

//關(guān)鍵字

stringotherinfo;

//其他數(shù)據(jù)項(xiàng)};boolcmp(Itema,Itemb){

//比較函數(shù)，指定按關(guān)鍵字從大到小排序

returna.key>b.key;}ItemR[100];sort(R,R+100,cmp);

//對(duì)全部元素R[0]~R[99]進(jìn)行排序sort(R,R+10,cmp);

//對(duì)前10個(gè)元素R[0]~R[9]進(jìn)行排序stable_sort(R,R+100,cmp);//對(duì)全部元素進(jìn)行穩(wěn)定排序8.7STL與排序STL之nth_elementnth_element的常用的方式：nth_element(first,nth,last[,cmp]);

表示從待排的閉開(kāi)區(qū)間[first,last)內(nèi)的元素中，按可選的比較函數(shù)參數(shù)cmp所指定的比較規(guī)則，選出第n（從0開(kāi)始）“小”的元素放在nth所指定的位置，且其左邊元素的關(guān)鍵字不大于、其右邊元素的關(guān)鍵字不小于nth所指元素。若cmp參數(shù)省略，則默認(rèn)為按非遞減序。first、last、nth可以是迭代器或地址參數(shù)。8.7STL與排序STL之nth_elementnth_element的簡(jiǎn)單示例#include<iostream>#include<algorithm>usingnamespacestd;voidPrint(intR[],intn);intmain(){

intA[12]={7,2,6,11,9,3,12,10,8,4,1,5};

//處理范圍[&A[0],&A[11]+1)，但只保證第6小的元素存放于A[6]

nth_element(A,A+6,A+12);//結(jié)果：521436789111012

Print(A,12);

return0;}8.7STL與排序STL之nth_elementnth_element的簡(jiǎn)單示例voidPrint(intR[],intn){

for(inti=0;i<n;i++)

{

if(i>0)cout<<"";

cout<<R[i];

}

cout<<endl;}8.7STL與排序STL之nth_elementnth_element與partial_sort的區(qū)別nth_element(A,A+6,A+12)：把所有12個(gè)元素中第6?。?xí)語(yǔ)中的第7?。┑姆诺紸[6]中。nth_element函數(shù)的時(shí)間復(fù)雜度約為O(n)，效率非常高，采用快速排序的劃分思想，故能保證前面的6個(gè)元素均不大于A[6]，而后面的n-7個(gè)元素均不小于A[6]。partial_sor