數(shù)據(jù)結(jié)構(gòu)第章內(nèi)部排序課件

第10章內(nèi)部排序討論各種內(nèi)部排序方法：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序的基本思想、算法特點、排序過程以及時間復(fù)雜性的分析。比較各種內(nèi)部排序方法。1目錄10.1概述10.2插入排序10.3快速排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種內(nèi)部排序方法的比較討論2排序（sorting）1.基本概念將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列。假設(shè)含n個記錄的序列為{R1，R2，…，Rn}(※）其相應(yīng)的關(guān)鍵字序列為{K1，K2，…，Kn}10.1概述3需確定1，2，…，n的一種排列p1，p2，…，pn，使其相應(yīng)的關(guān)鍵字滿足如下的非遞減（或非遞增）關(guān)系Kp1Kp2…Kpn即使序列(※）成為一個按關(guān)鍵字有序的序列{Rp1，Rp2，…，Rpn}這種操作過程稱為排序。排序(接上頁)基本概念4基本概念排序方法是穩(wěn)定的設(shè)Ki=Kj（lin，1jn，i≠j），且在排序前的序列中Ri領(lǐng)先于Rj（即i＜j），在排序后的序列中Ri仍領(lǐng)先于Rj。排序方法是不穩(wěn)定的設(shè)Ki=Kj（lin，1jn，i≠j），且在排序前的序列中Ri領(lǐng)先于Rj（即i＜j），在排序后的序列中Rj領(lǐng)先于Ri。52.排序方法分類按照文件所處的位置不同：內(nèi)部排序待排序記錄存放在計算機內(nèi)存中進行的排序過程。外部排序排序過程中有內(nèi)、外存間信息的傳遞及交換的排序過程。6排序方法分類按排序時使用的原理插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序。按照所需的工作量簡單的排序方法，其時間復(fù)雜度為O（n2）；先進的排序方法，其時間復(fù)雜度為O（nlogn）；基數(shù)排序，其時間復(fù)雜度為O（d·n）。73.基本操作

比較兩個關(guān)鍵字的大小；將記錄從一個位置移動至另一個位置。84.存儲結(jié)構(gòu)（1）以一維數(shù)組作為存儲結(jié)構(gòu)（2）以靜態(tài)鏈表作為存儲結(jié)構(gòu)（鏈表排序）（3）采用輔助表排序（地址排序）待排序記錄存儲在數(shù)組中，同時另設(shè)一個指示各個記錄存儲位置的地址向量。在排序過程中不移動記錄本身，而移動地址向量中這些記錄的“地址”，排序結(jié)束后再按照地址向量中的值調(diào)整記錄的存儲位置。95.排序方法分析排序的時間開銷:排序的時間開銷是衡量算法好壞的最重要的標(biāo)志。排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。一般都按平均情況進行估算。對于那些受對象關(guān)鍵字序列初始排列及對象個數(shù)影響較大的，需要按最好情況和最壞情況進行估算。衡量排序方法的標(biāo)準(zhǔn)排序時所需要的平均比較次數(shù)排序時所需要的平均移動排序時所需要的平均輔助存儲空間101.直接插入排序(StraightInsertionSort)

概念將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。例：已排序的一組記錄排列如下：12，33，45，57，76現(xiàn)將關(guān)鍵字40記錄插入上述序列中12，33，40，45，57，7610.2插入排序11

算法的基本思路直接插入排序設(shè)有n個待排記錄存放在r[1..n]中，將第i(2≤i≤n)個記錄插入到已排好序的有序表r[1..i-1]中的過程為：從r[i-1]起往前搜索，若r[i]<r[j](1≤j≤i-1)，則將r[j]向后移動，直至找到第i個記錄的位置。12

算法10.1直接插入排序voidInsertSort（SqList&L）{for(i=2;i<=L.Length;++i)ifLT(L.r[i].key,L.r[i-1].key{L.r[0]=L.r[i]；L.r[i]=L.r[i-1]；for(j=i-2;LT(L.r[0].key,L.r[j].key);--j）L.r[j+l]=L.r[j];L.r[j+l]=L.r[0];}

}13例子直接插入排序初始關(guān)鍵字：(42)41336774233733i=2：(41)(4142)336774233733i=3：(33)(334142)6774233733i=4：(33)(33414267)74233733i=5：(33)(3341426774)233733i=6：(23)(233341426774)3733i=7：(37)(23333741426774)33i=8：(33)(2333333741426774)14時間復(fù)雜性分析直接插入排序若設(shè)待排序的對象個數(shù)為L.length=n，則該算法的主程序執(zhí)行n-1趟。關(guān)鍵字比較次數(shù)和對象移動次數(shù)與對象關(guān)鍵字的初始排列有關(guān)。最好情況下，排序前對象已經(jīng)按關(guān)鍵字大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械淖詈笠粋€對象的關(guān)鍵字比較1次，總的關(guān)鍵字比較次數(shù)為n-1，對象移動次數(shù)為0。最壞情況下，排序前對象已經(jīng)按關(guān)鍵字大小從大到小有序（逆序），需比較和移動次數(shù)為多少？15直接插入排序時間復(fù)雜性分析若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵字比較次數(shù)和對象移動次數(shù)約為n2/4。因此，直接插入排序的時間復(fù)雜度為o(n2)。直接插入排序是一種穩(wěn)定的排序方法。162.其它插入排序折半插入排序（BinaryInsertionSort）折半插入排序基本思想是：設(shè)在順序表中有一個對象序列V[0],V[1],…,v[n-1]。其中，v[0],V[1],…,v[i-1]是已經(jīng)排好序的對象。在插入v[i]時，利用折半搜索法尋找v[i]的插入位置。

2-路插入排序表插入排序17折半插入排序的算法10.2voidBInsertSort(SqList&L){intlow,high,mid;for(inti=2;i<=L.length;++i){L.r[0]=L.r[i]; low=1;high=i-1; while(low<=high){mid=(low+high)/2; if(LT(L.r[0].key,L.r[mid].key))high=mid-1; elselow=mid+1;} for(intj=i-1;j>=high+1;--j)L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; }}說明：low或者h(yuǎn)igh+1為插入點穩(wěn)定排序18算法分析折半查找比順序查找快，所以折半插入排序就平均性能來說比直接插入排序要快。它所需要的關(guān)鍵字比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān)，僅依賴于對象個數(shù)。在插入第i個對象時，需要經(jīng)過log2i+1次關(guān)鍵字比較，才能確定它應(yīng)插入的位置。因此，將n個對象（為推導(dǎo)方便，設(shè)為n=2k)用折半插入排序所進行的關(guān)鍵字比較次數(shù)為：1920當(dāng)n較大時，總關(guān)鍵字比較次數(shù)比直接插入排序的最壞情況要好得多，但比其最好情況要差。在對象的初始排列已經(jīng)按關(guān)鍵字排好序或接近有序時，直接插入排序比折半插入排序執(zhí)行的關(guān)鍵字比較次數(shù)要少。折半插入排序的對象移動次數(shù)與直接插入排序相同，依賴于對象的初始排列。折半插入排序是一個穩(wěn)定的排序方法。213.希爾排序(Shell’sSort)基本思想先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。

概念希爾排序又稱“縮小增量排序”(DiminishingIncrementSort)屬于插入排序類的方法，其時間效率上優(yōu)于前述幾種方法。22例，初始關(guān)鍵字序列為：

43413367742337334735d=5

43234137333367477435一趟排序的結(jié)果：23373347354341336774希爾排序例子2323373347354341336774d=3

23474174373533334367二趟排序的結(jié)果：23333341354347376774三趟排序(直接插入排序)的結(jié)果：23333335374143476774希爾排序2410.3交換排序交換排序(ExchangeSort)

交換排序的基本思想是兩兩比較待排序?qū)ο蟮年P(guān)鍵字，如果發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之，直到所有對象都排好序為止。25基本思想將第1個記錄的關(guān)鍵字和第2個記錄的關(guān)鍵字進行比較，若為逆序（即r[1].key＞r[2].key），則將兩個記錄交換之，然后比較第2個記錄和第3個記錄的關(guān)鍵字。依次類推，直至第n-1個記錄和第n個記錄的關(guān)鍵字進行過比較為止。第一趟冒泡排序后，關(guān)鍵字最大的記錄被放到最后一個記錄的位置上。對前n-1個記錄進行同樣操作，其結(jié)果是使關(guān)鍵字次大的記錄被安置到第n-1個記錄的位置上。1.冒泡排序(BubbleSort)26一般地，第i趟冒泡排序是從r[1]到r[n-i+1]依次比較相鄰兩個記錄的關(guān)鍵字，并在“逆序”時交換相鄰記錄，其結(jié)果是這n-i+1個記錄中關(guān)鍵字最大的記錄被交換到第n-i+1的位置上。整個排序過程需進行k（1k<n）趟冒泡排序。排序結(jié)束的條件在一趟排序過程中沒有進行過交換記錄的操作。冒泡排序274938659776132749初始關(guān)鍵字3849657613274997第一趟排序后冒泡排序例子3849651327497697第二趟排序后3849132749657697第三趟排序后3813274949657697第四趟排序后1327384949657697第五趟排序后1327384949657697第六趟排序后28冒泡排序的算法Voidbubble-sort(inta[]，intn)for(I=n-1;change=TURE;I>1&&change;--I){change=false;for(j=0;j<I;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TURE}}算法復(fù)雜性分析：最好情況（正序）：一趟排序，n-1次比較，移動0個記錄最壞情況（逆序）：n-1趟排序，n-1+n-2+…+1=n(n-1/)/2次比較,移動n(n-1/)/2個記錄時間復(fù)雜度：O(n2)292.快速排序(QuickSort)基本思想根據(jù)選定的支點L，通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均小于L，而另一部分記錄的關(guān)鍵字均大于等于L。分別對這兩部分記錄繼續(xù)進行排序，以達(dá)到整個序列有序。支點的選擇方法取第一個記錄；最后一個記錄；第一個、最后一個和中間記錄三者中，關(guān)鍵字居中的那個記錄。30具體做法設(shè)待排序的序列為｛r[s]，r[s+1]，…，r[t]｝。附設(shè)兩個指針i和j，它們的初值分別為s和t，設(shè)支點記錄pivot=r[s]，x=pivotkey。則首先從j所指位置起向前搜索找到第一個關(guān)鍵字小于x的記錄和pivot互相交換，然后從i所指位置起向后搜索，找到第一個關(guān)鍵字大于x的記錄和pivot互相交換，重復(fù)這兩步直至i=j為止?？焖倥判?1舉例例，初始關(guān)鍵字序列為：

43413367742337334735x=43初始

43413367742337334735↑↑ij1次

35413367742337334743↑↑↑i→ij快速排序322次

35413343742337334767↑↑ij3次

35413333742337434767↑↑←↑ijj4次

35413333432337744767↑→↑↑iij快速排序335次

35413333372343744767↑↑←↑ijj快速排序5次

35413333372343744767↑↑ij完成一趟

3541333337234374476734快速排序的算法voidQSort(SqList&L,intlow,inthigh){ if(low<high){ intpivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); PrintST(L); QSort(L,pivotloc+1,high); PrintST(L); }}voidQuickSort(SqList&L){ QSort(L,1,L.length);}35intPartition(SqList&L,intlow,inthigh){L.r[0]=L.r[low];intpivotkey=L.r[low].key;while(low<high){ while(low<high&&L.r[high].key>=pivotkey)--high; L.r[low]=L.r[high]; while(low<high&&L.r[low].key<=pivotkey)++low; L.r[high]=L.r[low];} L.r[low]=L.r[0]; returnlow;}36算法分析從快速排序算法的遞歸樹可知，快速排序的趟數(shù)取決于遞歸樹的深度。如果每次劃分對一個對象定位后，該對象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對兩個長度減半的子序列進行排序，這是最理想的情況。在n個元素的序列中，對一個對象定位所需時間為O(n)。若設(shè)t(n)是對n個元素的序列進行排序所需的時間，而且每次對一個對象正確定位后，正好把序列劃分為長度相等的兩個子序列，此時，總的計算時間為：37T(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)………

