數(shù)據(jù)結(jié)構(gòu)第10章

第10章內(nèi)部排序1.排序的基本概念排序：將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)，使之按關(guān)鍵字遞增(或遞減)有序排列。310578363510

3678排序:設(shè)n

個(gè)記錄的序列為{R1,R2,R3,...,Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2,K3,...,Kn}若規(guī)定1,2,3,...,n的一個(gè)排列p1,p2,p3,...,pn

，使得相應(yīng)的關(guān)鍵字滿足如下非遞減關(guān)系:Kp≤Kp≤Kp≤...≤Kp123n則原序列變?yōu)橐粋€(gè)按關(guān)鍵字有序的序列:Rp,Rp,Rp,...,Rp123n{}此操作過(guò)程稱為排序。穩(wěn)定排序與不穩(wěn)定排序假設(shè)Ki=Kj

，且排序前序列中Ri

領(lǐng)先于Rj

；若在排序后的序列中Ri

仍領(lǐng)先于Rj

，則稱排序方法是穩(wěn)定的。若在排序后的序列中Rj

領(lǐng)先于Ri

，則稱排序方法是不穩(wěn)定的。例，序列3158

869若排序后得368

8915穩(wěn)定的若排序后得368

8915不穩(wěn)定的排序的時(shí)間開(kāi)銷(xiāo)：算法執(zhí)行中關(guān)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)來(lái)衡量。對(duì)于那些受關(guān)鍵字序列初始排列及記錄個(gè)數(shù)影響較大的，需要按最好情況和最壞情況進(jìn)行估算。內(nèi)部排序與外部排序內(nèi)部排序:

指的是待排序記錄存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中進(jìn)行的排序過(guò)程。外部排序:

指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過(guò)程中尚需對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程。排序方法分類(lèi)排序內(nèi)部排序外部排序涉及存儲(chǔ)器不同策略(原則)不同工作量不同插入排序交換排序選擇排序歸并排序計(jì)數(shù)排序簡(jiǎn)單的排序方法先進(jìn)的排序方法基數(shù)排序待排序的順序表類(lèi)型的類(lèi)型定義

#defineMAXSIZE20//表長(zhǎng)

typedefintKeyType;//關(guān)鍵字類(lèi)型

typedefstruct{ KeyTypekey;//關(guān)鍵字項(xiàng)

InfoTypeotherType;//其它數(shù)據(jù)項(xiàng)

}RecType;//記錄類(lèi)型

typedefstruct{RecTyper[MAXSIZE+1];//r[0]哨兵單元

intlength;}SqList;10.2插入排序插入排序(InsertionSort)的基本思想是：每次將一個(gè)待排序的記錄,按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子表中的適當(dāng)位置,直到全部記錄插入完成為止。

5種插入排序方法：

(1)直接插入排序;(2)折半插入排序;(3)2-路插入排序;(4)表插入排序;(5)希爾排序。10.2.1直接插入排序思想:利用有序表的插入操作進(jìn)行排序有序表的插入:

將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的有序表。例，序列132738657697插入4913273849

657697例，序列49386597761327初始，S={49}；{3849}算法描述:初始，令第1

個(gè)元素作為初始有序表；依次插入第

2,3,…,k

個(gè)元素構(gòu)造新的有序表；直至最后一個(gè)元素；{384965}{38496597}{3849657697}{133849657697}{13273849657697}直接插入排序算法主要應(yīng)用比較和移動(dòng)兩種操作。voidInsertSort(SqList&L){for(i=2;i<=L.length;++i){

if(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;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];

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

}}算法分析需1個(gè)記錄的輔助空間r[0];記錄個(gè)數(shù)為n，則n-1趟插入;最好情況下(正序)

記錄不需移動(dòng)。最差情況下(逆序)

