第10章內部排序學習目的與要求：1.深刻理解排序的定義和各種排序方法的特點,并能加以靈活應用;2.熟練掌握各種排序方法的執(zhí)行過程；3.熟練掌握各種排序方法的時間復雜度的分析方法，從“關鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時間性能;4.理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應用的排序方法必須是穩(wěn)定的。第10章內部排序學習目的與要求：1基本內容一、概述二、插入排序三、交換排序四、選擇排序五、歸并排序六、基數(shù)排序七、各種排序方法的比較基本內容一、概述2一、概述1．基本概念排序：將數(shù)據(jù)元素(或記錄)的一個任意序列,重新排列成一個按關鍵字有序的序列。排序方法的穩(wěn)定性：對關鍵字相同的數(shù)據(jù)元素，排序前后它們的領先關系保持不變，則稱該排序方法是穩(wěn)定的；反之，稱該排序方法是不穩(wěn)定的。內部排序：待排序記錄存放在計算機的內存中進行的排序。一、概述1．基本概念排序：將數(shù)據(jù)元素(或記錄)的一個任意序列3外部排序：待排序記錄的數(shù)量很大，以致內存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序。排序的時間開銷：排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。算法運行時間代價的估算一般都按平均情況進行估算。對于那些受記錄關鍵字序列初始排列及記錄個數(shù)影響較大的，需要按最好情況和最壞情況進行估算。外部排序：待排序記錄的數(shù)量很大，以致內存一次不能容納全部記錄42．排序的分類按排序過程依據(jù)的不同原則進行分類：交換排序選擇排序歸并排序計數(shù)排序插入排序按工作量進行分類：先進的排序方法，其時間復雜度為O(nlog2n)簡單的排序方法,其時間復雜度為O(n2)基數(shù)排序基數(shù)排序，其時間復雜度為O(d·n)2．排序的分類按排序過程依據(jù)的不同原則進行分類：交換排序選擇53．排序的基本操作和記錄的存儲方式排序過程中需要的兩種基本操作：（1）比較關鍵字的大??；（2）將記錄從一個位置移至另一個位置。待排序記錄序列可有下列三種存儲方式：（1）記錄存放在一組連續(xù)的存儲單元中；類似于線性表的順序存儲結構，記錄次序由存儲位置決定，實現(xiàn)排序需移動記錄。（2）記錄存放在靜態(tài)鏈表中；記錄次序由指針指示，實現(xiàn)排序不需移動記錄，僅需修改指針?！溑判颍?）記錄本身存放在一組連續(xù)的存儲單元中，同時另設指示各個記錄存儲位置的地址向量，排序過程中不移動記錄本身，而移動地址向量中相應記錄的地址。排序結束后再根據(jù)地址調整記錄的存儲位置?！刂放判?．排序的基本操作和記錄的存儲方式排序過程中需要的兩種基本操64．待排序記錄的數(shù)據(jù)類型#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;InfoTypeotherinfo;}RcdType;typedefstruct{RedTyper[MAXSIZE+1];//0單元作為哨兵intlength;}SqList;4．待排序記錄的數(shù)據(jù)類型#defineMAXSIZE27二、插入排序1．直接插入排序2．折半插入排序3．2-路插入排序4．表插入排序5．希爾排序插入排序的基本方法是：每步將一個待排序的記錄，按其關鍵字大小，插入到前面已經(jīng)排好序的一組記錄的適當位置上，直到記錄全部插入為止。二、插入排序1．直接插入排序插入排序的基本方法是：每步將一個81．直接插入排序基本思想：當插入第i(i1)個記錄時，前面的r[1],r[2]，…，r[i-1]已經(jīng)排好序。這時，用r[i]的關鍵字與r[i-1]，r[i-2]，…的關鍵字順序進行比較，找到插入位置即將r[i]插入，原來位置上之后的所有記錄依次向后順移。1．直接插入排序基本思想：9例49386597761327（）i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=7(133849657697)27j9727j76j65j49j38j排序結果：(13273849657697)例49386597710直接插入排序的算法voidInsertSort(SqList&L){//對待排序序列L進行直接插入排序for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){

L.r[0]=L.r[i];//復制為哨兵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];//記錄插入}}//InsertSort直接插入排序的算法voidInsertSort(SqLi11算法評價記錄的比較次數(shù)記錄的移動次數(shù)最好情況最壞情況0時間復雜度：T(n)=O(n2)結論：空間復雜度：S(n)=O(1)直接插入排序是一個穩(wěn)定的排序方法。算法評價記錄的比較次數(shù)記錄的移動次數(shù)最好情況最壞情況0時間復122．折半插入排序基本思想：利用直接插入排序的思想，只是在排序過程中，為減少查找次數(shù)，對已排好序的序列r[1],r[1],…,r[i-1]，利用折半查找法尋找r[i]的插入位置。例