Cnlog2n+nt(1)=o(nlog2n)可以證明，函數(shù)quicksort的平均計算時間也是o(nlog2n)。實驗結(jié)果表明：就平均計算時間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個。38快速排序是遞歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)。最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為log2(n+1)。因此，要求存儲開銷為o(log2n)。在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵字從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個比上一次少一個對象的子序列。這樣，必須經(jīng)過n-1趟才能把所有對象定位，而且第i趟需要經(jīng)過n-i次關(guān)鍵字比較才能找到第i個對象的安放位置，總的關(guān)鍵字比較次數(shù)將達(dá)到39其排序速度退化到簡單排序的水平，比直接插入排序還慢。占用附加存儲(即棧)將達(dá)到o(n)。若能更合理地選擇基準(zhǔn)對象，使得每次劃分所得的兩個子序列中的對象個數(shù)盡可能地接近，可以加速排序速度，但是由于對象的初始排列次序是隨機的，這個要求很難辦到。有一種改進辦法：取每個待排序?qū)ο笮蛄械牡谝粋€對象、最后一個對象和位置接近正中的3個對象，取其關(guān)鍵字居中者作為基準(zhǔn)對象。快速排序是一種不穩(wěn)定的排序方法。對于n較大的平均情況而言，快速排序是“快速”的，但是當(dāng)n很小時，這種排序方法往往比其它簡單排序方法還要慢。40基本思想每一趟在n-i+1（i=1，2，…，n-1）個記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個記錄。分類簡單選擇排序樹形選擇排序堆排序10.4選擇排序41簡單選擇排序(SimpleSelectionSort)基本思想通過n-i次關(guān)鍵字間的比較，從n-i+1個記錄中選出關(guān)鍵字最小的記錄，并和第i（1in）個記錄交換之（稱為一趟簡單選擇排序）。具體實現(xiàn)時令i從1至n-1，進行n-1次選擇操作。42算法voidSelectSort（SqList&L）{for(i=1;i<L.Length;++i){k=i;for(j=i+1;j<=L.Length;++j)if(L.r[j].key<L.r[k].key)k=j；if(i!=k){L.r[0]=L.r[i];L.r[i]=L.r[k];L.r[k]=L.r[0];}}}簡單選擇排序43簡單選擇排序舉例4938659776132749初始關(guān)鍵字1338659776492749第一趟排序后1327659776493849第二趟排序后1327389776496549第三趟排序后1327384976976549第四趟排序后1327384949976576第五趟排序后1327384949659776第六趟排序后1327384949657697第七趟排序后44