直接插入排序所需進(jìn)行關(guān)鍵字間的比較次數(shù)和記錄移動(dòng)次數(shù)約為：n2/4，算法時(shí)間復(fù)雜度為：O(n2)。直接插入排序是一個(gè)穩(wěn)定的排序方法。2.折半插入排序基本思想：r[1..i-1]已為有序序列，在插入r[i]時(shí)，利用折半查找法尋找r[i]的插入位置。voidBInsertSort(SqList&L){for(i=2;i<=L.length;++i){L.r[0]=L.r[i];low=1;high=i-1;

while(low<=high){m=(low+high)/2;if(L.r[0].key<L.r[m].key)high=m-1;elselow=m+1;}

for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];

L.r[high+1]=L.r[0];}}算法分析關(guān)鍵字比較次數(shù)與待排序序列的初始狀態(tài)無(wú)關(guān)，僅依賴于記錄個(gè)數(shù)。在插入第i個(gè)記錄時(shí)，需要經(jīng)過(guò)

log2(i-1)

+1

次關(guān)鍵字比較，才能確定它應(yīng)插入的位置。折半插入排序的記錄移動(dòng)次數(shù)與直接插入排序相同，依賴于記錄的初始排列。折半插入排序的時(shí)間復(fù)雜度為O(n2)。折半插入排序是一個(gè)穩(wěn)定的排序方法。3.2-路插入排序目的是減少記錄移動(dòng)的次數(shù)以第一個(gè)記錄為界，小于第一個(gè)記錄的插入到前半部分，否則插入后半部分第一個(gè)記錄不動(dòng)，視為中間位置將整個(gè)數(shù)組視為一個(gè)循環(huán)隊(duì)列，設(shè)置first和final兩個(gè)指針指向第一個(gè)記錄和最后一個(gè)記錄3.2-路插入排序初始關(guān)鍵字

4938659776132749i=1

(49)↑↑first

finali=2

(49)

(38)

↑final↑firsti=3

(4965)

(38)

↑final↑firsti=4

(496597)

(38)

↑final↑first….i=8

(4949657697132738)↑final↓first算法分析為了減少記錄的移動(dòng)次數(shù)，需n個(gè)記錄的輔助空間。移動(dòng)記錄的次數(shù)約為n2/8。2-路插入排序的時(shí)間復(fù)雜度為O(n2)。2-路插入排序是一個(gè)穩(wěn)定的排序方法。4.表插入排序目的是不移動(dòng)記錄，只改變指針每個(gè)記錄維護(hù)一個(gè)next指針，構(gòu)成一個(gè)循環(huán)鏈表插入動(dòng)作體現(xiàn)為改變next指針4.表插入排序MAXINT4938659776132749681504723初始狀態(tài)i=2201------i=32310-----i=423

14

0----i=523

1504---i=663

15042--i=763

15047

2-i=8681504723012345678MAXINT493865977613274910-------MAXINT13276597764938496(6)(7)504813MAXINT13273849769765496(6)(7)(7)(6)4053i=1,p=6MAXINT13386597764927496(6)1504823MAXINT13273849499765766(6)(7)(7)(6)(8)054MAXINT13273897764965496(6)(7)(7)04853MAXINT13273849496576976(6)(7)(7)(6)(8)(7)(8)0MAXINT13273849496597766(6)(7)(7)(6)(8)(7)04012345678i=2,p=7i=3,p=(2),7i=4,p=(1),6i=5,p=8i=6,p=(3),7i=7,p=(5),8靜態(tài)鏈表類(lèi)型定義#defineSIZE100typedefstruct{RcdTyperc;//記錄項(xiàng)

intnext;//指針項(xiàng)}SLNode;//表結(jié)點(diǎn)類(lèi)型typedefstruct{SLNoder[SIZE];//0號(hào)單元為表頭結(jié)點(diǎn)

intlength;}SLinkListType;//靜態(tài)鏈表類(lèi)型voidArrange(SLinkListType&SL){p=SL.r[0].next;for(i=1;i<SL.length;++I){//SL.r[1..i-1]已有序

while(p<i)p=SL.r[p].next;//找第i個(gè)記錄