(30)1370853942620i=213(1330)70853942620…...i=76(6133039427085)202．折半插入排序基本思想：例(30)13i=820(6133039427085)20lhmi=820(6133039427085)20lhmi=820(6133039427085)20l,m,hi=820(6133039427085)20lhi=820(613203039427085)i=820(6133014算法描述如下：voidBin_InsertSort(SqList&L){//對待排序序列L進行折半插入排序for(i=2;i<=L.length;++i){low=1;high=i-1;while(low<=high){mid=(low+high)/2;if(r.[mid].key<=r[0].key)high=mid-1;elselow=mid+1;}for(j=i-1;j>h;j--)L.r[j+1]=L.r[j];//記錄后移L.r[j+1]=L.r[0];//記錄插入}}//Bin_InsertSort算法描述如下：voidBin_InsertSort(Sq15算法分析折半插入排序減少了關鍵字間的比較次數(shù)（由O(n2)下降到O(nlog2n))。折半插入排序的記錄移動次數(shù)仍為O(n2)。折半插入排序的時間復雜度仍為O(n2)，空間復雜度仍為O(１)。折半插入排序是一個穩(wěn)定的排序方法。算法分析折半插入排序減少了關鍵字間的比較次數(shù)（由O(n2)下163．2-路插入排序基本思想：利用直接插入排序的思想，只是在排序過程中，為減少記錄的移動次數(shù)，但需要n個記錄的輔助空間。其做法是：另設一個和L.r同類型的數(shù)組d，首先將L.r[1]賦給d.r[1]，并將d.r[1]看成是在排好序的序列中處于中間位置的記錄，然后從L.r中第二個記錄起依次到d.r[1]之前或之后的有序序列中。例

301370853942620排序過程中d的狀態(tài)變化如下：i=1(30)firstfinali=2(30)13firstfinal3．2-路插入排序基本思想：利用直接插入排序的思想，只是在排17

301370853942620i=3(30)7013firstfinali=4(30)708513firstfinali=5(30)39708513firstfinali=6(30)3942708513firstfinali=7(30)39427085613firstfinali=8(30)3942708561320firstfinal3013708518算法描述如下：voidTwo_InsertSort(SqListL，SqList&D){//對待排序序列L進行2-路插入排序D.r[1]=L.r[1];D.length=L.length;first=final=1;for(i=2;i<=L.length;i++){x=L.r[i].key;if(x<D.r[1].key)if(first==1){D.r[D.length]=L.r[i];first=D.length;}else{low=first;high=D.length;while(low<=high){mid=(low+high)/2;if(x<D.r[mid].key)high=mid-1;elselow=mid+1;}算法描述如下：voidTwo_InsertSort(Sq19for(k=first;k<=high+1;k++)D.r[k-1]=D.r[k];D.r[high+1]=L.r[i];first--;}elseif(final==1){final++;D.r[final]=L.r[i];}else{low=2;high=final;while(low<=high){mid=(low+high)/2;if(x<D.r[mid].key)high=mid-1;elselow=mid+1;}for(k=fnal;k>=high+1;k++)D.r[k+1]=D.r[k];D.r[high+1]=L.r[i];fianl++;}}//for}//Two_InsertSortf20算法分析2-路插入排序減少了關鍵字間的比較次數(shù)(小于nlog2n)。2-路插入排序減少了記錄移動次數(shù)，約為n2/8。2-路插入排序的時間復雜度仍為O(n2)，但空間復雜度為O(n)。2-路插入排序是一個穩(wěn)定的排序方法。算法分析2-路插入排序減少了關鍵字間的比較次數(shù)(小于nlog214．表插入排序表插入排序采用了靜態(tài)鏈表的存儲結構，其排序過程如下：首先將靜態(tài)鏈表中數(shù)組下標為1的分量（結點）和表頭結點構成一個循環(huán)鏈表，然后依次將下標為2至n的分量（結點）按記錄關鍵字非遞減有序插入到循環(huán)鏈表中。表插入排序的基本操作仍是將一個記錄插入到已排好序的有序表中。和直接插入排序相比，不同之處僅是以修改2n次指針值代替移動記錄，排序過程中所需進行的關鍵字間的比較次數(shù)相同。因此，表插入排序的時間復雜度仍是O(n2)。4．表插入排序表插入排序采用了靜態(tài)鏈表的存儲結構，其排序過程225．希爾排序希爾排序方法又稱為“縮小增量”排序?；舅枷耄合葘⒄麄€待排序記錄序列分割成若干子序列分別進行直接插入排序，待整個序列“基本有序”時，再對全體記錄進行一次直接插入排序。5．希爾排序希爾排序方法又稱為“縮小增量”排序?；舅枷耄?3例初始：4938659776132748554取d1=5一趟分組：49

38

65

97

76

13

27

48

55

4一趟排序：13

27

48

55

4

49

38

65

97

76取d2=3二趟分組：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d3=1三趟分組：1344838274955659776三趟排序：4132738484955657697例初始：4938659724希爾排序算法分析子序列的構成不是簡單的“逐段分割”，而是將相隔某個增量的記錄組成一個子序列；希爾排序可提高排序速度，因為關鍵字較小的記錄跳躍式前移，在進行最后一趟增量為1的插入排序時，序列已基本有序;增量序列取法有多種：1)沒有除1以外的公因子2)最后一個增量值必須為1時間復雜度是所取增量序列的函數(shù)，但至今沒人能夠給出完整的數(shù)學分析。希爾排序是一個不穩(wěn)定的排序方法。希爾排序算法分析子序列的構成不是簡單的“逐段分割”，而是將相25三、交換排序1．起泡排序(BubbleSort)2．快速排序(QuickSort)三、交換排序1．起泡排序(BubbleSort)261．起泡排序(BubbleSort)基本過程：1)將第一個記錄的關鍵字與第二個記錄的關鍵字進行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止——第一趟冒泡排序，結果關鍵字最大的記錄被安置在最后一個記錄上;2)對前n-1個記錄進行第二趟冒泡排序，結果使關鍵字次大的記錄被安置在第n-1個記錄位置;3)重復上述過程，直到“在一趟排序過程中沒有進行過交換記錄的操作”為止。1．起泡排序(BubbleSort)基本過程：27例：49383838381313384949491327276565651327383897761327494976132749