算法分析直接選擇排序的關(guān)鍵字比較次數(shù)KCN與對象的初始排列無關(guān)。第i趟選擇具有最小關(guān)鍵字對象所需的比較次數(shù)總是n-i-1次，此處假定整個待排序?qū)ο笮蛄杏衝個對象。因此，總的關(guān)鍵字比較次數(shù)為45對象的移動次數(shù)與對象序列的初始排列有關(guān)。當(dāng)這組對象的初始狀態(tài)是按其關(guān)鍵字從小到大有序的時候，對象的移動次數(shù)RMN=0，達(dá)到最少。最壞情況是每一趟都要進行交換，總的對象移動次數(shù)為RMN=3(n-1)。直接選擇排序是一種不穩(wěn)定的排序方法。462.錦標(biāo)賽排序(TournamentTreeSort)

樹形選擇排序(TreeSelectionSort)它的思想與體育比賽時的淘汰賽類似。首先取得n個對象的關(guān)鍵字，進行兩兩比較，得到n/2個比較的優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來。然后對這n/2個對象再進行關(guān)鍵字的兩兩比較，…，如此重復(fù)，直到選出一個關(guān)鍵字最小的對象為止。47錦標(biāo)賽排序構(gòu)成的樹是滿的完全二叉樹，其深度為log2(n+1)，其中n為待排序元素個數(shù)。除第一次選擇具有最小關(guān)鍵字的對象需要進行n-1次關(guān)鍵字比較外，重構(gòu)勝者樹選擇具有次小、再次小關(guān)鍵字對象所需的關(guān)鍵字比較次數(shù)均為O(log2n)?？傟P(guān)鍵字比較次數(shù)為O(nlog2n)。對象的移動次數(shù)不超過關(guān)鍵字的比較次數(shù)，所以錦標(biāo)賽排序總的時間復(fù)雜度為O(nlog2n)。這種排序方法雖然減少了許多排序時間，但是使用了較多的附加存儲。算法分析48勝者樹的概念每次兩兩比較的結(jié)果是把關(guān)鍵字小者作為優(yōu)勝者上升到雙親結(jié)點，稱這種比賽樹為勝者樹。位于最底層的葉結(jié)點叫做勝者樹的外結(jié)點，非葉結(jié)點稱為勝者樹的內(nèi)結(jié)點。每個結(jié)點除了存放對象的關(guān)鍵字key外，還存放了此對象是否要參選的標(biāo)志Active和此對象在滿二叉樹中的序號index。勝者樹最頂層是樹的根，表示最后選擇出來的具有最小關(guān)鍵字的對象。49如果有n個對象，必須使用至少2n-1個結(jié)點來存放勝者樹。最多需要找到滿足2k-1<n

