哲學(xué)C語(yǔ)言第十章課件

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

L.r[0]=L.r[i];//復(fù)制為哨兵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算法評(píng)價(jià)記錄的比較次數(shù)記錄的移動(dòng)次數(shù)最好情況最壞情況0時(shí)間復(fù)雜度：T(n)=O(n2)結(jié)論：空間復(fù)雜度：S(n)=O(1)直接插入排序是一個(gè)穩(wěn)定的排序方法。算法評(píng)價(jià)記錄的比較次數(shù)記錄的移動(dòng)次數(shù)最好情況最壞情況0時(shí)間復(fù)122．折半插入排序基本思想：利用直接插入排序的思想，只是在排序過程中，為減少查找次數(shù)，對(duì)已排好序的序列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){//對(duì)待排序序列L進(jìn)行折半插入排序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算法分析折半插入排序減少了關(guān)鍵字間的比較次數(shù)（由O(n2)下降到O(nlog2n))。折半插入排序的記錄移動(dòng)次數(shù)仍為O(n2)。折半插入排序的時(shí)間復(fù)雜度仍為O(n2)，空間復(fù)雜度仍為O(１)。折半插入排序是一個(gè)穩(wěn)定的排序方法。算法分析折半插入排序減少了關(guān)鍵字間的比較次數(shù)（由O(n2)下163．2-路插入排序基本思想：利用直接插入排序的思想，只是在排序過程中，為減少記錄的移動(dòng)次數(shù)，但需要n個(gè)記錄的輔助空間。其做法是：另設(shè)一個(gè)和L.r同類型的數(shù)組d，首先將L.r[1]賦給d.r[1]，并將d.r[1]看成是在排好序的序列中處于中間位置的記錄，然后從L.r中第二個(gè)記錄起依次到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){//對(duì)待排序序列L進(jìn)行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-路插入排序減少了關(guān)鍵字間的比較次數(shù)(小于nlog2n)。2-路插入排序減少了記錄移動(dòng)次數(shù)，約為n2/8。2-路插入排序的時(shí)間復(fù)雜度仍為O(n2)，但空間復(fù)雜度為O(n)。2-路插入排序是一個(gè)穩(wěn)定的排序方法。算法分析2-路插入排序減少了關(guān)鍵字間的比較次數(shù)(小于nlog214．表插入排序表插入排序采用了靜態(tài)鏈表的存儲(chǔ)結(jié)構(gòu)，其排序過程如下：首先將靜態(tài)鏈表中數(shù)組下標(biāo)為1的分量（結(jié)點(diǎn)）和表頭結(jié)點(diǎn)構(gòu)成一個(gè)循環(huán)鏈表，然后依次將下標(biāo)為2至n的分量（結(jié)點(diǎn)）按記錄關(guān)鍵字非遞減有序插入到循環(huán)鏈表中。表插入排序的基本操作仍是將一個(gè)記錄插入到已排好序的有序表中。和直接插入排序相比，不同之處僅是以修改2n次指針值代替移動(dòng)記錄，排序過程中所需進(jìn)行的關(guān)鍵字間的比較次數(shù)相同。因此，表插入排序的時(shí)間復(fù)雜度仍是O(n2)。4．表插入排序表插入排序采用了靜態(tài)鏈表的存儲(chǔ)結(jié)構(gòu)，其排序過程225．希爾排序希爾排序方法又稱為“縮小增量”排序?；舅枷耄合葘⒄麄€(gè)待排序記錄序列分割成若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。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希爾排序算法分析子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將相隔某個(gè)增量的記錄組成一個(gè)子序列；希爾排序可提高排序速度，因?yàn)殛P(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟增量為1的插入排序時(shí)，序列已基本有序;增量序列取法有多種：1)沒有除1以外的公因子2)最后一個(gè)增量值必須為1時(shí)間復(fù)雜度是所取增量序列的函數(shù)，但至今沒人能夠給出完整的數(shù)學(xué)分析。希爾排序是一個(gè)不穩(wěn)定的排序方法。希爾排序算法分析子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將相25三、交換排序1．起泡排序(BubbleSort)2．快速排序(QuickSort)三、交換排序1．起泡排序(BubbleSort)261．起泡排序(BubbleSort)基本過程：1)將第一個(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è)記錄上;2)對(duì)前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個(gè)記錄位置;3)重復(fù)上述過程，直到“在一趟排序過程中沒有進(jìn)行過交換記錄的操作”為止。1．起泡排序(BubbleSort)基本過程：27例：49383838381313384949491327276565651327383897761327494976132749

49132749

652749

76

49

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

27

3849

4965

76

