Merge sort等各種數(shù)據(jù)結(jié)構(gòu)排序算法

本文格式為Word版，下載可任意編輯——Mergesort等各種數(shù)據(jù)結(jié)構(gòu)排序算法數(shù)據(jù)局結(jié)構(gòu)——排序算法

一、復(fù)習(xí)要點(diǎn)

排序是使用最頻繁的一類算法。排序分內(nèi)排序與外排序。內(nèi)排序算法主要分5大類，有12個(gè)算法。在插入排序類中探討了直接插入排序、二分法插入排序、表插入排序和shell排序算法；在交換排序類中探討了起泡排序和快速排序算法；在選擇排序類中探討了簡單項(xiàng)選擇擇排序、錦標(biāo)賽排序和堆排序算法；路歸并排序和遞歸的表歸并排序算法；低位優(yōu)先的鏈表基數(shù)排序算法。其中，不穩(wěn)定的排序方法有序、簡單項(xiàng)選擇擇排序、快速排序和堆排序；適合于待排序?qū)ο髷?shù)目較大的排序方法有快速排序、堆排序、歸并排序和基數(shù)排序；排序碼比較次數(shù)不受對象排序碼初始排列影響的排序方法有折半插入排序、簡單項(xiàng)選擇擇排序、錦標(biāo)賽排序、兩路歸并排序和基數(shù)排序，其中，當(dāng)排序碼的初始排列接近有序時(shí)，直接插入排序和起泡排序等增長很快，而快速排序則變成慢速排序。外排序是基于外存的排序方法。以歸并排序最為適合。因此，外排序以象排序碼中選取最小排序碼，法。此外，還探討了初始?xì)w并段生成的方法，最正確歸并樹等問題。本章復(fù)習(xí)的要點(diǎn)是：1、基本知識點(diǎn)要求理解排序的基本概念，包括什么是排序，排序的穩(wěn)定性，排序的性能分析，數(shù)）和空間代價(jià)（附加對象個(gè)數(shù)）折半插入排序；鏈表插入排序）選擇排序（直接選擇排序；鏈表選擇排序；錦標(biāo)賽排序；堆排序）迭代的歸并排序等內(nèi)排序的方法及其性能分析方法。法及其性能分析方法。方法。理解生成初始?xì)w并段及敗者樹構(gòu)造方法。立方法。

2、算法設(shè)計(jì)?插入排序：直接插入排序算法、折半插入排序算法、鏈表插入排序算法

?交換排序：起泡排序算法，快速排序的遞歸算法和用棧實(shí)現(xiàn)的非遞歸算法

?選擇排序：直接選擇排序算法，鏈表選擇排序算法，堆排序算

在歸并排序類中探討了迭代的兩在多排序碼排序類中探討了最

由于外存以順序存取的效率最高，k路平衡歸并為主。在采用了敗者樹。這是一種高效的選擇算

（對象排序碼的比較次數(shù)和對象的移動次。把握插入排序（直接插入排序；、交換排序（起泡排序；快速排序）理解多路平衡歸并等外排序方法及敗者樹構(gòu)造理解最正確歸并樹的建179

shell排n比k個(gè)對

、、如時(shí)間代價(jià)理解基數(shù)排序方

法

?歸并排序：兩路歸并算法，迭代的歸并排序算法；遞歸的鏈表歸并排序算法和用隊(duì)列實(shí)現(xiàn)的非遞歸鏈表歸并排序算法

?其它排序算法：計(jì)數(shù)排序算法，奇偶排序算法

二、難點(diǎn)和重點(diǎn)

