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

第10章排序排序是數(shù)據(jù)處理過程中經(jīng)常使用的一種重要的運(yùn)算，排序的方法有很多種，本章主要討論內(nèi)部排序的各種算法，并對(duì)每個(gè)排序算法的時(shí)間和空間復(fù)雜性以及算法的穩(wěn)定性等進(jìn)行了討論。10.1概述假設(shè)一個(gè)文件是由n個(gè)記錄R1，R2，…，Rn組成，所謂排序就是以記錄中某個(gè)(或幾個(gè))字段值不減“正序”(或不增“逆序”)的次序?qū)⑦@n個(gè)記錄重新排列，稱該字段為排序碼。能唯一標(biāo)識(shí)一個(gè)記錄的字段稱為關(guān)鍵字，關(guān)鍵字可以作為排序碼，但排序碼不一定要是關(guān)鍵字。根據(jù)排序過程中使用到的存儲(chǔ)介質(zhì)，可以將排序分成兩大類:內(nèi)部排序和外部排序。

內(nèi)部排序是指在排序過程中所有數(shù)據(jù)均放在內(nèi)存中處理，不需要使用外存的排序方法。而對(duì)于數(shù)據(jù)量很大的文件，在內(nèi)存不足的情況下，則還需要使用外存，這種排序方法稱為外部排序。排序碼相同的記錄，若經(jīng)過排序后，這些記錄仍保持原來的相對(duì)次序不變，稱這個(gè)排序算法是穩(wěn)定的。否則，稱為排序算法是不穩(wěn)定的。內(nèi)部排序算法的分類與性能分析：內(nèi)部排序算法大致可分為5類：(1)插入排序(2)交換排序(3)選擇排序(4)歸并排序(5)基數(shù)排序內(nèi)部排序算法的分類也可以從算法執(zhí)行所需的時(shí)間，即根據(jù)排序過程中的比較次數(shù)和移動(dòng)次數(shù)來劃分。一般可以分為3類：(1)簡單的排序算法，其時(shí)間復(fù)雜度為O(n2)；(2)先進(jìn)的排序算法，其時(shí)間復(fù)雜度為O(nlogn)；(3)基數(shù)排序，其時(shí)間復(fù)雜度為O(d·n)；內(nèi)部排序算法的分類與性能分析：采用不同的存儲(chǔ)結(jié)構(gòu)，對(duì)排序算法的記錄移動(dòng)次數(shù)也有影響。(1)如果采用線性表的順序存儲(chǔ)結(jié)構(gòu)(數(shù)組)，則在排序過程中記錄的移動(dòng)是避免不了的。(2)若采用線性鏈表，則可避免移動(dòng)記錄，只需修改指針即可。這種排序稱為鏈表排序。(3)記錄采用順序存儲(chǔ)，另設(shè)一個(gè)地址數(shù)組，排序時(shí)只對(duì)地址數(shù)組操作，不對(duì)記錄操作，這種排序稱為地址排序。(如：索引文件)在本章討論排序算法時(shí)，記錄存儲(chǔ)采用順序表結(jié)構(gòu)，記錄按排序碼（關(guān)鍵字）進(jìn)行“正序”排序，排序碼均為整數(shù)。有關(guān)定義如下：#defineMAXSIZE20//文件中記錄個(gè)數(shù)的最大值typedefintKeyType;//定義關(guān)鍵字類型為整數(shù)類型typedefstruct{KeyTypekey;//記錄的關(guān)鍵字InfoTypeotherinfo;//記錄中其它數(shù)據(jù)項(xiàng)}RecordType;//記錄類型