2k的k，使用2*2k-1個結(jié)點。每個結(jié)點包括關(guān)鍵字、對象序號和比較標(biāo)志三種信息。錦標(biāo)賽排序是一個穩(wěn)定的排序方法。50堆的定義n個元素的序列｛k1，k2，…，kn｝當(dāng)且僅當(dāng)滿足下關(guān)系ki≤k2i,ki≤k2i+1或ki≥k2i,ki≥k2i+1

其中

i=1,2,…,[n/2]3.堆排序(HeapSort)9683382711091236852447305391例如，下列兩個序列為堆：{96，83，27，38，11，09}{12，36，24，85，47，30，53，91}51堆排序基本思想首先對n個記錄的關(guān)鍵字按堆的定義建堆，輸出堆頂?shù)脑兀ㄗ钚￡P(guān)鍵字），以堆中最后一個元素代替之。然后對剩余的關(guān)鍵字再建堆（重新調(diào)整成堆），輸出堆頂?shù)脑兀ù涡￡P(guān)鍵字），如此重復(fù)，直至全部關(guān)鍵字排成有序序列為止。實現(xiàn)堆排序需解決兩個問題：(1)如何將一個無序序列建成一個堆？(2)如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個新的堆？52堆排序?qū)⒁粋€無序序列建成一個堆(1)先將一個無序序列按層次關(guān)系建成一個完全二叉樹。(2)從第n/2個元素開始。即從完全二叉樹的最后一個非終端結(jié)點開始，按照堆的定義，與其子結(jié)點交換，直至全部序列成為一個堆。53建堆舉例例如，有一個無序序列{4938659776132749}49389765761327494938496576132797493849137665279713384949766527971338492776654997堆54輸出堆頂元素，用最后一個元素代替之，然后調(diào)整剩余元素成為一個新的堆堆排序1338492776654997堆9738492776654913輸出13并用97代替之4927384997766513調(diào)整2738494976659713調(diào)整成一個新堆3849974976652713輸出27并用97代替之，然后調(diào)整成一個新堆55練習(xí)堆排序有一個無序序列{33，25，46，13，58，95，18，63}(1)將該序列建成一個堆。(2)按序輸出元素，并寫出調(diào)整成一個新堆的過程56最大堆的向下調(diào)整算法voidHeapAdjust(HeapType&H,ints,intm){ ElemTyperc=H.r[s]; for(intj=2*s;j<=m;j*=2){ if((j<m)&&(LT(H.r[j].key,H.r[j+1].key)))++j; if(!(LT(rc.key,H.r[j].key)))break; H.r[s].key=H.r[j].key;s=j; } H.r[s]=rc;}57基于初始堆進行堆排序最大堆的第一個對象r[1]具有最大的關(guān)鍵字，將r[1]與r[n]對調(diào)，把具有最大關(guān)鍵字的對象交換到最后，再對前面的n-1個對象，使用堆的調(diào)整算法HeapAdjust(1,n-1)，重新建立最大堆。結(jié)果具有次最大關(guān)鍵字的對象又上浮到堆頂，即r[1]位置。再對調(diào)r[1]和r[n-1]，調(diào)用HeapAdjust(1,n-2)，對前n-2個對象重新調(diào)整，…。如此反復(fù)執(zhí)行，最后得到全部排序好的對象序列。這個算法即堆排序算法。58堆排序的算法voidHeapSort(HeapType&H){ ElemTypetemp; for(inti=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); }}59算法分析若設(shè)堆中有n個結(jié)點，且2k-1