1、基本概念：排序碼、初始排序碼排列、排序碼比較次數(shù)、數(shù)據(jù)移動次數(shù)、穩(wěn)定性、附加存儲、內(nèi)部排序、外部排序2、插入排序?當(dāng)待排序的排序碼序列已經(jīng)基本有序時(shí)，3、選擇排序?用直接選擇排序在一個(gè)待排序區(qū)間中選出最小的數(shù)據(jù)時(shí)，間第一個(gè)數(shù)據(jù)對調(diào)，而不是順次后移。這導(dǎo)致方法不穩(wěn)定。?當(dāng)在序最快?錦標(biāo)賽排序的算法中將待排序的數(shù)據(jù)個(gè)數(shù)2k-1(或(4)快速排序

PivPvtp01245679排序碼比otos38較次數(shù)0,1,2,[1328101620189

*pos0pos1232pos2pos166]

0,11[21616203182[6

6pos2pos1028

*0]]

4,5,6,[2[11[2161620318287,8]60]28pospos*pospos0

pos]4,5,621[11616202[31861028pospos*pos]80]*421[1161[22301661026*pos]80]82116[11202306102*6]88

左子序列遞歸深度為1，右子序列遞歸深度為3。(5)直接選擇排序

初始789排序排列0123456較次數(shù)i=[1180221630281016*206]

i=[1181221630281016*206]

i=[118226630281016*2012]

i=[318326100281616*2012]

184

5

31

比9876

碼

i=42i=52i=[26101281616

*

[26101216816

*[21852030]

1842030]

18362610121616*8

2030]

i=[22872610121616*18

030]

i=[32882610121616*16

200]

[32

610121616*16

20280]

(6)錦標(biāo)賽排序2輸出2，調(diào)整勝者樹

2621062161016*61221630281016*20618當(dāng)參與排序的數(shù)據(jù)對象個(gè)數(shù)n不足2的某次冪時(shí)，將其補(bǔ)足到n=10，將葉結(jié)點(diǎn)個(gè)數(shù)補(bǔ)足到24=16個(gè)。排序碼=9。6輸出6，調(diào)整勝者樹10612106185

212

的某次冪。此題的比較次數(shù)

121610616*

1221630281016*20618

10輸出10，調(diào)整勝者樹

排序碼比較1018次數(shù)=1。

12101812161016*181221630281016*20618“不再參選〞，該結(jié)點(diǎn)自動升入12輸出12，調(diào)整勝者樹1218排序碼比較次數(shù)1216*1812162816*181221630281016*20618=3。某對象輸出后，對手自動升到雙親，不計(jì)入16輸出16，調(diào)整勝者樹1618排序碼比較次數(shù)1616*1812162816*181221630281016*2061816*

輸出16*，調(diào)整勝者樹186

=3。

=2。

當(dāng)某結(jié)點(diǎn)的比較對手的參選標(biāo)志為雙親結(jié)點(diǎn)，此動作不計(jì)入排序碼比較次數(shù)。

排序碼比較次數(shù)排序碼比較次數(shù)。

16*18排序碼比較次數(shù)=2。

3016*1812302816*181221630281016*2061818輸出18，調(diào)整勝者樹2018排序碼比較次數(shù)30201812302820181221630281016*2061820輸出20，調(diào)整勝者樹2018排序碼比較次數(shù)30201812302820181221630281016*2061828輸出28，調(diào)整勝者樹2818排序碼比較次數(shù)30281812302820181221630281016*2061830輸出30，排序完成3018排序碼比較次數(shù)30281812302820181221630281016*20618187

=3。

=0。

=2。

=0。

(7)堆排序

第一步，形成初始的最大堆(略)，其次步，做堆排序。

188

123012

21628162816

30281016*20181016*20181016*

2061826122630

初始排列，不是最大堆形成初始最大堆交換0#與9#對象202861816201620161261016*12181016*12181016*22830228302630從0#到8#重新形成堆交換0#與8#對象從0#到7#重新形成堆16*218

121618161216

2610181261016*261016*202830202830202830

交換0#與7#對象從0#到6#重新形成堆交換0#與6#對象

16*1016

121612161210

262616*182616*181018

202830202830202830從0#到5#重新形成堆交換0#與5#對象從0#到4#重新形成堆

2612

6101210610

121616*1821616*1821616*18

189

202830202830202830交換0#與4#對象從0#到3#重新形成堆交換0#與3#對象

190

2610

61021062

12161216121616*1816*1816*18

202830202830202830從0#到2#重新形成堆交換0#與2#對象從0#到1#重新形成堆

22

6106101216121616*1816*18

202830202830交換0#與1#對象從0#到1#重新形成堆，得到結(jié)果

(8)二路歸并排序

采用迭代的方法進(jìn)行歸并排序。設(shè)待排序的數(shù)據(jù)對象有n個(gè)。首先把每一個(gè)待排序的數(shù)據(jù)對象看作是長度為的初始?xì)w并項(xiàng)，然后進(jìn)行兩兩歸并，形成長度為2的歸并項(xiàng)，再對它們兩兩歸并，形成長度為4的歸并項(xiàng)，如此一趟一趟做下去，最終得到長度為n的歸并結(jié)果。

1221630281016*20618排序碼比較5次2121630102861816*2012排序碼比較6次*212163010162028618排序碼比較7次

*210121616202830618排序碼比較9次

2610121616*18202830

(9)基數(shù)排序61221630281016*2018

按最低位分派

r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]

620

2181016*

12162830f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]

191

收集30

10201221616*62818192

按最高位分派

r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]1816*16

62812

2102030f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]

610121618203016*28收集2

9-3在起泡排序過程中，什么狀況下排序碼會朝向與排序相反的方向移動，試舉例說明。在快速排序過程中有這種現(xiàn)象嗎？

假使在待排序序列的后面的若干排序碼比前面的排序碼小，則在起泡排序的過程中，排序碼可能向與最終它應(yīng)移向的位置相反的方向移動。例如，

574038111334487561997如9向相反方向移動657403811133448757199如19向相反方向移動

675740381113344875919如9向最終方向移動

679574038111334487519如13向相反方向移動

679115740381319344875如13向最終方向移動

679111357403819344875如34向相反方向移動

679111319574038344875679111319345740384875

9-4試修改起泡排序算法，在正反兩個(gè)方向交替進(jìn)行掃描，即第一趟把排序碼最大的對象放到序列的最終，其次趟把排序碼最小的對象放到序列的最前面。如此反復(fù)進(jìn)行。

靜態(tài)數(shù)據(jù)表類定義

193

#include

constintDefaultSize=100;

templateclassdataList//數(shù)據(jù)表的前視聲明

templateclassElement{//數(shù)據(jù)表元素類的定義

friendclassdataList;private:

Typekey;//排序碼

fieldotherdata;//其它數(shù)據(jù)成員public:

TypegetKey(){returnkey;}//取當(dāng)前結(jié)點(diǎn)的排序碼

voidsetKey(constTypex){key=x;}//將當(dāng)前結(jié)點(diǎn)的排序碼修改為x

Elementotherdata=x.otherdata;}

intoperator==(Elementx){returnkey==x.key;}//判this與x相等

intoperatorx){returnkey(Elementx){returnkey>x.key;}//判this大于x

intoperatorx){returnkey>x.key;}//判this小于x

}

templateclassdataList{

//用順序表來存儲待排序的元素，這些元素的類型是Typeprivate:

Element*Vector;//存儲待排序元素的向量

intMaxSize,CurrentSize;//最大元素個(gè)數(shù)與當(dāng)前元素個(gè)數(shù)

intPartition(constintlow,constinthigh)//用于快速排序的一次劃分算法

public:

datalist(intMaxSz=DefaultSize):MaxSize(Maxsz),CurrentSize(0)

{Vector=newElement[MaxSize];}//構(gòu)造函

194

數(shù)

intlength(){returnCurrentSize;}

Element}