typedefstruct{RecordTyper[MAXSIZE+1];//r[0]閑置或用作“哨兵”單元intlength;//記錄的個(gè)數(shù)}SqList;//順序表的類型10.2插入排序插入排序的基本思想是:將待排序表中的記錄，逐個(gè)地按其關(guān)鍵字值的大小插入到目前已經(jīng)排好序的若干個(gè)記錄組成的表中的適當(dāng)位置，并保持新表中記錄有序。10.2.1直接插入排序直接插入排序算法的思路是:初始可認(rèn)為表中的第1個(gè)記錄己排好序，然后將第2個(gè)到第n個(gè)記錄依次插入已排序的記錄組成的表中。在對(duì)第i個(gè)記錄Ri進(jìn)行插入時(shí)，R1，R2，…，Ri-1已排序，將記錄Ri的關(guān)鍵字keyi與已經(jīng)排好序的關(guān)鍵字從右向左依次比較，找到Ri應(yīng)插入的位置，將該位置以后直到Ri-1各記錄順序后移，空出該位置讓Ri插入。一組記錄的關(guān)鍵字分別為:312，126，272，226，28，165，123初始時(shí)將第1個(gè)關(guān)鍵字作為已經(jīng)排好序的，把排好序的數(shù)據(jù)記錄放入中括號(hào)[]中，表示有序表，剩下的在中括號(hào)外，如下所示：[312]，126，272，226，28，165，123設(shè)前3個(gè)記錄的關(guān)鍵字已重新排列有序，構(gòu)成一個(gè)含有3個(gè)記錄的有序表:[126，272，312]，226，28，165，123現(xiàn)在要將第4個(gè)關(guān)鍵字226插入！直接插入排序的過程：[126，272，312]，226，28，165，123現(xiàn)在要將第4個(gè)關(guān)鍵字226插入！將待插入的關(guān)鍵字226和已經(jīng)有序的最后一個(gè)關(guān)鍵字312比較，因?yàn)榇迦氲年P(guān)鍵字226小于312，所以226肯定要置于312的前面，至于是否就是置于312的前一個(gè)位置，此時(shí)還不能確定，需要繼續(xù)向左比較；將所有大于待插入關(guān)鍵字226的那兩個(gè)關(guān)鍵字312和272依次后移一個(gè)位置，在空出的位置插入待排序的關(guān)鍵字226，得一含有4個(gè)記錄的有序表：[126，226，272，312]，28，165，123直接插入排序的過程(續(xù))：voidInsertSort(SqList&L){for(i=2;i<=L.length;i++)//依次插入從第2個(gè)開始的所有元素 if(L.r[i].key<L.r[i-1].key){ L.r[0]=L.r[i];//設(shè)置哨兵(將當(dāng)前記錄存入0元素) L.r[i]=L.r[i-1];//將有序表中的記錄后移一個(gè)位置 for(j=i-2;L.r[0].key<L.r[j].key;--j) L.r[j+1]=L.r[j];//將有序表中的記錄繼續(xù)后移一個(gè)位置 L.r[j+1]=L.r[0];//將當(dāng)前記錄插入到指定位置}}//InsertSort直接插入排序算法：該算法是穩(wěn)定的！設(shè)待排序的7記錄的關(guān)鍵字為{312，126，272，226，28，165，123}，直接插入排序算法的執(zhí)行過程如下：哨兵關(guān)鍵字初始（）[312]，126，272，226，28，165，123i=2：（126）[126，312]，272，226，28，165，123i=3：（272）[126，272，312]，226，28，165，123i=4：（226）[126，226，272，312]，28，165，123i=5：（28）[28，126，226，272，312]，165，123i=6：（165）[28，126，165，226，272，312]，123i=7：（123）[28，123，126，165，226，272，312]直接插入排序算法的執(zhí)行過程直接插入排序算法執(zhí)行時(shí)間的分析：最好的情況：即初始關(guān)鍵字開始就是正序(遞增)的情況下，該算法外循環(huán)共執(zhí)行n-1次，其循環(huán)體內(nèi)由于條件不成立，不需要進(jìn)行移動(dòng)操作。所以在最好情況下，直接插入排序算法的比較次數(shù)為(n-1)次，移動(dòng)次數(shù)為0次。最壞的情況：即初始關(guān)鍵字開始是逆序(遞減)的情況下，當(dāng)插入第i個(gè)關(guān)鍵字時(shí)，該算法內(nèi)循環(huán)要執(zhí)行i-1次，每次要移動(dòng)1個(gè)記錄，而外循環(huán)體要執(zhí)行n-l次，在循環(huán)體內(nèi)不含內(nèi)循環(huán)每次循環(huán)要進(jìn)行3次移動(dòng)操作，所以在最壞情況下，比較次數(shù)為2+…+n=(n+2)(n-1)/2，移動(dòng)次數(shù)為(3+4+…+n+1)=(n+4)(n-1)/2。若待排序的記錄以各種排列出現(xiàn)的概率相同，則可取上述最小值和最大值的平均值作為直接插入排序算法的比較次數(shù)和移動(dòng)次數(shù)，約為n2/4。由此，直接插入排序算法的時(shí)間復(fù)雜度為O(n2)。10.2.2其他插入排序1.折半插入排序根據(jù)插入排序的基本思想，在找第i個(gè)記錄的插入位置時(shí)，前i-l個(gè)記錄已排序，將第i個(gè)記錄的關(guān)鍵字key和已排序的前i-1個(gè)的中間位置記錄的關(guān)鍵字進(jìn)行比較，如果key小于中間位置記錄關(guān)鍵字，則可以在前半部繼續(xù)使用二分法查找，否則在后半部繼續(xù)使用二分法查找，直到查找范圍為空，即可確定key的插入位置。當(dāng)n較大時(shí)，折半插入排序的比較次數(shù)遠(yuǎn)少于直接插入排序的平均比較次數(shù)，但二者所要進(jìn)行的移動(dòng)次數(shù)相等，故折半插入排序的時(shí)間復(fù)雜度也是O(n2)。voidBInsertSort(SqList&L){for(i=2;i<=L.length;i++){//依次插入從第2個(gè)開始的所有元素 L.r[0]=L.r[i];//保存待插入的元素 low=1;high=i-1; while(low<=high){//在r[low..high]中查找有序插入的位置 mid=(low+high)/2;//折半if(L.r[0].key<L.r[mid].key)high=mid-1; elselow=mid+1; }//while for(j=i-1;j>=low;--j)L.r[j+1]=L.r[j];//記錄后移 L.r[low]=L.r[0];//插入}//for}//BInsertSort折半插入排序算法2.2-路插入排序2-路插入排序是在折半插入排序的基礎(chǔ)，對(duì)插入排序中移動(dòng)元素的操作進(jìn)行改進(jìn)。其基本思想是：將插入?yún)^(qū)域分成大致等長的兩段，選擇性地插入到其中一段。具體過程如下：01234563428817922165534firstfinal3428firstfinal348128firstfinal34798128firstfinal3479812228firstfinal347981162228firstfinal34557981162228firstfinal3.表插入排序折半插入排序比較次數(shù)通常比直接插入排序的比較次數(shù)少，但移動(dòng)次數(shù)相等。表插入排序?qū)⒃诓贿M(jìn)行記錄移動(dòng)的情況下，利用存儲(chǔ)結(jié)構(gòu)有關(guān)信息的改變來達(dá)到排序的目的。給每個(gè)記錄附設(shè)一個(gè)所謂的指針域next，它的類型為整型，表插入排序的思路：在插入第i個(gè)記錄Ri時(shí)，R1，R2，…，Ri-1已經(jīng)通過各自的指針域next按關(guān)鍵字不減的次序連接成一個(gè)（靜態(tài)鏈）表，將記錄Ri的關(guān)鍵字keyi與表中已經(jīng)排好序的關(guān)鍵字從表頭向右、或稱向后依次比較，找到Ri應(yīng)插入的位置，將其插入在表中，使表中各記錄的關(guān)鍵字仍然有序。#defineMAXSIZE100/*文件中記錄個(gè)數(shù)的最大值*/typedefstruct{RecordTyperc; //記錄項(xiàng)intnext; //指針項(xiàng)}SLNode; //表結(jié)點(diǎn)類型typedefstruct{SLNoder[MAXSIZE]; //0號(hào)單元為表頭結(jié)點(diǎn)intlength; //鏈表長度(記錄數(shù))}SLinkList; //靜態(tài)鏈表類型表插入排序的存儲(chǔ)結(jié)構(gòu)初始時(shí)，r[0].next用于存放表中第1個(gè)記錄的下標(biāo)，r[0].next的值為1，排序結(jié)束時(shí)，r[0].next中存放的是所有關(guān)鍵字中值最小的對(duì)應(yīng)記錄的下標(biāo)，其它的關(guān)鍵字記錄通過各自的指針域next按不減的次序連接成一個(gè)（靜態(tài)鏈）表，最大的關(guān)鍵字記錄的next為0。具體過程如下：表插入排序算法4938659776132749201------初始012345678i=2493865977613274923140----i=34938659776132749231504---49386597761327496315042--i=6493865977613274963150472-i=7493865977613274910-------49386597761327492310-----i=44938659776132749681504723i=8i=5012345678voidTableInsertSort(SLinkList&SL){SL.r[0].next=1;SL.r[1].next=0;//第1個(gè)元素為有序靜態(tài)表for(i=2;i<=SL.length;i++){//依次插入從第2個(gè)開始的所有元素 q=0;p=SL.r[0].next;//p指向表中第1個(gè)元素，q指向p的前驅(qū)元素位置 while(p!=0&&(SL.r[p].rc.key<SL.r[i].rc.key){//找插入位置 q=p;p=SL.r[p].next;//繼續(xù)查找 }//while SL.r[i].next=p; SL.r[q].next=i;//將第i個(gè)元素插入q和p所指向的元素之間}//for}//TableInsertSort表插入排序算法(續(xù))10.2.3Shell(希爾)排序Shell排序的基本思想是：對(duì)n個(gè)記錄進(jìn)行排序，首先取一個(gè)整數(shù)d<n，將這n個(gè)記錄分成d組，所有位置相差為d的倍數(shù)的記錄分在同一組，在每組中使用直接插入排序進(jìn)行組內(nèi)排序，然后縮小d的值，重復(fù)進(jìn)行分組和組內(nèi)排序，一直到d=1結(jié)束。因此又稱“縮小增量排序”。設(shè)待排序的9記錄的關(guān)鍵字為{312，126，274，226，28，85，28，165，123}，開始取d=9/2=4，以后每次讓d縮小一半，其排序過程為：初始狀態(tài)：312126274226288528165123第1步：d=4288528165123126274226312第2步：d=2288528126123165274226312第3步：d=1282885123126165226274312voidShellSort(SqList&L){d=L.length/2;while(d>=1){ for(i=d+1;i<=L.length;i++){ //從第d+1個(gè)元素開始,將所有元素有序插入相應(yīng)分組中 L.r[0]=L.r[i];//保存第i個(gè)元素 j=i-d;//向前找插入位置 while(L.r[0].key<L.r[j].key&&j>0){//找插入位置并后移 L.r[j+d]=L.r[j];//后移 j=j-d; //繼續(xù)向前查找 }//while L.r[j+d]=L.r[0];//插入第i個(gè)元素 }//for d=d/2;}//while}//ShellSortShell排序算法Shell排序的分析是一個(gè)復(fù)雜的數(shù)學(xué)問題，算法的時(shí)間復(fù)雜度與增量d有關(guān)。一般是O(n3/2)。對(duì)于增量d，盡量取素?cái)?shù)，且最后d=1。10.3交換排序交換排序的基本思路：對(duì)待排序記錄兩兩進(jìn)行關(guān)鍵字比較，若不滿足排序順序則交換這對(duì)記錄，直到任何兩個(gè)記錄的關(guān)鍵字都滿足排序要求為止。冒泡排序(BubbleSort)的基本思想為：第1趟，對(duì)所有記錄從左到右每相鄰兩個(gè)記錄的關(guān)鍵字進(jìn)行比較，如果這兩個(gè)記錄的關(guān)鍵字不符合排序要求，則進(jìn)行交換，這樣一趟做完，將關(guān)鍵字最大者放在最后一個(gè)位置；第2趟，對(duì)剩下的n-l個(gè)待排序記錄重復(fù)上述過程，又將一個(gè)關(guān)鍵字放于最終位置，反復(fù)進(jìn)行n-l次，可將n-l個(gè)關(guān)鍵字對(duì)應(yīng)的記錄放至最終位置，剩下的即為關(guān)鍵字最小的記錄，它在第1的位置處。如果在某一趟中，沒有發(fā)生交換，則說明此時(shí)所有記錄已經(jīng)按排序要求排列完畢，排序結(jié)束。10.3.1冒泡排序voidBubbleSort(SqList&L){i=1;done=1;while(i<=L.length&&done){ //最多進(jìn)行l(wèi)ength次冒泡，如沒有發(fā)生交換則結(jié)束 done=0; for(j=1;j<=L.length-i;j++) if(L.r[j+1].key<L.r[j].key){//兩個(gè)記錄不符合排序規(guī)則 L.r[0]=L.r[j]; //交換兩個(gè)記錄位置 L.r[j]=L.r[j+1]; L.r[j+1]=L.r[0]; done=1; }//if i++;}//while}//BubbleSort冒泡排序算法該算法是穩(wěn)定的！時(shí)間復(fù)雜度與插入算法一樣。例如：待排序的9個(gè)記錄的關(guān)鍵字序列為{312，126，272，226，8，165，123，12，28}，使用冒泡排序算法進(jìn)行的排序過程如下圖所示：10.3.2快速排序快速排序(QuickSort)是對(duì)冒泡排序的一種改進(jìn)，它的基本思想是：通過一趟排序?qū)⒋判虻挠涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均小于另一部分記錄的關(guān)鍵字，然后分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序?？焖倥判虻膶?shí)現(xiàn)方法是：從n個(gè)待排序的記錄中任取一個(gè)記錄(不妨取第1個(gè)記錄，該記錄稱為樞軸或支點(diǎn))，將該記錄放置于排序后它最終應(yīng)該放的位置，使它前面的記錄關(guān)鍵字都不大于它的關(guān)鍵字，而后面的記錄關(guān)鍵字都大于它的關(guān)鍵字，這個(gè)過程稱為一趟快速排序（或一次劃分）。然后對(duì)前、后兩部分待排序記錄重復(fù)上述過程，可以將所有記錄放于排序成功后的相應(yīng)位置，排序即告完成。一趟快速排序(劃分)的具體做法是：附設(shè)兩個(gè)指針low和high，其初值分別是1和L.length，設(shè)樞軸記錄的關(guān)鍵字為pivotkey，其初值為low指針?biāo)赣涗浀年P(guān)鍵字。首先從high位置起向前搜索找到第一個(gè)關(guān)鍵字小于pivotkey的記錄和樞軸記錄互相交換，然后從low所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于pivotkey的記錄和樞軸記錄互相交換，重復(fù)這兩步直至low=high為止。具體算法如下：1.快速排序的實(shí)現(xiàn)intPartition(SqList&L,intlow,inthigh){pivotkey=L.r[low].key;while(low<high){ while(low<high&&L.r[high].key>=pivotkey)--high; L.r[low]?L.r[high];//兩個(gè)記錄互換位置 while(low<high&&L.r[low].key<=pivotkey)++low; L.r[low]?L.r[high];//兩個(gè)記錄互換位置}returnlow;}//Partition設(shè)待排序的7個(gè)記錄的關(guān)鍵字序列為{126，272，12，165，123，12，28}，一次劃分的過程如圖所示：初始狀態(tài)：pivoekey=126126272121651231228lowhigh282721216512312126lowhigh第1次循環(huán)281261216512312272lowhigh281212165123126272lowhigh第2次循環(huán)281212126123165272lowhigh281212123126165272lowhigh第3次循環(huán)281212123126165272lowhigh快速排序是不穩(wěn)定的！因此，上述7個(gè)記錄的關(guān)鍵字{126，272，12，165，123，12，28}經(jīng)快速排序后的結(jié)果如下：第1次劃分后：{28，12，12，123}，126，{165，272}第2次劃分后：{12，12}，28，{123}，126，{165，272}第3次劃分后：{12，12}，28，{123}，126，165，{272}第4次劃分后：12，{12}，28，{123}，126，165，{272}voidQuickSort(SqList&L,intlow,inthigh){if(low<high){ pivotloc=Partition(L,low,high); QuickSort(L,low,pivotloc-1);//對(duì)低端子表遞歸調(diào)用本函數(shù) QuickSort(L,pivotloc+1,high);//對(duì)高端子表遞歸調(diào)用本函數(shù)}}//QuickSort2.快速排序算法intPartition(SqList&L,intlow,inthigh){//改進(jìn)的一趟排序算法L.r[0]=L.r[low];pivotkey=L.r[low].key;while(low<high){ while(low<high&&L.r[high].key>=pivotkey)--high; L.r[low]=L.r[high];//兩個(gè)記錄互換位置 while(low<high&&L.r[low].key<=pivotkey)++low; L.r[high]=L.r[low];//兩個(gè)記錄互換位置}L.r[low]=L.r[0];returnlow;}//Partition快速排序算法的時(shí)間復(fù)雜度是O(nlogn)。是該量級(jí)平均性能最好的算法。10.4選擇排序選擇排序的基本思想是：每次從待排序的文件中選擇出關(guān)鍵字最小的記錄，將該記錄放于已排序文件的指定位置，直到已排序文件記錄個(gè)數(shù)等于初始待排序文件的記錄個(gè)數(shù)為止。10.4.1簡單(直接)選擇排序首先從所有n個(gè)待排序記錄中選擇關(guān)鍵字最小的記錄，將該記錄與第1個(gè)記錄交換，再從剩下的n-l個(gè)記錄中選出關(guān)鍵字最小的記錄和第2個(gè)記錄交換。重復(fù)這樣的操作直到剩下2個(gè)記錄時(shí)，再從中選出關(guān)鍵字最小的記錄和第n-1個(gè)記錄交換。剩下的那1個(gè)記錄肯定是關(guān)鍵字最大的記錄，這樣排序即告完成。voidSimpleSelectSort(SqList&L){for(i=1;i<=L.length-1;i++){ k=i;//記下當(dāng)前最小元素的位置 for(j=i+1;j<=L.length;j++)//向右查找更小的元素 if(L.r[j].key<L.r[k].key)k=j;//修改當(dāng)前最小元素的位置 if(k!=i){//如果k不等于i，則將第k、i個(gè)元素交換 L.r[0]=L.r[k];//以第0個(gè)元素作為中間單元進(jìn)行交換 L.r[k]=L.r[i]; L.r[i]=L.r[0]; }//if}//for}//SimpleSelectSort簡單(直接)選擇排序算法該算法是不穩(wěn)定的！且最好最壞情況的時(shí)間復(fù)雜度均為O(n2)10.4.2樹型選擇排序樹形選擇排序(又稱錦標(biāo)賽排序)是一種按淘汰賽的思想進(jìn)行選擇排序的方法。首先對(duì)n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，然后對(duì)其中的較小者再進(jìn)行兩兩比較，如此重復(fù)，直到選出最小關(guān)鍵字的記錄為止。樹形選擇排序的過程如下圖所示。38131338384965976513137627502710.4.2樹型選擇排序(續(xù))當(dāng)輸出最小關(guān)鍵字后，根據(jù)關(guān)系的傳遞性，欲選出次小關(guān)鍵字，僅需將葉子結(jié)點(diǎn)中的最小關(guān)鍵字(13)改為“最大值”，然后從該葉子結(jié)點(diǎn)開始，和其左(或右)關(guān)鍵字進(jìn)行比較，修改從葉子結(jié)點(diǎn)到根的路徑上各結(jié)點(diǎn)的關(guān)鍵字，則根結(jié)點(diǎn)的關(guān)鍵字為次小關(guān)鍵字。同理，可以依此選出從小到大的所有關(guān)鍵字。38272738384965976576∞76275027該排序方法的時(shí)間復(fù)雜度為O(nlogn)10.4.3堆排序樹形選擇排序尚有輔助存儲(chǔ)空間較多、和“最大值”進(jìn)行多余的比較等缺點(diǎn)。為了彌補(bǔ)，Willioms和Floyd在1964年提出的稱為堆排序的選擇排序算法。堆是一個(gè)序列{k1,k2,…,kn}，它滿足下面的條件：ki≤k2i并且ki≤k2i+1，當(dāng)i=1,2,…,n/2（小頂堆）或者：ki≥k2i并且ki≥k2i+1，當(dāng)i=1,2,…,n/2（大頂堆）采用順序方式存儲(chǔ)這個(gè)序列，就可以將這個(gè)序列的每一個(gè)元素ki看成是一顆有n個(gè)結(jié)點(diǎn)的完全二叉樹的第i個(gè)結(jié)點(diǎn)，其中k1是該二叉樹的根結(jié)點(diǎn)。把堆對(duì)應(yīng)的一維數(shù)組(即該序列的順序存儲(chǔ)結(jié)構(gòu))看作一棵完全二叉樹的順序存儲(chǔ)，那么堆的特征可解釋為：完全二叉樹中任一分支結(jié)點(diǎn)的值都小于等于(或大于等于)它的左、右兒子結(jié)點(diǎn)的值。堆的元素序列中的第一個(gè)元素k1（即對(duì)應(yīng)的完全二叉樹根結(jié)點(diǎn)）的值是所有元素中值最小的(或最大的)。堆排序方法就是利用這一點(diǎn)來選擇最小(最大)元素。1224308553475391(a)小頂堆（逆序排序）大頂堆（正序排序）96278311389(b)1112302453855347919683273811911在確定n個(gè)元素中最小值或最大值（堆頂元素）之后，若再將剩余n-1個(gè)元素的序列重新建成一個(gè)堆，則又可得到次小值或次大值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列，這個(gè)過程稱之為堆排序。由此可見，實(shí)現(xiàn)堆排序要解決兩個(gè)問題：如何將一個(gè)無序序列建成一個(gè)堆？在交換堆頂元素后，如何調(diào)整剩余元素成為一個(gè)新的堆？

假設(shè)將待排序列A作遞減（逆序）排序，堆排序的過程如下：將待排序列A[1…n]調(diào)整為一個(gè)小頂堆；將堆頂元素A[1]（即最小排序碼）與堆尾元素（即堆中最后一個(gè)元素）交換，從堆中除去堆尾元素（即最小排序碼），然后調(diào)整堆中剩余元素，使它們恢復(fù)堆屬性；重復(fù)進(jìn)行步驟(2)，直至堆中只有1個(gè)元素。下面先討論第二個(gè)問題。例如有一個(gè)小頂堆，當(dāng)交換堆頂元素后，堆的調(diào)整過程如下。我們稱這個(gè)自堆頂向葉子的調(diào)整過程為“篩選”。1224308553475391(1)調(diào)整堆9124308553475312(1)將12與91交換12302453855347919130245385534712將24與91交換2447308553915312(2)2430475385539112調(diào)整堆9147308553245312(2)9130475385532412將30與53交換3053479185532412調(diào)整堆5347538591243012(3)53534791853024123047538591245312(3)將47與85交換4753538591243012(4)4753539185302412調(diào)整堆8553534791243012(4)8553539147302412將53與91交換5353854791243012(5)5385539147302412調(diào)整堆9153854753243012(5)9185535347302412將53與91交換5391854753243012(6)5385915347302412調(diào)整堆9153854753243012(6)9185535347302412將85與91交換8553914753243012(7)8591535347302412排序結(jié)束9153854753243012(7)9185535347302412下面討論第一個(gè)問題：如何建“堆”？從一個(gè)無序序列建堆的過程就是一個(gè)“篩選”的過程。若將此無序序列看成一棵完全二叉樹，則最后一個(gè)非終端結(jié)點(diǎn)是第n/2個(gè)元素，“篩選”的過程就從此元素開始。例如：無序序列為{85,53,47,91,30,53,24,12}，其對(duì)應(yīng)的完全二叉樹為：8547533091245312(1)篩選從此結(jié)點(diǎn)開始91與12交換8547533012245391(2)47與24交換855347913053241285534712305324918524533012475391(3)53與12交換8524123053475391(4)85與12,再與30交換855324123053479185122453305347911224308553475391(5)最后得到的“堆”1230245385534791堆排序算法見p-282堆排序的時(shí)間復(fù)雜度：O(nlogn)。堆排序僅需一個(gè)記錄大小供交換用的輔助存儲(chǔ)空間。

歸并排序是又一類不同的排序方法。所謂“歸并”就是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。

歸并排序的基本思路是：將初始序列中的n個(gè)記錄看成是n個(gè)有序的子序列，每個(gè)子序列的長度為1，然后兩兩歸并，得到[n/2]個(gè)長度為2或1的有序子序列，再兩兩歸并，……，如此重復(fù)，直至得到一個(gè)長度為n的有序序列為止。這種排序方法稱為2-路歸并排序。10.5歸并排序初始關(guān)鍵字：[49][38][65][97][76][38][27]2-路歸并排序的過程一趟歸并之后：[38，49][65，97][38，76][27]二趟歸并之后：[38，49，65，97][27，38，76]三趟歸并之后：[27，38，38，49，65，76，97]2-路歸并排序的核心操作是將一維數(shù)組中前后相鄰的兩個(gè)有序表歸并成一個(gè)有序表。其算法見p-283。2-路歸并排序的算法

基數(shù)排序(RadixSort)不同于前面介紹的排序方法，它無需比較關(guān)鍵字，二是通過“分組”與“收集”兩個(gè)過程來完成排序任務(wù)，其中借助了多關(guān)鍵字排序的實(shí)現(xiàn)。即將排序的關(guān)鍵字看成是有多個(gè)關(guān)鍵字分量復(fù)合而成，如整數(shù)可視為若干數(shù)位的集合，每個(gè)數(shù)位的取值范圍為0~9（基數(shù)為10），然后根據(jù)各關(guān)鍵字分量從低位到高位進(jìn)行“分組”、“收集”完成排序。

例如，要對(duì)24,2,56,102,98,4,81,112進(jìn)行基數(shù)排序，過程如下：（1）準(zhǔn)備工作：將待排序的關(guān)鍵字編成統(tǒng)一長度的排序碼：024,002,056,102,098,004,081,112；并根據(jù)基數(shù)設(shè)置10個(gè)的隊(duì)列（分別為0~9）；（2）根據(jù)各關(guān)鍵字的個(gè)位數(shù)，將各關(guān)鍵字依次進(jìn)入相應(yīng)的隊(duì)列，完成第一次“分組”；然后將0~9個(gè)隊(duì)列中的關(guān)鍵字依次出隊(duì)，完成第一次“收集”；（3）重復(fù)第（2）步的過程，依次完成對(duì)“十位數(shù)”、“百位數(shù)”的“分組”與“收集”，完成整個(gè)排序。10.6基數(shù)排序基數(shù)排序過程實(shí)例（按個(gè)位數(shù)分組、收集）隊(duì)列0108120021020021123402456056780989待排序的關(guān)鍵字：024,002,056,102,098,002,081,112；分組收集收集后的關(guān)鍵字：081,002,102,002,112,024,056,098；基數(shù)排序過程實(shí)例（按十位數(shù)分組、收集）隊(duì)列0002102002111220243450566780819098待排序的關(guān)鍵字：081,002,102,002,112,024,056,098

；分組收集收集后的關(guān)鍵字：002,102,002,112,024,056,081,098；基數(shù)排序過程實(shí)例（按百位數(shù)分組、收集）隊(duì)列0002002024056081098110211223456789待排序的關(guān)鍵字：002,102,002,112,024,056,081,098

；分組收集收集后的關(guān)鍵字：002,002,024,056,081,098,102,112；內(nèi)部排序算法的穩(wěn)定性分析假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對(duì)次序保持不變，即在原序列中，Ri=Rj，且Ri在Rj之前，而在排序后的序列中，Ri仍在Rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。(1)冒泡排序

冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。我們知道，冒泡排序的交換條件是：a[j]>a[j+1]或者a[j]<a[j+1]很明顯不包括相等的情況，所以如果兩個(gè)元素相等，他們不會(huì)交換；如果兩個(gè)相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個(gè)相鄰起來，這時(shí)候也不會(huì)交換，所以相同元素的前后順序不會(huì)改變，所以冒泡排序是一種穩(wěn)定排序算法。內(nèi)部排序算法的穩(wěn)定性分析(2)選擇排序

選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的，比如給第一個(gè)位置選擇最小的，在剩余元素里面給第二個(gè)元素選擇第二小的，依次類推，直到第n-1個(gè)元素，第n個(gè)元素不用選擇了，因?yàn)橹皇Ｏ滤粋€(gè)最大的元素了。那么，在一趟選擇，如果當(dāng)前元素比一個(gè)元素小，而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。比較拗口，舉個(gè)例子，序列5

8

5

2

9，

我們知道第一遍選擇第1個(gè)元素5會(huì)和2交換，那么原序列中2個(gè)5的相對(duì)前后順序就被破壞了，所以選擇排序是一個(gè)不穩(wěn)定的排序算法。內(nèi)部排序算法的穩(wěn)定性分析(3)插入排序

插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個(gè)元素。當(dāng)然，剛開始這個(gè)有序的小序列只有1個(gè)元素，就是第一個(gè)元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經(jīng)有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果碰見一個(gè)和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。即和冒泡排序一樣：a[j]>a[j+1]或者a[j]<