q=SL.r[p].next;//指向尚未調(diào)整的表尾

if(p!=i){SL.r[p]←→SL.r[i];SL.r[i].next=p;}

p=q;}}算法分析：修改2n次指針代替記錄移動(dòng)，關(guān)鍵字比較次數(shù)與直接插入排序相同；重排最壞情況下進(jìn)行3(n-1)次記錄移動(dòng)。算法時(shí)間復(fù)雜度：O(n2).5.希爾排序(Shell’sSort)1959年“縮小增量排序”基本思想：待排記錄按關(guān)鍵字“基本有序”，即具有特性L.r[i].key<Max{L.r[j].key}(1≤j＜i)的記錄較少。先將整個(gè)待排序列分割成若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列“基本有序”時(shí)，再對(duì)全體序列進(jìn)行一次直接插入排序。子序列的構(gòu)成不是簡(jiǎn)單地“逐段分割”，而是將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。思想:先將待排序記錄序列分割成為若干子序列分別進(jìn)行直接插入排序；待整個(gè)序列中的記錄基本有序后，再全體進(jìn)行一次直接插入排序。例，序列493865977613274855419第一趟排序Gap=5491319382765489755764131949273848655597476第二趟排序Gap=313194927384865559747613553876274

654948199713385576427

4965194897第三趟排序Gap=14131927

38

4849

556576

97voidShellInsert(SqList&L,intGap){for(i=Gap+1;i<=L.length;++i)if(L.r[i].key<L.r[i-Gap].key){//L.r[i]插入有序增量子表

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

for(j=i-Gap;j>0&&(L.r[0].key<L.r[j].key);j-=Gap)L.r[j+Gap]=L.r[j];

L.r[j+Gap]=L.r[0];}}voidShellSort(SqList&L,intdlta[],intt){for(k=0;k<t;++k)ShellInsert(L,dlta[k]);}開(kāi)始時(shí)Gap的值較大，子序列中的記錄較少，排序速度較快；隨著排序進(jìn)展，Gap值逐漸變小，子序列中記錄個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)序列已基本有序，所以排序速度仍然很快。關(guān)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整的數(shù)學(xué)分析，還沒(méi)有人能夠做到(難題）。Gap的取法有多種。最初shell提出取gap=

n/2

，gap=

gap/2

，直到gap=1。后來(lái)knuth提出取gap=

gap/3

+1。還有人提出都取奇數(shù)為好，也有人提出各gap互質(zhì)為好。Knuth利用大量的實(shí)驗(yàn)統(tǒng)計(jì)資料得出，當(dāng)n很大時(shí)，關(guān)鍵字平均比較次數(shù)和記錄平均移動(dòng)次數(shù)大約在n1.25到1.6n1.25

的范圍內(nèi)，當(dāng)n→∞時(shí)，可減少到n(log2n)2。這是在利用直接插入排序作為子序列排序方法的情況下得到的。希爾排序不是穩(wěn)定的排序方法。算法分析10.3交換排序10.3.1起泡排序思想:

通過(guò)不斷比較相鄰元素大小，進(jìn)行交換來(lái)實(shí)現(xiàn)排序。首先將第一個(gè)元素與第二個(gè)元素比較大小，若為逆序，則交換；然后比較第二個(gè)元素與第三個(gè)元素的大小，若為逆序，則交換；...直至比較第n-1個(gè)元素與第n個(gè)元素的大小，若為逆序，則交換；第一趟排序:結(jié)果:關(guān)鍵字最大的記錄被交換至最后一個(gè)元素位置上。例，序列4938761327493876132738

49

13

27384913762776初始第一趟排序后最大值13

492749次大值第二趟排序后3813

27132713382738第三趟排序后第四趟排序后voidBubbleSort(SqList&L){for(i=L.length,change=TRUE; i>1&&change;--i){ change=FALSE; for(j=1;j<i;j++)

if(L.r[j].key>L.r[j+1].key) {L.r[j]

L.r[j+1]; change=TRUE; }

}}算法分析正序：進(jìn)行n-1次關(guān)鍵字的比較，且不移動(dòng)記錄；逆序：進(jìn)行n-1趟排序記錄移動(dòng)次數(shù)：關(guān)鍵字比較次數(shù)：起泡排序的時(shí)間復(fù)雜度：O(n2).起泡排序是一種穩(wěn)定的排序方法。2.快速排序基本思想：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分的關(guān)鍵字均比另一部分的關(guān)鍵字小，再對(duì)這兩部分繼續(xù)排序。初始關(guān)鍵字49386597761327

49

pivotkey=49↑i↑j↓進(jìn)行一次交換后27386597761349

↑j↑i↓進(jìn)行二次交換后27389776136549

↑j↑i↓進(jìn)行三次交換后27381397766549

↑i↓↑j進(jìn)行四次交換后27381376976549

↑j↑i完成一趟排序(273813)49(76976549)

一次劃分一次劃分后(273813)

49

(76976549)

初始關(guān)鍵字4938659776132749

分別進(jìn)行劃分(13)

27

(38)49(4965)

76

(97)

1327384949

(65)7697voidQSort(SqList&L,intlow,inthigh){if(low<high){

pivotloc=Partition(L,low,high);

QSort(L,low,pivotloc–1);QSort(L,pivotloc+1,high);}}1327384949657697intPartition(SqList&L,intlow,inthigh){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];

while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];}

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