97}快速排序結(jié)束：{13

27

3849

49

65

76

97}一趟完成后：{27，38，13，49，76，97，65，4933快速排序算法描述：intPartition(SqList&L,intlow,inthigh){//對(duì)順序表L進(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];//將比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){//對(duì)順序表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){//對(duì)順序表L作快速排序Qsort(L,1,L.length);}//QuickSortvoidQsort(SqList&L,intlow35快速排序算法分析在n個(gè)元素的序列中，對(duì)一個(gè)記錄定位所需時(shí)間為O(n)。若設(shè)T(n)是對(duì)n個(gè)元素的序列進(jìn)行排序所需的時(shí)間，而且每次對(duì)一個(gè)記錄正確定位后，正好把序列劃分為長(zhǎng)度相等的兩個(gè)子序列，此時(shí)，總的計(jì)算時(shí)間為：T(n)

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

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

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

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

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

//初始堆建立

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

//堆的輸出與調(diào)整

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){//調(diào)整H.r[s..m]成一個(gè)大頂堆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算法分析時(shí)間復(fù)雜度：最壞情況下T(n)=O(nlogn)空間復(fù)雜度：S(n)=O(1)對(duì)記錄數(shù)較少的文件不值得提倡，但對(duì)n較大的文件很有效。堆排序是一個(gè)不穩(wěn)定的排序方法。算法分析時(shí)間復(fù)雜度：最壞情況下T(n)=O(nlogn)空間56五、歸并排序(MergingSort)歸并排序(mergesort)是一類與插入排序、交換排序、選擇排序不同的另一種排序方法。歸并的含義是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。歸并排序有多路歸并排序、2-路歸并排序；可用于內(nèi)部排序，也可以用于外部排序。我們僅對(duì)內(nèi)部排序的2-路歸并方法進(jìn)行討論。2-路歸并排序算法思路：(1)把n個(gè)記錄看成n個(gè)長(zhǎng)度為1的有序子表；(2)進(jìn)行兩兩歸并使記錄關(guān)鍵字有序，得到n/2個(gè)長(zhǎng)度為2的有序子表；(3)重復(fù)第(2)步直到所有記錄歸并成一個(gè)長(zhǎng)度為n的有序表為止。五、歸并排序(MergingSort)歸并57例如：初始關(guān)鍵字：[49][38][65][97][76][13][27]一趟歸并之后：[3849][6597][1376][27]兩趟歸并之后：[38496597][132776]三趟歸并之后：[13273849657697]例如：一趟歸并之后：[3849][582-路歸并排序中的核心操作是將一維數(shù)組中前后相鄰的兩個(gè)有序序列歸并為一個(gè)有序序列，其算法描述如下：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]歸并排序?yàn)門R1[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){//對(duì)順序表L作歸并排序MSort(L.r,L.r,1,L.length);}//MergeSort2-路歸并排序的遞歸算法描述如下：voidMSort(R60算法分析在歸并排序算法中，遞歸深度為O(log2n)，記錄的關(guān)鍵字比較次數(shù)為O(nlog2n)。算法總的時(shí)間復(fù)雜度為O(nlog2n)。歸并排序所需的附助空間較多，需要一個(gè)與原待排序序列數(shù)組同樣大小的輔助數(shù)組，所以算法的空間復(fù)雜度為O(n)。歸并排序是一個(gè)穩(wěn)定的排序方法。算法分析在歸并排序算法中，遞歸深度為O(log2n)，記錄的61六、基數(shù)排序(RadixSort)基數(shù)排序是與前面所介紹的排序方法完全不同的一種排序方法，該排序方法采用“分配”與“收集”的辦法，用對(duì)多關(guān)鍵字進(jìn)行排序的思想實(shí)現(xiàn)對(duì)單關(guān)鍵字進(jìn)行排序的方法。多關(guān)鍵字排序以撲克牌排序?yàn)槔好繌垞淇伺朴袃蓚€(gè)“關(guān)鍵字”：花色和面值。其有序關(guān)系為：花色：

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

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

和Rj

(1

i<j

n)都滿足：

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

(Kj0,Kj1,…,Kjd-1)

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

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

看成是一個(gè)d元組：

(Ki0,Ki1,…,Kid-1)

其中的每一個(gè)分量Kij

(0

jd-1)也可看成是一個(gè)關(guān)鍵字。假設(shè)分量Kij

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

front[radix]指示隊(duì)頭，rear[radix]

指向隊(duì)尾。以靜態(tài)鏈表作為待排序序列的存儲(chǔ)結(jié)構(gòu)。在記錄重排時(shí)不必移動(dòng)記錄，只需修改各記錄的鏈接指針即可。針對(duì)d元組中的每一個(gè)分量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算法分析若每個(gè)關(guān)鍵字有d位，需要重復(fù)執(zhí)行d趟“分配”與“收集”。每趟對(duì)n個(gè)記錄進(jìn)行“分配”的時(shí)間復(fù)雜度為O(n)，對(duì)rd(rd是指每個(gè)關(guān)鍵字的取值范圍)個(gè)隊(duì)列進(jìn)行

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

L.r[0]=L.r[i];//復(fù)制為哨兵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算法評(píng)價(jià)記錄的比較次數(shù)記錄的移動(dòng)次數(shù)最好情況最壞情況0時(shí)間復(fù)雜度：T(n)=O(n2)結(jié)論：空間復(fù)雜度：S(n)=O(1)直接插入排序是一個(gè)穩(wěn)定的排序方法。算法評(píng)價(jià)記錄的比較次數(shù)記錄的移動(dòng)次數(shù)最好情況最壞情況0時(shí)間復(fù)862．折半插入排序基本思想：利用直接插入排序的思想，只是在排序過程中，為減少查找次數(shù)，對(duì)已排好序的序列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){//對(duì)待排序序列L進(jìn)行折半插入排序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算法分析折半插入排序減少了關(guān)鍵字間的比較次數(shù)（由O(n2)下降到O(nlog2n))。折半插入排序的記錄移動(dòng)次數(shù)仍為O(n2)。折半插入排序的時(shí)間復(fù)雜度仍為O(n2)，空間復(fù)雜度仍為O(１)。折半插入排序是一個(gè)穩(wěn)定的排序方法。算法分析折半插入排序減少了關(guān)鍵字間的比較次數(shù)（由O(n2)下903．2-路插入排序基本思想：利用直接插入排序的思想，只是在排序過程中，為減少記錄的移動(dòng)次數(shù)，但需要n個(gè)記錄的輔助空間。其做法是：另設(shè)一個(gè)和L.r同類型的數(shù)組d，首先將L.r[1]賦給d.r[1]，并將d.r[1]看成是在排好序的序列中處于中間位置的記錄，然后從L.r中第二個(gè)記錄起依次到d.r[1]之前或之后的有序序列中。例

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