voidswap(Elementx=y;y=temp;}voidSort();//排序}

templatevoiddataList::shaker_Sort(){//奇數(shù)趟對表Vector從前向后,比較相鄰的排序碼,遇到逆序即交換,直到把參與比較排序碼序列

//中最大的排序碼移到序列尾部。偶數(shù)趟從后向前,比較相鄰的排序碼,遇到逆序即交換,直到把

//參與比較排序碼序列中最小的排序碼移到序列前端。inti=1,j;intexchange;

while(i=i;j--)//逆向起泡if(Vector[j-1]>Vector[j]){//發(fā)生逆序

Swap(Vector[j-1],Vector[j]);//交換,最小排序碼放在Vector[i-1]處

exchange=1;//做“發(fā)生了交換〞標(biāo)志

}

if(exchange==0)break;////當(dāng)exchange為則中止排序

for(j=i;jVector[j+1]){//發(fā)生逆序

Swap(Vector[j],Vector[j+1]);//交換,最大排序碼放在Vector[n-i]處

exchange=1;//做“發(fā)生了交換〞標(biāo)志

}

if(exchange==0)break;//當(dāng)exchange為則中止排序

i++;

}

195

00}

templatevoiddataList::shaker_Sort(){intlow=1,high=CurrentSize-1,i,j;intexchange;

while(lowVector[i+1]){//Swap(Vector[i],Vector[i+1]);j=i;//記憶右邊最終發(fā)生交換的位置j

}

high=j;//比較范圍上界縮小到for(i=high;i>low;i--)//if(Vector[i-1]>Vector[i]){//Swap(Vector[i-1],Vector[i]);j=i;//記憶左邊最終發(fā)生交換的位置j

}

low=j;//比較范圍下界縮小到}}

9-5假使待排序的排序碼序列已經(jīng)按非遞減次序有序排列，數(shù)QuickSort()的計(jì)算時(shí)間將下降到O(n2)。

若待排序的n個(gè)對象的序列已經(jīng)按排序碼非遞減次序有序排列，且設(shè)排序的時(shí)間代價(jià)為T(n)。當(dāng)以第一個(gè)對象作為基準(zhǔn)對象時(shí)，一次劃分算法Partition，通過n-1次排序碼比較，把只能把整個(gè)序列劃分為：基準(zhǔn)對象的左子序列為空序列，右子序列為有非遞減有序序列。對于這樣的遞歸QuickSort()算法，其時(shí)間代價(jià)為T(n)=(n-1)+T(n-1)

=(n-1)+{(n-2)+T(n-2)}

=(n-1)+(n-2)+{(n-3)+T(n-3)}=??

=(n-1)+(n-2)+(n-3)+?+{2+T(1)}=(n-1)+(n-2)+(n-3)+?+2+1

196

//交換

//交換

試證明函n-1個(gè)對象的jj

正向起泡發(fā)生逆序反向起泡發(fā)生逆序應(yīng)用=n(n-1)/2=O(n2)

9-6在實(shí)現(xiàn)快速排序的非遞歸算法時(shí)，可根據(jù)基準(zhǔn)對象，將待排序排序碼序列劃分為兩個(gè)子序列。若下一趟首先對較短的子序列進(jìn)行排序，試證明在此做法下，快速排序所需要的棧的深度為O(log2n)。

由快速排序的算法可知,所需遞歸工作棧的深度取決于所需劃分的最大次數(shù)。假使在排序過程中每次劃分都能把整個(gè)待排序序列根據(jù)基準(zhǔn)對象劃分為左、右兩個(gè)子序列。假定這兩個(gè)子序列的長度相等，則所需棧的深度為

S(n)=1+S(n/2)=

=1+{1+S(n/4)}=2+S(n/4)=2+{1+S(n/8)}=3+S(n/8)=??

=log2n+S(1)=log2n(假設(shè)歸棧的深度為0)

假使每次遞歸左、右子序列的長度不等，并且先將較長的子序列的左、右端點(diǎn)保存在遞歸棧中，再對較短的子序列進(jìn)行排序，可用表示最壞狀況的大O表示法表示。此時(shí)其遞歸棧的深度不一定正好是log2n，其最壞狀況為O(log2n)。

9-7在實(shí)現(xiàn)快速排序算法時(shí)，可先檢查位于兩端及中點(diǎn)的排序碼，三者之中的數(shù)值不是最大也不是最小的排序碼作為基準(zhǔn)對象?；谶@種思想的快速排序算法，并證明對于已排序的排序碼序列，算法的計(jì)算時(shí)間為O(nlog2n)。參看教科書

9-8在使用非遞歸方法實(shí)現(xiàn)快速排序時(shí),序區(qū)間的兩個(gè)端點(diǎn)。那么能否用隊(duì)列來代替這個(gè)棧

可以用隊(duì)列來代替棧。在快速排序的過程中，通過一趟劃分，可以把一個(gè)待排序區(qū)間分為兩個(gè)子區(qū)間，然后分別對這兩個(gè)子區(qū)間施行同樣的劃分。棧的作用是在處理一個(gè)子區(qū)間時(shí)，上界和下界，待該區(qū)間處理完成后再從棧中取出另一子區(qū)間的邊界，對其進(jìn)行處理。這個(gè)功能利用隊(duì)列也可以實(shí)現(xiàn)，的順序有所變動而已。

9-9試設(shè)計(jì)一個(gè)算法,使得在O(n)的時(shí)間內(nèi)重排數(shù)組的排序碼排在所有取正值(非負(fù)值)的排序碼之前。

197

個(gè)對象的序列所用遞?為什么保存另一個(gè)子區(qū)間的只不過是處理子區(qū)間,將所有取負(fù)值