returnlow;}算法分析1397497627384965最壞情況(有序)，遞歸樹(shù)成為單支樹(shù)，每次劃分只得到一個(gè)比上一次少一個(gè)記錄的子序列?？偟年P(guān)鍵字比較次數(shù)達(dá)到：占用附加存儲(chǔ)(即棧)將達(dá)到O(n)。最好情況(基準(zhǔn)為中值，左右子區(qū)間大致相等)：在n個(gè)元素的序列中，對(duì)一個(gè)記錄定位所需時(shí)間為O(n)，設(shè)T(n)是對(duì)n個(gè)記錄的序列進(jìn)行排序所需的時(shí)間，總的計(jì)算時(shí)間為：T(n)

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

cn+2(cn/2+2T(n/22))=2cn+22T(n/22)

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

kcn+2kT(n/2k)=cnlog2n+nT(1)可以證明，QuickSort平均時(shí)間復(fù)雜度也是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就平均計(jì)算時(shí)間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個(gè)。遞歸調(diào)用層次數(shù)與遞歸樹(shù)的深度一致

log2n+1對(duì)于n較大的平均情況而言，快速排序是“快速”的，但是當(dāng)n很小時(shí)，這種排序方法往往比其它簡(jiǎn)單排序方法還要慢。有一種改進(jìn)辦法：取每個(gè)待排序?qū)ο笮蛄械牡谝粋€(gè)對(duì)象、最后一個(gè)對(duì)象和位置接近正中的3個(gè)對(duì)象，取其關(guān)鍵字居中者作為基準(zhǔn)對(duì)象?？焖倥判蚴且环N不穩(wěn)定的排序方法。10.4選擇排序思想:

每一趟都選出一個(gè)最大或最小的元素，并放在合適的位置。

簡(jiǎn)單選擇排序

樹(shù)形選擇排序

堆排序10.4.1簡(jiǎn)單選擇排序思想:第1趟選擇:從1—n

個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第1個(gè)記錄交換。第2趟選擇:從2—n

個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第2

個(gè)記錄交換。第n-1趟選擇:從n-1—n

個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第n-1

個(gè)記錄交換。...例，序列4938976576第1趟選擇:min3849976576第2趟選擇:min38

49976576第3趟選擇:min38

49

659776第4趟選擇:min38

49

65

7697

簡(jiǎn)單(直接)選擇排序記錄移動(dòng)次數(shù)：最好：0次；最壞：3(n-1).2.樹(shù)形選擇排序(錦標(biāo)賽排序)n個(gè)記錄的關(guān)鍵字，進(jìn)行兩兩比較，得到