n

2k，則對應(yīng)的完全二叉樹有k層。在第i層上的結(jié)點數(shù)2i-1(i=1,…,k)。在第一個形成初始堆的for循環(huán)中對每一個非葉結(jié)點調(diào)用了一次堆調(diào)整算法HeapAdjust()，因此該循環(huán)所用的計算時間為：其中，i是層序號，2i-1是第i層的最大結(jié)點數(shù)，(k-i+1)是第i層結(jié)點的高度,(k-i)是第i層結(jié)點能夠移動的最大距離。60在第二個for循環(huán)中，調(diào)用了n-1次HeapAdjust()算法，該循環(huán)的計算時間為O(nlog2n)(見教材283頁)。因此，堆排序的時間復(fù)雜性為O(nlog2n)。該算法的附加存儲主要是在第二個for循環(huán)中用來執(zhí)行對象交換時所用的一個臨時對象。因此，該算法的空間復(fù)雜性為O(1)。堆排序是一個不穩(wěn)定的排序方法。6110.5歸并排序歸并排序的基本思想假設(shè)初始序列有n個記錄，則可看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2的或1的有序子序列；再兩兩歸并，……，如此重復(fù)，直至得到一個長度為n的有序序列為止，這種方法稱為2-路歸并排序。歸并將兩個或兩個以上的有序表組合成一個新的有序表。62歸并排序舉例初始關(guān)鍵字[49][38][65][97][76][13][27]一趟歸并之后[3849][6597][1376][27]二趟歸并之后[38496597][132776]三趟歸并之后[13273849657697]63兩路歸并算法(教材283頁)voidMerge(ElemTypeSR[],ElemTypeTR[],inti,intm,intn){ for(intj=m+1,k=i;i<=m&&j<=n;++k){ if(LQ(SR[i].key,SR[j].key)) TR[k]=SR[i++]; elseTR[k]=SR[j++]; }64if(i<=m) for(intn1=k,n2=i;n1<=n&&n2<=m;n1++,n2++) TR[n1]=SR[n2]; if(j<=n) for(intn1=k,n2=j;n1<=n&&n2<=n;n1++,n2++) TR[n1]=SR[n2];}65遞歸形式的兩路歸并算法(教材284頁)voidMSort(ElemTypeSR[],ElemTypeTR1[],ints,intt){ ElemTypeTR2[MAXSIZE]; if(s==t)TR1[s]=SR[s]; else{ intm=(s+t)/2; MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t); Merge(TR2,TR1,s,m,t); }}voidMergeSort(SqList&L){ MSort(L.r,L.r,1,L.length);}66在歸并排序算法中，遞歸深度為O(log2n)，對象關(guān)鍵字的比較次數(shù)為O(nlog2n)。算法總的時間復(fù)雜度為O(nlog2n)。歸并排序占用附加存儲較多，需要另外一個與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組。這是這個算法的缺點。歸并排序是一個穩(wěn)定的排序方法。算法分析6710.6基數(shù)排序基數(shù)排序是采用“分配”與“收集”的辦法，用對多關(guān)鍵字進行排序的思想實現(xiàn)對單關(guān)鍵字進行排序的方法。68以撲克牌排序為例。每張撲克牌有兩個“關(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多關(guān)鍵字排序69多關(guān)鍵字排序這就是多關(guān)鍵字排序。排序后形成的有序序列叫做詞典有序序列。對于上例兩關(guān)鍵字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。一般情況下，假定有一個n個對象的序列{V0,V1,…,Vn-1}，且每個對象Vi中含有d個關(guān)鍵字如果對于序列中任意兩個對象Vi和Vj(0

i<j

n-1)都滿足：70多關(guān)鍵字排序則稱序列對關(guān)鍵字(K1,K2,…,Kd)有序。其中，K1稱為最高位關(guān)鍵字，Kd稱為最低位關(guān)鍵字。如果關(guān)鍵字是由多個數(shù)據(jù)項組成的數(shù)據(jù)項組，則依據(jù)它進行排序時就需要利用多關(guān)鍵字排序。實現(xiàn)多關(guān)鍵字排序有兩種常用的方法最高位優(yōu)先MSD(MostSignificantDigitfirst)最低位優(yōu)先LSD(LeastSignificantDigitfirst)最高位優(yōu)先法通常是一個遞歸的過程：先根據(jù)最高位關(guān)鍵字K1排序,得到若干對象組，對象組中每個對象都有相同關(guān)鍵字K1。71多關(guān)鍵字排序再分別對每組中對象根據(jù)關(guān)鍵字K2進行排序，按K2值的不同，再分成若干個更小的子組，每個子組中的對象具有相同的K1和K2值。依此重復(fù)，直到對關(guān)鍵字Kd完成排序為止。最后，把所有子組中的對象依次連接起來，就得到一個有序的對象序列。最低位優(yōu)先法首先依據(jù)最低位關(guān)鍵字Kd對所有對象進行一趟排序，再依據(jù)次低位關(guān)鍵字Kd-1對上一趟排序的結(jié)果再排序，依次重復(fù)，直到依據(jù)關(guān)鍵字K1最后一趟排序完成，就可以得到一個有序的序列。使用這種排序方法對每一個關(guān)鍵字進行排序時，不需要再分組，而是整個對象組都參加排序。72多關(guān)鍵字排序LSD和MSD方法也可應(yīng)用于對一個關(guān)鍵字進行的排序。此時可將單關(guān)鍵字Ki看作是一個子關(guān)鍵字組：73鏈?zhǔn)交鶖?shù)排序基數(shù)排序是典型的LSD排序方法，利用“分配”和“收集”兩種運算對單關(guān)鍵字進行排序。在這種方法中，把單關(guān)鍵字Ki