取試編寫該?1尋常要利用一個(gè)棧記憶待排

templatevoidreArrange(dataListwhile(i!=j){

while(L[i].getKey()=0)j--;swap(L[i],L[j]);i++;j--;}}

9-10奇偶交換排序是另一種交換排序。它的第一趟對序列中的所有奇數(shù)項(xiàng)i掃描，其次趟對序列中的所有偶數(shù)項(xiàng)i掃描。若A[i]>A[i+1]，則交換它們。第三趟有對所有的奇數(shù)項(xiàng)，第四趟對所有的偶數(shù)項(xiàng)，?，如此反復(fù)，直到整個(gè)序列全部排好序?yàn)橹埂?1)這種排序方法終止的條件是什么？(2)寫稀奇偶交換排序的算法。

(3)當(dāng)待排序排序碼序列的初始排列是從小到大有序，或從大到小有序時(shí)，在奇偶交換排序過程中的排序碼比較次數(shù)是多少？

(1)設(shè)有一個(gè)布爾變量exchange，判斷在每一次做過一趟奇數(shù)項(xiàng)掃描和一趟偶數(shù)項(xiàng)掃描后是否有過交換。若exchange=1，表示方才有過交換，還需繼續(xù)做下一趟奇數(shù)項(xiàng)掃描和一趟偶數(shù)項(xiàng)掃描；若exchange=0，表示方才沒有交換，可以終止排序。(2)奇偶排序的算法

templatevoiddataList::odd-evenSort(){inti,exchange;do{

exchange=0;

for(i=1;iVector[i+1]){//相鄰兩項(xiàng)比較,發(fā)生逆序

exchange=1;//作交換標(biāo)記swap(Vector[i],Vector[i+1]);//交換}

for(i=0;iVector[i+1]){//相鄰兩項(xiàng)比較,發(fā)生逆序

198

exchange=1;//作交換標(biāo)記swap(Vector[i],Vector[i+1]);//交換}

}while(exchange!=0);}

(3)設(shè)待排序?qū)ο笮蛄兄锌偣灿衝個(gè)對象。序列中各個(gè)對象的序號從0開始。則當(dāng)所有待排序?qū)ο笮蛄兄械膶ο蟀磁判虼a從大到小初始排列時(shí)，執(zhí)行m=?(n+1)/2?趟奇偶排序。當(dāng)所有待排序?qū)ο笮蛄兄械膶ο蟀磁判虼a從小到大初始排列時(shí)，執(zhí)行1趟奇偶排序。在一趟奇偶排序過程中，對所有奇數(shù)項(xiàng)掃描一遍，排序碼比較?(n-1)/2?次；對所有偶數(shù)項(xiàng)掃描一遍，排序碼比較每趟奇偶排序兩遍掃描的結(jié)果，排序碼總比較次數(shù)為?n/2?=n-1。

9-11請編寫一個(gè)算法，在基于單鏈表表示的待排序排序碼序列上進(jìn)行簡單項(xiàng)選擇擇排序。

采用靜態(tài)單鏈表作為存儲表示。用Vector[0]作為表頭結(jié)點(diǎn)，各待排序數(shù)據(jù)對象從Vector[1]開始存放。算法的思想是每趟在原始鏈表中摘下排序碼最大的結(jié)點(diǎn)(幾個(gè)排序碼相等時(shí)為最前面的結(jié)點(diǎn)入到結(jié)果鏈表的最前端。由于在原始鏈表中摘下的排序碼越來越小，在結(jié)果鏈表前端插入的排序碼也越來越小，最終形成的結(jié)果鏈表中的結(jié)點(diǎn)將按排序碼非遞減的順序有序鏈接。

靜態(tài)鏈表類定義

templateclassstaticlinkList;//靜態(tài)視聲明

templateclassElement{//靜態(tài)的定義

friendclassstaticlinkList;private:

Typekey;//排序碼，其它信息略intlink;//結(jié)點(diǎn)的鏈接指針public:

TypegetKey(){returnkey;}//取當(dāng)序碼

voidsetKey(Typex){key=x;}//將當(dāng)前結(jié)點(diǎn)的排序碼修改為x

intgetLink(){returnlink;}//取當(dāng)前結(jié)點(diǎn)的鏈接指針

199

n/2?次。所以?(n-1)/2?)，把它插鏈表類的鏈表元素前結(jié)點(diǎn)的+?前類排voidsetLink(intptr){link=ptr;}//將當(dāng)前結(jié)點(diǎn)的鏈接指針置為ptr

}

templateclassstaticlinkList{//靜態(tài)鏈表的類定義

private:

Element*Vector;//存儲待排序元素的向量

intMaxSize,CurrentSize;//向量中最大元素個(gè)數(shù)和當(dāng)前元素個(gè)數(shù)

public:

dstaticlinkList(intMaxsz=DefaultSize):MaxSize(Maxsz),CurrentSize(0)

{Vector=newElement[Maxsz];}voidSort();}

TemplatevoidstaticlinkList::selectSort(){inth=Vector[0].link,p,q,r,s;Vector[0].link=0;

while(h!=0){//原始鏈表未掃描完p=s=h;q=r=0;

while(p!=0){//掃描原始鏈表,尋覓排序碼最大的結(jié)點(diǎn)s

if(Vector[p].data>Vector[s].data)//記憶當(dāng)前找到的排序碼最大結(jié)點(diǎn)

{s=p;r=q;}q=p;p=Vector[p].link;}

if(s==h)h=Vector[h];//排序碼最大的結(jié)點(diǎn)是原始鏈表前端結(jié)點(diǎn),摘下

elseVector[r].link=Vector[s].link;//排序碼最大的結(jié)點(diǎn)是原始鏈表表中結(jié)點(diǎn),摘下

Vector[s].link=Vector[0].link;//結(jié)點(diǎn)s插入到結(jié)果鏈表的前端

Vector[0].link=s;

}}