49132749

652749

76

49

97初始關鍵字第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后第六趟排序后例：4938383828算法分析時間復雜度最好情況（正序）最壞情況（逆序）比較次數(shù)移動次數(shù)n-10T(n)=O(n2)空間復雜度：S(n)=O(1)起泡排序是一個穩(wěn)定的排序方法算法分析時間復雜度最好情況（正序）最壞情況（逆序）比較次數(shù)移292．快速排序(QuickSort)對冒泡排序的一種改進基本思想：通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續(xù)分別進行排序，以達到整個序列有序。2．快速排序(QuickSort)對冒泡排序的一種改進基本30排序過程：1)初始時令i=s,j=t;2)首先從j所指位置向前搜索第一個關鍵字小于pivot的記錄，并和rp交換;3)再從i所指位置起向后搜索，找到第一個關鍵字大于pivot的記錄，和rp交換;4)重復上述兩步，直至i==j為止;（此時整個序列被分成有序的前后兩塊）5)再分別對兩個子序列進行快速排序，直到每個子序列只含有一個記錄為止。對r[s……t]中記錄進行一趟快速排序，附設兩個指針i和j，設樞軸記錄rp=r[s]，pivot=rp.key排序過程：1)初始時令i=s,j=t;對31快速排序舉例初始關鍵字：{49，38，65，97，76，13，27，49}pivotkey491次交換后：{27，38，65，97，76，13，，49}ijijji2次交換后：{27，38，，97，76，13，65，49}ijj3次交換后：{27，38，13，97，76，，65，49}iji4次交換后：{27，38，13，，76，97，65，49}jij一趟完成后：{27，38，13，49，76，97，65，49}快速排序舉例初始關鍵字：{49，38，65，97，76，1332一趟完成后：{27，38，13，49，76，97，65，49}分別進行快速排序：{13

27

3849

4965

76

97}快速排序結束：{13

27

3849

49

65

76

97}一趟完成后：{27，38，13，49，76，97，65，4933快速排序算法描述：intPartition(SqList&L,intlow,inthigh){//對順序表L進行一趟快速排序，返回樞軸記錄所在的位置

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];//將比pivotkey小的記錄移到低端while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];//將比pivotkey大的記錄移到高端}L.r[low]=l.r[0];returnlow;}快速排序算法描述：intPartition(SqList34voidQsort(SqList&L,intlow,inthigh){//對順序表L的子序列L.r[low..high]作快速排序if(low<high){pivotloc=Partition(L,low,high);Qsort(L,low,pivotloc-1);Qsort(L,pivotloc+1,high);}}//QSortvoidQuickSort(SqList&L){//對順序表L作快速排序Qsort(L,1,L.length);}//QuickSortvoidQsort(SqList&L,intlow35快速排序算法分析在n個元素的序列中，對一個記錄定位所需時間為O(n)。若設T(n)是對n個元素的序列進行排序所需的時間，而且每次對一個記錄正確定位后，正好把序列劃分為長度相等的兩個子序列，此時，總的計算時間為：T(n)

cn+2T(n/2) //c是一個常數(shù)

cn+2(cn/2+2T(n/4))=2cn+4T(n/4)2cn+4(cn/4+2T(n/8))=3cn+8T(n/8)………

cn

log2n+nT(1)=O(nlog2n)快速排序的平均時間是O(nlogn)，在所有同數(shù)量級(O(nlogn))的排序方法中，就平均計算時間而言，快速排序是我們所討論的所有內部排序方法中最好的一個?？焖倥判蛩惴ǚ治鲈趎個元素的序列中，對一個記錄定位所需時間為36快速排序需要一個?？臻g來實現(xiàn)遞歸，若每趟排序都將記錄序列均勻地分割成長度相接近的兩個子序列，則棧的最大深度為O(logn)。若初始序列按關鍵字基本有序（最壞情況），快速排序蛻化為起泡排序，其時間復雜度為O(n2)，最壞情況下棧的深度為n。改進的方法，用“三者取中”的法則選取樞軸記錄（pivotkey)?？焖倥判蚴且环N不穩(wěn)定的排序方法。對于n較大的平均情況而言，快速排序是“快速”的，但是當n很小時，這種排序方法往往比其它簡單排序方法還要慢?？焖倥判蛐枰粋€?？臻g來實現(xiàn)遞歸，若每趟排序都將記錄序列均勻37四、選擇排序基本思想：每一趟(例如第i趟，i=1,…,n-1)在n-i+1

個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。1．簡單選擇排序(SelectSort)2．樹形選擇排序(TreeSelectionSort)3．堆排序(HeapSort)四、選擇排序基本思想：每一趟(例如第i趟，i=1,381．簡單選擇排序(SelectSort)基本步驟：i從1開始，直到n-1，進行n-1趟排序，第i趟的排序過程為：在一組記錄r[i]～r[n](i=1,2,…,n-1)中選擇具有最小關鍵字的記錄,并和第i個記錄進行交換。1．簡單選擇排序(SelectSort)基本步驟：39簡單選擇排序的算法voidSelectSort(SqList&L){//對順序表L進行簡單選擇排序for(i=1;i<L.length;++i){k=i;//選擇關鍵字最小的記錄for(j=i+1;j<=L.length;++j) if(L.r[k].key>L.r[j].key)k=j;

//最小記錄與第i個記錄互換if(i!=k){temp=L.r[i]; L.r[i]=L.r[k];L.r[k]=temp;}}}簡單選擇排序的算法40算法分析簡單選擇排序的關鍵字比較次數(shù)與記錄的初始排列無關。第i趟選擇具有最小關鍵字的記錄所需的比較次數(shù)是n-i次，若整個待排序序列有n條記錄。因此，總的關鍵字比較次數(shù)為：記錄的移動次數(shù)與記錄的初始排列有關。當初始狀態(tài)是按其關鍵字從小到大有序的時候，記錄的移動次數(shù)為0，達到最少(最好情況)。最壞情況是每一趟都要進行交換，總的記錄移動次數(shù)為3(n-1)。簡單選擇排序是一種不穩(wěn)定的排序方法。簡單選擇排序的時間復雜度是O(n2)，空間復雜度是O(1)。算法分析簡單選擇排序的關鍵字比較次數(shù)與記錄的初始排列無關。第412．樹形選擇排序(TreeSelectionSort)又稱錦標賽排序(TournamentSort),是簡單選擇排序的改進(減少關鍵字間的比較次數(shù))?；舅枷?與體育比賽時的淘汰賽類似。首先取得n個記錄的關鍵字，進行兩兩比較，得到n/2個比較的優(yōu)勝者(關鍵字小者)，作為第一步比較的結果保留下來。然后對這n/2個記錄再進行關鍵字的兩兩比較，…，如此重復，直到選出一個關鍵字最小的記錄為止。2．樹形選擇排序(TreeSelectionSort)42如果n不是2的k次冪，則讓葉子結點數(shù)補足到滿足2k-1個。葉結點上面一層的非葉結點是葉結點關鍵字兩兩比較的結果。最頂層是樹的根。每次兩兩比較的結果是把關鍵字小者作為優(yōu)勝者上升到雙親結點，稱這種比賽樹為勝者樹。位于最底層的葉結點叫做勝者樹的外結點，非葉結點稱為勝者樹的內結點。每個結點除了存放記錄的關鍵字key外，還存放了此記錄是否要參選的標志flag和此記錄在滿二叉樹中的序號index。如果n不是2的k次冪，則讓葉子結點數(shù)補足到滿足2k43形成初始勝者樹（最小關鍵字上升到根）關鍵字比較次數(shù):7形成初始勝者樹（最小關鍵字上升到根）關鍵字比較次數(shù):744關鍵字比較次數(shù):2關鍵字比較次數(shù):2關鍵字比較次數(shù):2關鍵字比較次數(shù):245說明：錦標賽排序構成的樹是完全二叉樹，其深度為log2n

+1，其中n為待排序元素個數(shù)。除第一次選擇具有最小關鍵字的記錄需要進行n-1次關鍵字比較外，重構勝者樹選擇具有次小、再次小關鍵字記錄所需的關鍵字比較次數(shù)均為log2n?？傟P鍵字比較次數(shù)為O(nlog2n)。記錄的移動次數(shù)不超過關鍵字的比較次數(shù)，所以錦標賽排序總的時間復雜度為O(nlog2n)。這種排序方法雖然減少了許多排序時間，但是使用了較多的附加存儲。錦標賽排序是一個穩(wěn)定的排序方法。說明：錦標賽排序構成的樹是完全二叉樹，其深度為log2n463．堆排序(HeapSort)堆排序是樹形選擇排序的一種改進，主要是為了減少輔助存儲空間和多余比較。堆的定義：

n個元素的序列{k1,k2,…,kn}當且僅當滿足下列關系時，稱之為堆。3．堆排序(HeapSort)堆排序是樹形47例：（96，83，27，38，11，9）例：（13，38，27，50，76，65，49，97）可將堆序列看成完全二叉樹大頂堆小頂堆例：（96，83，27，38，11，9）例：（13，3848堆排序的基本思想是：把n個記錄存于向量r之中，把它看成完全二叉樹，此時關鍵字序列不一定滿足堆的關系。堆排序大體分兩步處理：第一步：初建堆。從堆的定義出發(fā)，當i=1,2,…,n/2時應滿足ki≤k2i和ki≤k2i+1（或ki≥k2i和ki≥k2i+1）。所以先取i=n/2(它一定是第n個結點雙親的編號)將以i結點為根的子樹調整為堆；然后令i=i-1，再將以i結點為根的子樹調整為堆。此時可能會反復調整某些結點，直到i=1為止，堆初步建成。第二步：堆排序。首先輸出堆頂元素，讓堆中最后一個元素上移到原堆頂位置，然后恢復堆，因為經(jīng)過上移堆頂元素的操作后，往往破壞了堆關系，所以要恢復堆；重復執(zhí)行輸出堆頂元素、堆尾元素上移和恢復堆的步驟，直到全部元素輸出完為止。我們稱這個從堆頂至葉子的調整過程為“篩選”。從一個無序序列建堆的過程就是一個反復“篩選”的過程。堆排序的基本思想是：把n個記錄存于向量r之中，把它看成完全二49例如：根據(jù)輸入序列{49,38,65,97,76,13,27,49}，建立一個小頂堆。第一步：初建堆例如：根據(jù)輸入序列{49,38,65,97,76,50第二步：堆排序。這是一個反復輸出堆頂元素，將堆尾元素移至堆頂，再調整恢復堆的過程?；謴投训倪^程與初建堆中i=1時所進行的操作完全相同。注意：每輸出一次堆頂元素，堆頂與堆尾元素就交換一次，同時堆尾的邏輯位置退1，直到堆中剩下一個元素為止。第二步：堆排序。這是一個反復輸出堆頂元素，將堆尾元素移至堆頂51例如：對于給定的輸入序列{80,42,13,55,94,17,46}，進行堆排序。例如：對于給定的輸入序列{80,42,13,55,952[哲學]C語言第十章課件53堆排序算法描述如下：voidHeapSort(HeapType&H){//對順序表H進行堆排序

//初始堆建立

for(i=H.length/2;i>0;--i)HeapAdjust(H,i,H.length);

//堆的輸出與調整

for(i=H.length;i>1;--i){temp=H.r[1];H.r[1]=H.r[i];H.r[i]=temp;HeapAdjust(H,1,i-1);}}堆排序算法描述如下：voidHeapSort(HeapTy54voidHeapAdjust(HeapType&H,ints,intm){//調整H.r[s..m]成一個大頂堆rc=H.r[s];for(j=2*s;j<=m;j*=2){if(j<m&&H.r[j].key<H.r[j+1].key)j++;if(rc.key≥H.r[j.key])break;H.r[s]=H.r[j];s=j;}H.r[s]=rc;}voidHeapAdjust(HeapType&H,i55算法分析時間復雜度：最壞情況下T(n)=O(nlogn)空間復雜度：S(n)=O(1)對記錄數(shù)較少的文件不值得提倡，但對n較大的文件很有效。堆排序是一個不穩(wěn)定的排序方法。算法分析時間復雜度：最壞情況下T(n)=O(nlogn)空間56五、歸并排序(MergingSort)歸并排序(mergesort)是一類與插入排序、交換排序、選擇排序不同的另一種排序方法。歸并的含義是將兩個或兩個以上的有序表合并成一個新的有序表。歸并排序有多路歸并排序、2-路歸并排序；可用于內部排序，也可以用于外部排序。我們僅對內部排序的2-路歸并方法進行討論。2-路歸并排序算法思路：(1)把n個記錄看成n個長度為1的有序子表；(2)進行兩兩歸并使記錄關鍵字有序，得到n/2個長度為2的有序子表；(3)重復第(2)步直到所有記錄歸并成一個長度為n的有序表為止。五、歸并排序(MergingSort)歸并57例如：初始關鍵字：[49][38][65][97][76][13][27]一趟歸并之后：[3849][6597][1376][27]兩趟歸并之后：[38496597][132776]三趟歸并之后：[13273849657697]例如：一趟歸并之后：[3849][582-路歸并排序中的核心操作是將一維數(shù)組中前后相鄰的兩個有序序列歸并為一個有序序列，其算法描述如下：voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]j=m+1;k=i;while(i<=m&&j<=n)if(SR[i].key<=SR[j].key)TR[k++]=SR[i++];elseTR[k++]=SR[j++];while(i<=m)TR[k++]=SR[i++];while(j<=n)TR[k++]=SR[j++];}//Merge2-路歸并排序中的核心操作是將一維數(shù)組中前后592-路歸并排序的遞歸算法描述如下：voidMSort(RcdTypeSR[],RcdType&TR1[],ints,intt){//將SR[s..t]歸并排序為TR1[s..t]。if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//將SR[s..t]平分為SR[s..m]和SR[m+1..t]MSort(SR,TR2,s,m);//將SR[s..m]歸并為有序的TR2[s..m]

MSort(SR,TR2,m+1,t);//將SR[m+1..t]歸并為有序的TR2[m+1..t]

Merge(TR2,TR1,s,m,t);//將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]

}}//MSortvoidMergeSort(SqList&L){//對順序表L作歸并排序MSort(L.r,L.r,1,L.length);}//MergeSort2-路歸并排序的遞歸算法描述如下：voidMSort(R60算法分析在歸并排序算法中，遞歸深度為O(log2n)，記錄的關鍵字比較次數(shù)為O(nlog2n)。算法總的時間復雜度為O(nlog2n)。歸并排序所需的附助空間較多，需要一個與原待排序序列數(shù)組同樣大小的輔助數(shù)組，所以算法的空間復雜度為O(n)。歸并排序是一個穩(wěn)定的排序方法。算法分析在歸并排序算法中，遞歸深度為O(log2n)，記錄的61六、基數(shù)排序(RadixSort)基數(shù)排序是與前面所介紹的排序方法完全不同的一種排序方法，該排序方法采用“分配”與“收集”的辦法，用對多關鍵字進行排序的思想實現(xiàn)對單關鍵字進行排序的方法。多關鍵字排序以撲克牌排序為例：每張撲克牌有兩個“關鍵字”：花色和面值。其有序關系為：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A注：“花色”的地位高于“面值”如果我們進行多關鍵字排序,可以把所有撲克牌排成以下次序：2,…,A,2,…,A,2,…,A,2,…,A六、基數(shù)排序(RadixSort)基數(shù)排序62對于上例兩關鍵字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序（先按不同“面值”分成13堆，然后將這13堆牌自小至大疊在一起（大數(shù)放在小數(shù)的下面），然后將這付牌整個顛倒過來再重新按不同“花色”分成4堆，最后將這4堆牌按自小至大的次序合在一起）。一般情況下，假定有一個n個記錄的序列{R1,R2,…,Rn}，且每個記錄Ri中含有d個關鍵字

(Ki0,Ki1,…,Kid-1).如果對于序列中任意兩個記錄Ri

和Rj

(1

i<j

n)都滿足：

(Ki0,Ki1,…,Kid-1)<

(Kj0,Kj1,…,Kjd-1)

則稱序列{R1,R2,…,Rn}對關鍵字(K0,K1,…,Kd-1)有序。其中，K0稱為最主位關鍵字，Kd-1稱為最次位關鍵字。對于上例兩關鍵字的排序，可以先按花色排序，之后再按面值排序；63實現(xiàn)多關鍵字排序通常有兩種方法：最高位優(yōu)先MSD(MostSignificantDigitfirst)最低位優(yōu)先LSD(LeastSignificantDigitfirst)最高位優(yōu)先法先根據(jù)最主位關鍵字K0排序,得到若干子序列，每個子序列中每個記錄都有相同關鍵字K0。再分別對每個子序列中記錄根據(jù)關鍵字K1進行排序，按K1值的不同，再分成若干個更小的子序列，每個子序列中的記錄具有相同的K0和K1值。依此重復，直到對關鍵字Kd-1完成排序為止。最后，把所有子序列中的記錄依次連接起來，就得到一個有序的記錄序列。實現(xiàn)多關鍵字排序通常有兩種方法：最高位優(yōu)先法64最低位優(yōu)先法首先依據(jù)最次位關鍵字Kd-1對所有記錄進行一趟排序，再依據(jù)關鍵字Kd-2對上一趟排序的結果再排序，依次重復，直到依據(jù)關鍵字K0最后一趟排序完成，就可以得到一個有序的序列。使用這種排序方法對每一個關鍵字進行排序時，不需要再分組，而是整個序列都參加排序。MSD和LSD方法也可應用于對一個關鍵字進行的排序。此時可將單關鍵字Ki

看作是一個子關鍵字組：(Ki0,Ki1,…,Kid-1)最低位優(yōu)先法MSD和LSD方法也可應用于對65鏈式基數(shù)排序基數(shù)排序是典型的LSD排序方法，利用“分配”和“收集”兩種運算對單關鍵字進行排序。在這種方法中，把單關鍵字Ki

看成是一個d元組：

(Ki0,Ki1,…,Kid-1)

其中的每一個分量Kij

(0

jd-1)也可看成是一個關鍵字。假設分量Kij

有radix種取值，則稱radix為基數(shù)。例如，關鍵字984可以看成是一個3元組(9,8,4)，每一位有0,1,…,9等10種取值，基數(shù)radix=10。關鍵字‘data’可以看成是一個4元組(d,a,t,a)，每一位有‘a(chǎn)’,‘b’,…,‘z’等26種取值，radix=26。鏈式基數(shù)排序基數(shù)排序是典型的LSD排序方法，66針對d元組中的每一個分量Kij，把記錄序列中的所有記錄,按Kij的取值，先“分配”到radix(rd)個隊列中去。然后再按各隊列的順序，依次把記錄從隊列中“收集”起來，這樣所有記錄按取值Kij排序完成。如果對于所有記錄的關鍵字K0,K1,…,Kn-1，依次對各位的分量，讓j=d-1,d-2,…,0，分別用這種“分配”、“收集”的運算逐趟進行排序，在最后一趟“分配”、“收集”完成后，所有記錄就按其關鍵字的值從小到大排好序了。各隊列采用鏈式存儲結構，分配到同一隊列的關鍵字用鏈接指針鏈接起來。每一隊列設置兩個隊列指針：

front[radix]指示隊頭，rear[radix]

指向隊尾。以靜態(tài)鏈表作為待排序序列的存儲結構。在記錄重排時不必移動記錄，只需修改各記錄的鏈接指針即可。針對d元組中的每一個分量Kij，把記錄序列中67例如：待排序序列放在單鏈表中，如下所示：109063930589184505269008083278e[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]278109063930589184505269008083第一趟分配063083184505278008109589269930第一趟收集例如：待排序序列放在單鏈表中，如下所示：109063930568063083184505278008109589269930e[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第二趟分配008109930063269278083184589505第二趟收集06308318450527800810958926993069008109930063269278083184589505e[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]505008109930063269278083184589第三趟分配063083109184269278505589930008第三趟收集后的有序序列00810993006326927808318458950570算法分析若每個關鍵字有d位，需要重復執(zhí)行d趟“分配”與“收集”。每趟對n個記錄進行“分配”的時間復雜度為O(n)，對rd(rd是指每個關鍵字的取值范圍)個隊列進行

“收集”的時間復雜度為O(rd)?？倳r間復雜度為O(d(n+rd))?；鶖?shù)排序需要增加n+2rd個附加鏈接指針?；鶖?shù)排序是穩(wěn)定的排序方法。算法分析若每個關鍵字有d位，需要重復執(zhí)行d趟“分配”與“71七、各種排序方法的比較輔助空間最差最好穩(wěn)定性比較次數(shù)移動次數(shù)最差最差最好最好直接插入排序希爾排序起泡排序快速排序簡單選擇排序堆排序歸并排序基數(shù)排序排序方法O(n)O(n2)O(nlog2n)O(nlog2n)O(nlog2n)O(nlog2n)O(n)O(n2)O(n2)O(n2)O(n2)O(nlog2n)O(nlog2n)0O(n2)O(n2)O(n2)00O(n)穩(wěn)定不穩(wěn)定O(nlog2n)O(nlog2n)穩(wěn)定不穩(wěn)定不穩(wěn)定不穩(wěn)定穩(wěn)定穩(wěn)定O(1)O(1)O(1)O(1)O(1)O(1)O(log2n)O(n)O(1)O(1)O(1)O(1)O(n)O(n)O(rd)O(rd)//////0000七、各種排序方法的比較輔助空間最差最好穩(wěn)定性比較次數(shù)移動次數(shù)72說明：直接插入排序、折半插入排序、冒泡排序、錦標賽排序、歸并排序、基數(shù)排序是穩(wěn)定的排序方法；而希爾排序、快速排序、簡單選擇排序、堆排序是不穩(wěn)定的排序方法。直接插入排序、冒泡排序、簡單選擇排序是簡單的排序方法，其時間復雜度都為O(n2)，空間復雜度為O(1)?？焖倥判?、錦標賽排序、堆排序和歸并排序是先進型的排序方法，其時間復雜度均為O(nlog2n)，空間復雜度分別為O(log2n)、O(n)、O(1)、O(n)。希爾排序又稱為縮小增量的排序，也是插入類排序的方法，但在時間上有較大的改進。其時間復雜度約為O(n1.3),空間復雜度為O(1)。說明：直接插入排序、折半插入排序、冒泡排序、錦標賽排序、歸并73就平均時間性能而言，快速排序最佳，但最壞情況下的時間性能不如堆排序和歸并排序。當在n個數(shù)據(jù)（n很大）中選出最小的幾個數(shù)據(jù)時，堆排序最快。歸并排序對待排序關鍵字的初始排列不敏感，故排序速度較穩(wěn)定。但所需輔助空間較多（O(n)）。各種不同的排序方法應根據(jù)不同的環(huán)境及條件分別選擇。一般而言，對于排序元素少的，可以選用時間復雜度為O(n2)的算法；對于元素多的，可選用時間復雜度為O(nlog2n)的算法。簡單排序以“直接插入排序”最簡單，當序列“基本有序”或n較小時，它是最佳排序方法，通常用它與先進的排序方法諸如快速排序等結合使用?；鶖?shù)排序最適合n很大而關鍵字較小的序列。就平均時間性能而言，快速排序最佳，但最壞情況下的時間性能不如74第10章內部排序學習目的與要求：1.深刻理解排序的定義和各種排序方法的特點,并能加以靈活應用;2.熟練掌握各種排序方法的執(zhí)行過程；3.熟練掌握各種排序方法的時間復雜度的分析方法，從“關鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時間性能;4.理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應用的排序方法必須是穩(wěn)定的。第10章內部排序學習目的與要求：75基本內容一、概述二、插入排序三、交換排序四、選擇排序五、歸并排序六、基數(shù)排序七、各種排序方法的比較基本內容一、概述76一、概述1．基本概念排序：將數(shù)據(jù)元素(或記錄)的一個任意序列,重新排列成一個按關鍵字有序的序列。排序方法的穩(wěn)定性：對關鍵字相同的數(shù)據(jù)元素，排序前后它們的領先關系保持不變，則稱該排序方法是穩(wěn)定的；反之，稱該排序方法是不穩(wěn)定的。內部排序：待排序記錄存放在計算機的內存中進行的排序。一、概述1．基本概念排序：將數(shù)據(jù)元素(或記錄)的一個任意序列77外部排序：待排序記錄的數(shù)量很大，以致內存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序。排序的時間開銷：排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。算法運行時間代價的估算一般都按平均情況進行估算。對于那些受記錄關鍵字序列初始排列及記錄個數(shù)影響較大的，需要按最好情況和最壞情況進行估算。外部排序：待排序記錄的數(shù)量很大，以致內存一次不能容納全部記錄782．排序的分類按排序過程依據(jù)的不同原則進行分類：交換排序選擇排序歸并排序計數(shù)排序插入排序按工作量進行分類：先進的排序方法，其時間復雜度為O(nlog2n)簡單的排序方法,其時間復雜度為O(n2)基數(shù)排序基數(shù)排序，其時間復雜度為O(d·n)2．排序的分類按排序過程依據(jù)的不同原則進行分類：交換排序選擇793．排序的基本操作和記錄的存儲方式排序過程中需要的兩種基本操作：（1）比較關鍵字的大?。唬?）將記錄從一個位置移至另一個位置。待排序記錄序列可有下列三種存儲方式：（1）記錄存放在一組連續(xù)的存儲單元中；類似于線性表的順序存儲結構，記錄次序由存儲位置決定，實現(xiàn)排序需移動記錄。（2）記錄存放在靜態(tài)鏈表中；記錄次序由指針指示，實現(xiàn)排序不需移動記錄，僅需修改指針?！溑判颍?）記錄本身存放在一組連續(xù)的存儲單元中，同時另設指示各個記錄存儲位置的地址向量，排序過程中不移動記錄本身，而移動地址向量中相應記錄的地址。排序結束后再根據(jù)地址調整記錄的存儲位置。——地址排序3．排序的基本操作和記錄的存儲方式排序過程中需要的兩種基本操804．待排序記錄的數(shù)據(jù)類型#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;InfoTypeotherinfo;}RcdType;typedefstruct{RedTyper[MAXSIZE+1];//0單元作為哨兵intlength;}SqList;4．待排序記錄的數(shù)據(jù)類型#defineMAXSIZE281二、插入排序1．直接插入排序2．折半插入排序3．2-路插入排序4．表插入排序5．希爾排序插入排序的基本方法是：每步將一個待排序的記錄，按其關鍵字大小，插入到前面已經(jīng)排好序的一組記錄的適當位置上，直到記錄全部插入為止。二、插入排序1．直接插入排序插入排序的基本方法是：每步將一個821．直接插入排序基本思想：當插入第i(i1)個記錄時，前面的r[1],r[2]，…，r[i-1]已經(jīng)排好序。這時，用r[i]的關鍵字與r[i-1]，r[i-2]，…的關鍵字順序進行比較，找到插入位置即將r[i]插入，原來位置上之后的所有記錄依次向后順移。1．直接插入排序基本思想：83例49386597761327（）i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=7(133849657697)27j9727j76j65j49j38j排序結果：(13273849657697)例49386597784直接插入排序的算法voidInsertSort(SqList&L){//對待排序序列L進行直接插入排序for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){

L.r[0]=L.r[i];//復制為哨兵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];//記錄插入}}//InsertSort直接插入排序的算法voidInsertSort(SqLi85算法評價記錄的比較次數(shù)記錄的移動次數(shù)最好情況最壞情況0時間復雜度：T(n)=O(n2)結論：空間復雜度：S(n)=O(1)直接插入排序是一個穩(wěn)定的排序方法。算法評價記錄的比較次數(shù)記錄的移動次數(shù)最好情況最壞情況0時間復862．折半插入排序基本思想：利用直接插入排序的思想，只是在排序過程中，為減少查找次數(shù)，對已排好序的序列r[1],r[1],…,r[i-1]，利用折半查找法尋找r[i]的插入位置。例

(30)1370853942620i=213(1330)70853942620…...i=76(6133039427085)202．折半插入排序基本思想：例(30)87i=820(6133039427085)20lhmi=820(6133039427085)20lhmi=820(6133039427085)20l,m,hi=820(6133039427085)20lhi=820(613203039427085)i=820(6133088算法描述如下：voidBin_InsertSort(SqList&L){//對待排序序列L進行折半插入排序for(i=2;i<=L.length;++i){low=1;high=i-1;while(low<=high){mid=(low+high)/2;if(r.[mid].key<=r[0].key)high=mid-1;elselow=mid+1;}for(j=i-1;j>h;j--)L.r[j+1]=L.r[j];//記錄后移L.r[j+1]=L.r[0];//記錄插入}}//Bin_InsertSort算法描述如下：voidBin_InsertSort(Sq89算法分析折半插入排序減少了關鍵字間的比較次數(shù)（由O(n2)下降到O(nlog2n))。折半插入排序的記錄移動次數(shù)仍為O(n2)。折半插入排序的時間復雜度仍為O(n2)，空間復雜度仍為O(１)。折半插入排序是一個穩(wěn)定的排序方法。算法分析折半插入排序減少了關鍵字間的比較次數(shù)（由O(n2)下903．2-路插入排序基本思想：利用直接插入排序的思想，只是在排序過程中，為減少記錄的移動次數(shù)，但需要n個記錄的輔助空間。其做法是：另設一個和L.r同類型的數(shù)組d，首先將L.r[1]賦給d.r[1]，并將d.r[1]看成是在排好序的序列中處于中間位置的記錄，然后從L.r中第二個記錄起依次到d.r[1]之前或之后的有序序列中。例

301370853942620排序過程中d的狀態(tài)變化如下：i=1(30)firstfinali=2(30)13firstfinal