看成是一個d元組：其中的每一個分量(1

jd)也可看成是一個關(guān)鍵字。74鏈?zhǔn)交鶖?shù)排序分量(1

j

d)有radix種取值，則稱radix為基數(shù)。例如，關(guān)鍵字984可以看成是一個3元組(9,8,4)，每一位有0,1,…,9等10種取值，基數(shù)radix=10。關(guān)鍵字‘data’可以看成是一個4元組(d,a,t,a)，每一位有‘a(chǎn)’,‘b’,…,‘z’等26種取值，radix=26。針對d元組中的每一位分量，把對象序列中的所有對象,按的取值，先“分配”到rd個隊列中去。然后再按各隊列的順序，依次把對象從隊列中“收集”起來，這樣所有對象按取值排序完成。75鏈?zhǔn)交鶖?shù)排序如果對于所有對象的關(guān)鍵字K0,K1,…,Kn-1，依次對各位的分量，讓j=d,d-1,…,1，分別用這種“分配”、“收集”的運算逐趟進行排序，在最后一趟“分配”、“收集”完成后，所有對象就按其關(guān)鍵字的值從小到大排好序了。各隊列采用鏈?zhǔn)疥犃薪Y(jié)構(gòu)，分配到同一隊列的關(guān)鍵字用鏈接指針鏈接起來。每一隊列設(shè)置兩個隊列指針：intfront[radix]指示隊頭，intrear[radix]指向隊尾。為了有效地存儲和重排n個待排序?qū)ο螅造o態(tài)鏈表作為它們的存儲結(jié)構(gòu)。在對象重排時不必移動對象，只需修改各對象的鏈接指針即可。76基數(shù)排序的“分配”與“收集”過程第一趟614921485637738101215530790306第一趟分配（按最低位i=3）re[0]re[1]re[2]re[3]re[4]re[5]re[6]re[7]re[8]re[9]614738921485637101215530790306fr[0]