9-12若參與錦標(biāo)賽排序的排序碼有11個(gè)，為了完成排序，至少需要

200

多少次排序碼比較？

對于有n(n>0)個(gè)數(shù)據(jù)的序列，錦標(biāo)賽排序選最小數(shù)據(jù)需進(jìn)行n-1次數(shù)據(jù)比較，以后每選一個(gè)數(shù)據(jù)，進(jìn)行數(shù)據(jù)比較的次數(shù)，均需?log2n?-1次（在外結(jié)點(diǎn)層無比較）。對于有11個(gè)排序碼的序列，第一次選具最小排序碼的數(shù)據(jù)，需進(jìn)行10次排序碼比較，以后在剩下的序列中每選一個(gè)具最小排序碼的數(shù)據(jù)，都需進(jìn)行?log211?-1=2次排序碼比較，因此，為了完成排序，需要10+2*10=30次排序碼比較。

9-13試給出適用于錦標(biāo)賽排序的勝者樹的類型聲明。并寫一個(gè)函數(shù)，對n個(gè)參與排序的對象，構(gòu)造勝者樹。設(shè)n是2的冪。

適用于錦標(biāo)賽排序的勝者樹的類型聲明.

templateclassDataNode{//勝者樹結(jié)點(diǎn)的類定義public:

Typedata;//數(shù)據(jù)值

intindex;//樹中的結(jié)點(diǎn)號,即在完全二叉樹順序存儲中的下標(biāo)

intactive;//是否參選的標(biāo)志，=1,參選=0,不再參選}

templatevoidTournamentSort(Typea[],intn){//建立樹的順序存儲數(shù)組tree,將數(shù)組a[]中的元素復(fù)制到勝者樹中,對它們進(jìn)行排序,并把結(jié)

//果返送回?cái)?shù)組中,n是待排序元素個(gè)數(shù)。

DataNode*tree;//勝者樹結(jié)點(diǎn)數(shù)組DataNodeitem;

intbottomRowSize=PowerOfTwo(n);

//計(jì)算滿足>=n的2的最小次冪的數(shù):樹的底行大小n=7時(shí)它為8

intTreeSize=2*bottomRowSize-1;//計(jì)算勝者樹的小:內(nèi)結(jié)點(diǎn)+外結(jié)點(diǎn)數(shù)

intloadindex=bottomRowSize-1;//外結(jié)點(diǎn)開始位置tree=newDataNode[TreeSize];//動態(tài)分派勝者結(jié)點(diǎn)數(shù)組空間

intj=0;//在數(shù)組a中取數(shù)據(jù)指針

for(inti=loadindex;ivoidUpdateTree(DataNode*tree,inti){

//錦標(biāo)賽排序中的調(diào)整算法：i是表中當(dāng)前最小元素的下標(biāo),即勝者。從它開始向上調(diào)整。

if(i%2==0)tree[(i-1)/2]=tree[i-1];//i為偶數(shù),對手為左結(jié)點(diǎn)

elsetree[(i-1)/2]=tree[i+1];//i為奇數(shù),對手為右結(jié)點(diǎn)

//最小元素輸出之后,它的對手上升到父結(jié)點(diǎn)位置

i=(i-1)/2;//i上升到雙親結(jié)點(diǎn)位置while(i){

if(i%2==0)j=i-1;//確定i的對手是左結(jié)點(diǎn)還是右結(jié)點(diǎn)

elsej=i+1;

202

if(!tree[i].active||!tree[j].active)//比賽對手中間有一個(gè)為空

if(tree[i].active)tree[(i-1)/2]=tree[i];

elsetree[(i-1)/2]=tree[j];//非空者上升到雙親結(jié)點(diǎn)else//比賽對手都不為空if(tree[i].dataj=[JaRoGuRoKiEvAnJiKa10nnymmanmy[RRoGuKaKiEvAnJiJanonmyymanmj=[DRoGuKaKiEvAnJiJan9otmyymanm[RKiGuKaDoEvAnJiJanommyytanm]j=[JaKiGuKaDoEvAnJiRo8nmyytanmm][Ki

KaGuJimDoEvAnJanRomyytan]mj=[JaKaGuJimDoEvAnKiRo7nyytanm]m[KJimGuJanDoEvAnKiRoayytan]mmj=[AJimGuJanDoEvKaKiRo6nnytay]mm[JiJanGuAnDoEvKaKiRomynta]ymmj=[EJanGuAnDoJiKaKiRo5vayntm]ymm[JaEvaGuAnDoJiKaKiRonynt]mymmj=[DEvaGuAnJanJiKaKiRo4otyn]mymm[GEvaDoAnJanJiKaKiRouytn]mymmj=[AEvaDoGuJanJiKaKiRo3nnty]mymm[E

AnDoGuJanJiKaKiRovant]ymymmj=[DAnEvGuJanJiKaKiRo2otna]ymymm[D

AnEvGuJanJiKaKiRootn]aymymmj=[D

An

EvGuJanJiKaKiRo204

10

DotTi交m]換DotTi調(diào)]m整RoTi交n]m換RoTi調(diào)nm整RoTi交nm換RoTi調(diào)nm整RoTi交nm換RoTi調(diào)nm整RoTi交nm換RoTi調(diào)nm整RoTi交nm換RoTi調(diào)nm整RoTi交nm換RoTi調(diào)nm整RoTi交nm換RoTi調(diào)nm整RoTi交nm換RoTi調(diào)nm整RoTi

交

1

otn]a[AnDoEvn]tay