n/2

個(gè)比較的優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來(lái)。然后對(duì)這

n/2

個(gè)記錄再進(jìn)行關(guān)鍵字的兩兩比較，…，如此重復(fù)，直到選出一個(gè)關(guān)鍵字最小的記錄為止。{21,25,49,25*,16,08,63}082108086325*2121254925*160863162116166325*2121254925*16632121636325*2121254925*63錦標(biāo)賽排序構(gòu)成的樹(shù)是滿的完全二叉樹(shù)，其深度為

log2n+1，其中n為待排序記錄個(gè)數(shù)。除第一次選擇具有最小關(guān)鍵字的記錄需要進(jìn)行n-1次關(guān)鍵字比較外，選擇具有次小、再次小關(guān)鍵字記錄所需的關(guān)鍵字比較次數(shù)均為O(log2n)?？傟P(guān)鍵字比較次數(shù)為O(nlog2n)。記錄的移動(dòng)次數(shù)不超過(guò)關(guān)鍵字的比較次數(shù)，所以錦標(biāo)賽排序總的時(shí)間復(fù)雜度為O(nlog2n)。這種排序方法雖然減少了許多排序時(shí)間，但是使用了較多的附加存儲(chǔ)。錦標(biāo)賽排序是一個(gè)穩(wěn)定的排序方法。算法分析3.堆排序(HeapSort)將r[1..n]看成是一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu),利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系,在當(dāng)前無(wú)序區(qū)中選擇關(guān)鍵字最大(或最小)的記錄。堆的定義：n個(gè)關(guān)鍵字序列K1,K2,…,Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡(jiǎn)稱為堆性質(zhì))：

(1)Ki≤K2i

且Ki≤K2i+1或

(2)Ki≥K2i

且Ki≥K2i+1(1≤i≤n/2)滿足第(1)種情況的堆稱為“小頂堆”,滿足第(2)種情況的堆稱為“大頂堆”。{96,83,27,38,11,9}{12,36,24,85,47,30}85122436473038962783119小頂堆大頂堆堆排序解決2個(gè)問(wèn)題①如何由一個(gè)無(wú)序序列建成一個(gè)堆？②如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個(gè)新的堆？492525*21160812456349252125*1608082525*16214913654208252125*16492525*082116491234562525*210816491625*210825491625*08252149025431自堆頂至葉子的調(diào)整過(guò)程為“篩選”。25*162108254908162125*2549081625*25214913654225*160821254912345621160825*254908162125*2549211625*082549123456081625*25214913654216082125*254908162125*2549160825*212549123456081625*252149136542①如何由一個(gè)無(wú)序序列建成一個(gè)堆？反復(fù)“篩選”的過(guò)程。從i=n/2到1,反復(fù)“篩選”。212525*491608123456i212525*164908025431i21254925*160821254925*1608初始關(guān)鍵字集合212525*49160812345621254925*160849252125*1608492525*162108136542最大堆的初始化根據(jù)inta[10]={20,12,35,15,10,80,30,17,2,1}建立最大堆12345678910算法：從第一個(gè)具有孩子的結(jié)點(diǎn)i開(kāi)始（i=[n/2]），如果以這個(gè)元素為根的子樹(shù)已是最大堆，則不需調(diào)整，否則需調(diào)整子樹(shù)使之成為堆。繼續(xù)檢查i-1，i-2等結(jié)點(diǎn)為根的子樹(shù)，直到檢查整個(gè)二叉樹(shù)的根結(jié)點(diǎn)(其位置為１)。最大堆的初始化step1已知n=10;i=n/2=5;12345678910i2012351510803017210123456789最大堆的初始化step2i=4123456789102012351510803017210123456789i2i2i+1最大堆的初始化step3i=3123456789102012351710803015210123456789i2i2i+1最大堆的初始化step4_0i=2123456789102012801710353015210123456789i2i2i+1最大堆的初始化step4_1i=2,j=2i=4123456789102017801210353015210123456789j2j2j+1最大堆的初始化step5_0i=5123456789102017801510353012210123456789i2i2i+1最大堆的初始化step5_1i=1,j=2i+1=3123456789108017201510353012210123456789j2j2j+1最大堆的初始化step5_2123456789108017351510203012210123456789typedefSqListHeapType;voidHeapAdjust(HeapType&H,ints,intm){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;}voidHeapSort(HeapType&H){

for(i=H.length/2;i>0;--i)//建立初始堆

HeapAdjust(H,i,H.length);

for(i=H.length;i>1;--i){H.r[1]←→H.r[i];HeapAdjust(H,1,i-1);}}算法分析深度為k的堆，篩選算法中進(jìn)行的關(guān)鍵字比較次數(shù)至多為2(k-1)。