GuymyJanJiKa

mymKimmRomnRonmTim

換調(diào)整

(2)按數(shù)值遞增順序排序

205

形成初始堆(按最大堆)0123263329

35

i=2633[32925i=0i=1

22]

26[3329

35191222

]

[33329526191222

]

4191951212

622

堆排序0123456j=[223329交換626191235

]

[33292235調(diào)整

261912為堆

]

j=[12292235交換5261933

]

[29221235調(diào)整

261933為堆

]

j=[19221235交換4262933

][262235調(diào)整

1912]2933為堆

j=[122235交換31926]2933[22122635調(diào)整

192933為堆]

j=[19122635交換2222933

]

[192635調(diào)整

206

j=1

12][12

19][1219]2229262229262229

33為堆

35交換3335調(diào)整33為堆

(3)同樣7個(gè)數(shù)字，換一個(gè)初始排列，再按數(shù)值的遞增順序排序形成初始堆(按最大堆)012345612192622

332935

i=1219[32625293322

]

i=12[2926035193322

]

i=[329261533191222

]

堆排序0123456j=[222926交換633191235

]

[33292635調(diào)整

221912為堆

]

j=[12292635交換5221933

]

[29261235調(diào)整

221933為堆

]

j=[19261235交換4222933

][261935調(diào)整

2212]2933為堆

j=[121935交換32226]2933

207

j=2j=1

[2219

12]

[121922]

[19

12]22[12

19]22[1219]22

2635調(diào)整

2933為堆2635交換293326

2926

2926

29

35調(diào)整33為堆35交換3335調(diào)整33為堆

9-15假使只想在一個(gè)有n個(gè)元素的任意序列中得到其中最小的第k(k0)個(gè)數(shù)據(jù)的序列，選最小數(shù)據(jù)需進(jìn)行n-1次數(shù)據(jù)比較，以后每選一個(gè)數(shù)據(jù)，進(jìn)行數(shù)據(jù)比較的次數(shù)，均需?log2n?-1次。例如，同樣12個(gè)數(shù)據(jù)，第一次選最小的數(shù)據(jù)6，需進(jìn)行11次數(shù)據(jù)比較，以后選7、9、11時(shí)，都是?log212?-1=2次數(shù)據(jù)比較。

208

列施行排序

將兩個(gè)子序列LeftList和RightList合并為一個(gè)序列List;}}

典型的例子就是快速排序和歸并排序。若設(shè)T(n)是對n個(gè)對象的序列進(jìn)行排序所需的時(shí)間，而且把序列劃分為長度相等的兩個(gè)子序列后，對每個(gè)子序列進(jìn)行排序所需的時(shí)間為T(n/2)，最終合并兩個(gè)已排好序的子序列所需時(shí)間為cn（c是一個(gè)常數(shù)）。此時(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)???

≤cnlog2n+nT(1)=O(nlog2n)

9-23假使某個(gè)文件經(jīng)內(nèi)排序得到80個(gè)初始?xì)w并段，試問(1)若使用多路歸并執(zhí)行3趟完成排序，那么應(yīng)取的歸并路數(shù)至少應(yīng)為多少？

(2)假使操作系統(tǒng)要求一個(gè)程序同時(shí)可用的輸入/輸出文件的總數(shù)不超過15個(gè)，則按多路歸并至少需要幾趟可以完成排序？假使限定這個(gè)趟數(shù)，可取的最低路數(shù)是多少？

(1)設(shè)歸并路數(shù)為k，初始?xì)w并段個(gè)數(shù)m=80，根據(jù)歸并趟數(shù)計(jì)算公式S=?logkm?=?logk80?=3得：k3≥80。由此解得k≥3，即應(yīng)取的歸并路數(shù)至少為5。

(2)設(shè)多路歸并的歸并路數(shù)為k，需要k個(gè)輸入緩沖區(qū)和1個(gè)輸出緩沖區(qū)。1個(gè)緩沖區(qū)對應(yīng)1個(gè)文件，有k+1=15，因此k=14，可做14路歸并。由S=?logkm?=?log1480?=2。即至少需2趟歸并可完成排序。

若限定這個(gè)趟數(shù)，由S=?logk80?=2，有80≤k2，可取的最低路數(shù)為9。即要在2趟內(nèi)完成排序，進(jìn)行9路排序即可。

9-24假設(shè)文件有4500個(gè)記錄，在磁盤上每個(gè)頁塊可放75個(gè)記錄。計(jì)算機(jī)中用于排序的內(nèi)存區(qū)可容納450個(gè)記錄。試問：

(1)可建立多少個(gè)初始?xì)w并段？每個(gè)初始?xì)w并段有多少記錄？存放于多少個(gè)頁塊中？

(2)應(yīng)采用幾路歸并？請寫出歸并過程及每趟需要讀寫磁盤的頁塊數(shù)。

214

(1)文件有4500個(gè)記錄，計(jì)算機(jī)中用于排序的內(nèi)存區(qū)可容納450個(gè)記錄，可建立的初始?xì)w并段有4500∕450=10個(gè)。每個(gè)初始?xì)w并段中有450個(gè)記錄，存于450∕75=6個(gè)頁塊中。(2)內(nèi)存區(qū)可容納6個(gè)頁塊，可建立6個(gè)緩沖區(qū)，其中5個(gè)緩沖區(qū)用于輸入，1個(gè)緩沖區(qū)用于輸出，因此，可采用5路歸并。歸并過程如下：

45045045045045045045045045045022502250

4500

共做了2趟歸并，每趟需要讀60個(gè)磁盤頁塊，寫出60個(gè)磁盤頁塊。