建初始堆進(jìn)行了

n/2次篩選，關(guān)鍵字比較次數(shù)至多為：n個(gè)關(guān)鍵字，完全二叉樹(shù)的深度

log2n+1。調(diào)整建立新堆時(shí)，調(diào)用HeapAdjust過(guò)程n-1次，關(guān)鍵字比較次數(shù)至多為：堆排序的時(shí)間復(fù)雜度為O(nlog2n)，空間復(fù)雜性為O(1).堆排序是一個(gè)不穩(wěn)定的排序方法。作業(yè)：

10.12歸并:是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。2-路歸并：假設(shè)初始序列有n個(gè)記錄，首先把它看成是n個(gè)長(zhǎng)度為1的有序子序列(歸并項(xiàng))，先做兩兩歸并，得到

n/2

個(gè)長(zhǎng)度為2的歸并項(xiàng)(如果n為奇數(shù)，則最后一個(gè)有序子序列的長(zhǎng)度為1)；再做兩兩歸并，…，如此重復(fù)，最后得到一個(gè)長(zhǎng)度為n的有序序列。10.5歸并排序(MergingSort)212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293h=1h=2h=4h=8h=16采用2-路歸并排序方法進(jìn)行排序的過(guò)程(11個(gè)記錄)。1趟歸并后2趟歸并后3趟歸并后4趟歸并后

一趟歸并進(jìn)行

n/(2*h)

次兩個(gè)有序子表的歸并操作Merger.將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n].voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){for(j=m+1,k=i;i<=m&&j<=n;++k){

if(SR[i].key<=SR[j].key)TR[k]=SR[i++];

elseTR[k]=SR[j++];}if(i<=m)TR[k..n]=SR[i..m];if(j<=n)TR[k..n]=SR[j..n];}有序子表長(zhǎng)度分別為：n,m.則Merge的時(shí)間復(fù)雜度為：O(n+m).voidMergePass(RcdTypeSR[],RcdType&TR[],inth,intn){for(i=1;i+2*h-1<=n;i=i+2*h)//歸并h長(zhǎng)的兩相鄰子表

Merge(SR,TR,i,i+h-1,i+2*h-1);if(i+h-1<=n)//余下部分

Merge(SR,TR,i,i+h-1,n);}迭代的歸并排序算法（一趟歸并排序的情形）voidMergeSort(SqList&L)//自底向上的二路歸并算法

{RcdTypeTR[];for(h=1;h<L.length;h=2*h) {MergePass(L.r,TR,h,L.length); L.r[1..L.length]=TR[1..L.length]; }}Merge調(diào)用n/(2*h)

次MergePass調(diào)用log2n

次算法總的時(shí)間復(fù)雜度:O(nlog2n)遞歸的歸并排序算法voidMSort(RcdTypeSR[],RcdType&TR1[],ints,intt){if(s==t)TR1[s]=SR[s];else{

m=(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);}算法分析在迭代的歸并排序算法中，函數(shù)MergePass()做一趟兩路歸并排序，要調(diào)用merge()函數(shù)

n/(2*h)

次，函數(shù)MergeSort()調(diào)用MergePass()正好

log2n

次，而每次merge()至多執(zhí)行比較2h次，所以算法總的時(shí)間復(fù)雜度為O(nlog2n)。遞歸的歸并排序方法的遞歸深度為

log2n

，算法總的時(shí)間復(fù)雜度為O(nlog2n)。歸并排序占用附加存儲(chǔ)較多，需要另外一個(gè)與原待排序記錄數(shù)組同樣大小的輔助數(shù)組。O(n)

這是這個(gè)算法的缺點(diǎn)。歸并排序是一個(gè)穩(wěn)定的排序方法。10.6基數(shù)排序(RadixSort)基數(shù)排序是通過(guò)“分配”和“收集”過(guò)程來(lái)實(shí)現(xiàn)排序,是一種借助于多關(guān)鍵字排序的思想對(duì)單關(guān)鍵字排序的方法。1.多關(guān)鍵字排序每張撲克牌有兩個(gè)“關(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有n

個(gè)記錄的序列{R1,R2,…,Rn}，且每個(gè)記錄Ri

中含有d

個(gè)關(guān)鍵字序列中任意兩個(gè)對(duì)象Ri和Rj(1

i<j

n)都滿足：

則稱序列對(duì)關(guān)鍵字(K1,K2,…,Kd)

有序。其中，K1

稱為最主位關(guān)鍵字，Kd稱為最次位關(guān)鍵字。實(shí)現(xiàn)多關(guān)鍵字排序有兩種常用的方法最高位優(yōu)先MSD(MostSignificantDigitfirst)最低位優(yōu)先LSD(LeastSignificantDigitfirst)最高位優(yōu)先法：先根據(jù)最高位關(guān)鍵字K1排序,得到若干組，每組中每個(gè)記錄都有相同關(guān)鍵字K1。再分別對(duì)每組中記錄根據(jù)關(guān)鍵字K2進(jìn)行排序，按K2值的不同，再分成若干個(gè)更小的子組，每個(gè)子組中的記錄具有相同的K1和K2值。依此重復(fù)，直到對(duì)關(guān)鍵字Kd完成排序?yàn)橹?。最后，把所有子組中的記錄依次連接起來(lái)，就得到一個(gè)有序的序列。最低位優(yōu)先法：首先依據(jù)最低位關(guān)鍵字Kd對(duì)所有記錄進(jìn)行一趟排序，再依據(jù)次低位關(guān)鍵字Kd-1對(duì)上一趟排序的結(jié)果再排序，依次重復(fù)，直到依據(jù)關(guān)鍵字K1最后一趟排序完成，就可以得到一個(gè)有序的序列。使用這種排序方法對(duì)每一個(gè)關(guān)鍵字進(jìn)行排序時(shí)，不需要再分組，而是整個(gè)記錄都參加排序。52張牌排序方法:最高位優(yōu)先法(MSDF):先按不同“花色”分成有次序的4堆，每一堆均具有相同的花色；然后分別對(duì)每一堆按“面值”大小整理有序。最低位優(yōu)先法(LSDF):先按不同“面值”分成13堆；然后將這13堆牌自小至大疊在一起(2,3,...,A)；然后將這付牌整個(gè)顛倒過(guò)來(lái)再重新按不同的“花色”分成4堆；最后將這4堆牌按自小至大的次序合在一起。收集分配2.鏈?zhǔn)交鶖?shù)排序基數(shù)排序是典型的LSD排序方法，利用“分配”和“收集”兩種運(yùn)算對(duì)單關(guān)鍵字進(jìn)行排序。在這種方法中，把單關(guān)鍵字Ki