9-25設(shè)初始?xì)w并段為(10,15,31,?),(9,20,?),(22,34,37,?),(6,15,42,?),(12,37,?),(84,95,?),試?yán)脭≌邩溥M(jìn)行k路歸并，手工執(zhí)行選擇最小的5個(gè)排序碼的過程。

做6路歸并排序，選擇最小的5個(gè)排序碼的敗者樹如下圖所示。4輸出6(4號段)1輸出9(1號段)0輸出10(0號段)

15554400110010136109102036109363456334545668422612842215122215128415遞補(bǔ)20遞補(bǔ)

15遞補(bǔ)

5輸出12(5號段)4輸出15(4號段)

00

4511

010136152036152033456456

215

221512842215378437遞補(bǔ)42遞補(bǔ)

9-26設(shè)輸入文件包含以下記錄：14,22,7,24,15,16,11,100,10,9,20,12,90,17,13,19,26,38,30,25,50,28,110,21,40?，F(xiàn)采用置換-選擇方法生成初始?xì)w并段，并假設(shè)內(nèi)存工作區(qū)可同時(shí)容納5個(gè)記錄，請畫出選擇的過程。

設(shè)內(nèi)存工作區(qū)在某一時(shí)刻可以處理6個(gè)記錄，利用敗者樹生成初始?xì)w并段的過程如下。輸入文件InFile內(nèi)存工輸出文件OutFile動作作區(qū)14,22,07,24,15,16,11,輸入6個(gè)記100,10,09,20,12,90,錄17,13,19,26,38,30,25,50,28,110,21,4011,100,10,09,20,12,14,22,選擇07,輸90,17,13,19,26,38,07,出07,30,25,50,28,110,21,24,15,門檻07,置4016換11100,10,09,20,12,90,14,22,07選擇11,輸17,13,19,26,38,30,11,出11,25,50,28,110,21,4024,15,門檻11,置16換10010,09,20,12,90,17,14,22,07,100選擇14,輸13,19,26,38,30,25,100,出14,50,28,110,21,4024,15,門檻14,置16換1009,20,12,90,17,13,10,22,07,100,14選擇15,輸19,26,38,30,25,50,100,出15,28,110,21,4024,15,門檻15,置16換0920,12,90,17,13,19,10,22,07,100,14,15選擇16,輸26,38,30,25,50,28,100,4出16,110,21,4024,09,門檻16,置16換2012,90,17,13,19,26,10,22,07,100,14,15,16選擇20,輸38,30,25,50,28,110,100,出20,

216

21,4024,09,門檻20,置20換1290,17,13,19,26,38,10,22,07,100,14,15,選擇22,輸30,25,50,28,110,21,100,16,20出22,4024,09,門檻22,置12換9017,13,19,26,38,30,10,90,07,100,14,15,選擇24,輸25,50,28,110,21,40100,16,20,22出24,24,09,門檻24,置12換1713,19,26,38,30,25,10,90,07,100,14,15,選擇90,輸50,28,110,21,4016,20,22,100,出90,17,09,24門檻90,置12換1319,26,38,30,25,50,10,13,07,100,14,15,選擇100,28,110,21,4016,20,22,100,輸出100,17,09,24,90門檻100,12置換1926,38,30,25,50,28,10,13,07,100,14,15,無大于門檻110,21,4019,16,20,22,的的記17,09,24,90,100,∞錄,輸出段12終止符26,38,30,25,50,28,10,13,選擇09,輸110,21,4019,出09,17,09,門檻09,置12換2638,30,25,50,28,110,10,13,09選擇10,輸21,4019,出10,17,26,門檻10,置12換3830,25,50,28,110,21,38,13,09,10選擇12,輸4019,出12,17,26,門檻12,置12換3025,50,28,110,21,4038,13,09,10,12選擇13,輸19,出13,17,26,門檻13,置30換25

217

50,28,110,21,4038,25,09,10,12,1319,17,26,3038,25,09,10,12,13,1719,50,26,3038,25,09,10,12,13,17,1928,50,26,3038,110,09,10,12,13,17,28,19,2550,26,3038,110,09,10,12,13,17,19,25,2628,50,21,3038,110,09,10,12,13,17,40,19,25,26,50,21,283038,110,09,10,12,13,17,19,25,26,40,50,21,28,30∞―,110,09,10,12,13,17,19,25,26,40,28,30,3850,21,――,09,10,12,13,17,110,―,19,25,26,28,30,38,4050,21,――,09,10,12,13,17,110,―,19,25,26,218

28,110,21,40110,21,4021,4040選擇17,輸出17,門檻17,置換50選擇19,輸出19,門檻19,置換28選擇25,輸出25,門檻25,置換110選擇26,輸出26,門檻26,置換21選擇28,輸出28,門檻28,置換40選擇30,輸出30,門檻30,無輸入選擇38,輸出38,門檻38,無輸入選擇40,輸出40,門檻40,無輸入選擇50,輸出50,門檻50,無輸入選擇110,輸出110,

―,21,――,―,―,―,21,――,―,―,―,21,――,―,―,―,―,―28,30,38,40,50門檻110,無輸入09,10,12,13,17,無大于門檻19,25,26,的的記28,30,38,40,50,錄,輸出段110,∞終止符選擇21,輸出21,門檻21,無輸入21,∞無大于門檻的的記錄,輸出段終止符9-27給出12個(gè)初始?xì)w并段，其長度分別為30,44,8,6,3,20,60,18,9,62,68,85。現(xiàn)要做4路外歸并排序，試畫出表示歸并過程的最正確歸并樹，并計(jì)算該歸并樹的帶權(quán)路徑長度WPL。

設(shè)初始?xì)w并段個(gè)數(shù)n=12，外歸并路數(shù)k=4，計(jì)算(n-1)%(k-1)=11%3=2≠0，必需補(bǔ)k-2-1=1個(gè)長度為0的空歸并段，才能構(gòu)造k路歸并樹。此時(shí)，歸并樹的內(nèi)結(jié)點(diǎn)應(yīng)有(n-1+1)/(k-1)=12/3=4個(gè)。036891820304460626885036891718203044606268850368917182030446062646885196413

WPL=(3+6+8)*3+(9+18+20+30+44+60+62)*2+(68+85)*1=51+486+153=690

219

三、其他練習(xí)題

9-28填空題

(1)每次從無序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做_______排序；每次從無序表中挑揀出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做________排序。

(2)每次直接或通過基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列時(shí)就交換它們的位置，此種排序方法叫做________排序；每次使兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法叫做________排序。

(3)在直接選擇排序中，記錄比較次數(shù)的時(shí)間繁雜度為________，記錄移動次數(shù)的時(shí)間繁雜度為________。

(4)在堆排序的過程中，對n個(gè)記錄建立初始堆需要進(jìn)行________次調(diào)整運(yùn)算，由初始堆到堆排序終止，需要對樹根結(jié)點(diǎn)進(jìn)行________次調(diào)整運(yùn)算。

(5)在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時(shí)間繁雜度為________，整個(gè)堆排序過程的時(shí)間繁雜度為________。

(6)假定一組記錄的排序碼為(46,79,56,38,40,84)，則利用堆排序方法建立的初始堆為________。

(7)快速排序在平均狀況下的時(shí)間繁雜度為________，在最壞狀況下的時(shí)間繁雜度為________。

(8)快速排序在平均狀況下的空間繁雜度為________，在最壞狀況下的空間繁雜度為________。

(9)在快速排序方法中，進(jìn)行每次劃分時(shí)，是從當(dāng)前待排序區(qū)間的________向________依次查找出處于逆序的元素并交換之，最終將基準(zhǔn)元素交換到一個(gè)確定位置，從而以該位置把當(dāng)前區(qū)間劃分為前后兩個(gè)子區(qū)間。

(10)假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進(jìn)行快速排序的一次劃分的結(jié)果為________。

(11)在二路歸并排序中，對n個(gè)記錄進(jìn)行歸并的趟數(shù)為________。(12)在歸并排序中，進(jìn)行每趟歸并的時(shí)間繁雜度為________，整個(gè)排序過程的時(shí)間繁雜度為________，空間繁雜度為________。

(13)對20個(gè)記錄進(jìn)行歸并排序時(shí)，共需要進(jìn)行________趟歸并，在第三趟歸并時(shí)是把長度為________的有序表兩兩歸并為長度為________的有序表。

(14)假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進(jìn)行歸并

220

排序的過程中，其次趟歸并后的結(jié)果為________。

(1)插入,選擇(2)交換,二路歸并(3)O(n2),O(n)(4)?n/2?,n-1

(6)O(log2n),O(nlog2n)(6)(84,79,56,38,40,46)(7)O(nlog2n),O(n2)(8)O(log2n),O(n)(9)兩端,中間(10)[3840]46[567984](11)4,4(12)O(n),O(nlog2n),O(n)(13)5,4,

9-29當(dāng)所有待排序記錄的排序碼都相等，計(jì)算以下排序方法的運(yùn)行時(shí)間：

(1)直接插入排序；(3)起泡排序；

(1)n-1(3)n-1

9-30填空題

(1)對n個(gè)不同的排序碼進(jìn)行起泡排序，在（序碼比較次數(shù)最??；在（(2)快速排序在（（④）狀況下最易發(fā)揮其優(yōu)點(diǎn)。(3)將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，最少需要（較，最多需要（(4)堆的形狀是一棵（(1)就平均時(shí)間而言，

①排序?qū)ο笠呀?jīng)按其排序碼從小到大排好②排序?qū)ο笠呀?jīng)按其排序碼從大到小排好，現(xiàn)要求全部逆轉(zhuǎn)③排序?qū)ο笠呀?jīng)按其排序碼從小到大排好④每次劃分對象定位后，左側(cè)子序列與右側(cè)子序列長度一致的⑤5⑥25

⑦完全二叉⑧快速

9-31試構(gòu)造排序算法的思想可以用如下的有向圖來描述：

8(2)2?n/2(4)n(n-1)/2②③⑥）次數(shù)據(jù)比較。⑦（⑧5個(gè)整數(shù)最多用(14)[38465679][4084](2)堆排序；(4)直接選擇排序。為奇數(shù)),2?n/2?-1(n為偶數(shù))①）狀況下排）狀況下排序碼比較次數(shù)最大。）狀況下最不利于發(fā)揮其優(yōu)點(diǎn)，在

⑤）次數(shù)據(jù)比

）樹。）排序最好。

7次比較的算法。

221?(n

③ac④頂點(diǎn)abcde

⑦e①②入度43210

⑤bd⑥

在圖中有5個(gè)頂點(diǎn)，代表5個(gè)可比較的整數(shù)a,b,c,d,e。有向邊的箭頭從較大的整數(shù)指向較小的整數(shù)，虛線表示的有向邊表示不用比較，而是通過傳遞性得到的。圖中各有向邊的編號給出7次比較的先后次序。

首先比較a與b和c與d，得avoiddataList::merge(constintleft,constintmid,constintright){inti,j;Typetemp;

for(i=left;iA[mid+1]){temp=A[mid];

for(j=mid-1;j>=i;j--)A[j+1]=A[j];A[i]=A[mid+1];

for(j=mid+2;jA[j])A[j-1]=A[j];elsebreak;A[j-1]=temp;}}}

(1)若A={12,28,35,42,