看成是一個(gè)d元組：分量有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。記錄的關(guān)鍵字K0,K1,…,Kd-1，依次對(duì)各位的分量，分別用“分配”、“收集”的運(yùn)算逐趟進(jìn)行排序，各隊(duì)列采用鏈?zhǔn)疥?duì)列結(jié)構(gòu)，分配到同一隊(duì)列的關(guān)鍵字用指針鏈接起來(lái)。每一隊(duì)列設(shè)置兩個(gè)指針:front[radix]指示隊(duì)頭,rear[radix]指向隊(duì)尾。以靜態(tài)鏈表作為n個(gè)記錄的存儲(chǔ)結(jié)構(gòu)。在記錄重排時(shí)不必移動(dòng)記錄，只需修改各記錄的鏈接指針即可。例，序列278109063930589184505269008083第一趟分配0123456789278109063930589184505269008083第一趟收集930063083184505278008109589269第二趟分配0123456789930063083184505278008109589269第二趟收集505008109930063269278083184589第二趟收集505008109930063269278083184589第三趟分配0123456789505008109930063269278083184589第三趟收集008063083109184269278505589930算法分析若每個(gè)關(guān)鍵字有d位，需要重復(fù)執(zhí)行d趟“分配”與“收集”。每趟對(duì)n個(gè)記錄進(jìn)行“分配”，對(duì)radix個(gè)隊(duì)列進(jìn)行“收集”?？倳r(shí)間復(fù)雜度為

O(d(n+radix))。若基數(shù)radix相同，對(duì)于記錄個(gè)數(shù)較多而關(guān)鍵字位數(shù)較少的情況，使用鏈?zhǔn)交鶖?shù)排序較好?；鶖?shù)排序需要增加n+2*radix個(gè)附加鏈接指針?；鶖?shù)排序是穩(wěn)定的排序方法。作業(yè)10.110.7各種內(nèi)部排序方法的比較討論1.選擇排序方法時(shí)需考慮的因素待排序的記錄數(shù)目；記錄本身信息量的大小；關(guān)鍵字的結(jié)構(gòu)及其分布情況；對(duì)排序穩(wěn)定性的要求；語(yǔ)言工具的條件，輔助空間的大小。2.各種內(nèi)部排序方法的性能排序方法比較次數(shù)

移動(dòng)次數(shù)穩(wěn)定性附加存儲(chǔ)最好最差最好最差最好最差直接插入排序nn20n2√

1折半插入排序nlog2n0n2√1起泡排序nn20n2√1快速排序nlog2nn2nlog2nn2×log2nn簡(jiǎn)單選擇排序n20n×1錦標(biāo)賽排序nlog2nnlog2n√n堆排序nlog2nnlog2n×1歸并排序nlog2nnlog2n√n3.結(jié)論沒(méi)有哪一種排序方法是絕對(duì)好的，都有其優(yōu)缺點(diǎn)若n較小，可采用直接插入排序或簡(jiǎn)單選擇排序若序列的初始狀態(tài)已按關(guān)鍵字基本有序，則選用直接插入或起泡排序?yàn)橐耍蝗鬾較大，采用O(nlog2n)的排序方法；若n很大，記錄的關(guān)鍵字位數(shù)較少且可以分解時(shí)，采用基數(shù)排序較好；避免移動(dòng)記錄，用鏈表作存儲(chǔ)結(jié)構(gòu)，如表插入；內(nèi)部排序可能達(dá)到的最快速度是什么？時(shí)間下界？時(shí)間上界O(n2)

任何借助于“比較”的排序方法，至少需要O(nlog2n)的時(shí)間。三個(gè)關(guān)鍵字：k1,k2,k3，則描述3個(gè)記錄排序過(guò)程的判定樹(shù)必有3!=6個(gè)葉子結(jié)點(diǎn)。n個(gè)記錄的序列，初始狀態(tài)有n!個(gè)，則描述n個(gè)記錄排序過(guò)程的判定樹(shù)必有n!個(gè)葉子結(jié)點(diǎn)。則判定樹(shù)的樹(shù)高至少為

log2n!

+1，log2n!≈nlog2n，最壞情況下能達(dá)到的最好的時(shí)間復(fù)雜度為O(nlog2n).練習(xí)1.在堆排序、起泡排序、簡(jiǎn)單選擇排序和快速排序中，