數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--二路歸并排序說(shuō)明書(shū)

1、<p><b>　　前 言</b></p><p><b>　　1.1排序的重要性</b></p><p>　　生活中，無(wú)時(shí)不刻不充滿(mǎn)這排序，比如：班級(jí)同學(xué)的成績(jī)排名問(wèn)題，公司產(chǎn)值高低的問(wèn)題等等，解決這些問(wèn)題的過(guò)程中，都涉及到了一個(gè)數(shù)據(jù)結(jié)構(gòu)的構(gòu)造思想過(guò)程。數(shù)據(jù)結(jié)構(gòu)中的排序，也有很多種，如：插入排序、交換排序、選擇排序等等，此時(shí)我們就要注

2、意選擇具有優(yōu)解的算法，將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)有序的排列，便于我們查找。</p><p>　　假設(shè)含有n個(gè)記錄的序列為{R1,R2,Rn},其相應(yīng)的關(guān)鍵字序列為{K1,K2,…,Kn}需確定1，2…n的一種排序P1,P2…Pn,使其相應(yīng)的關(guān)鍵字滿(mǎn)足如下的非遞減的關(guān)系：Kp1≤Kp2≤…≤Kpn,即按關(guān)鍵字{Rp1,Rp2,…,Rpn}有序的排列，這樣的一種操作稱(chēng)為排序。一般情況下，排序又

3、分為內(nèi)部排序和外部排序。而在內(nèi)部排序中又含有很多排序方法，就其全面性能而言，很難提出一種被認(rèn)為是最好的方法，因?yàn)槊恳环N方法都有它的優(yōu)缺點(diǎn)，適合在不同的環(huán)境下使用。我們學(xué)習(xí)的排序有:直接插入排序、折半插入排序、希爾排序、快速排序、基數(shù)排序、歸并排序等。本次課題研究中，我主要進(jìn)行了二路歸并排序的研究和學(xué)習(xí)。</p><p>　　1.2設(shè)計(jì)的背景和意義</p><p>　　排序是計(jì)算機(jī)領(lǐng)域的一類(lèi)

4、非常重要的問(wèn)題，計(jì)算機(jī)在出來(lái)數(shù)據(jù)的過(guò)程中，有25%的時(shí)間花在了排序上，有許多的計(jì)算機(jī)設(shè)備，排序用去計(jì)算機(jī)處理數(shù)據(jù)時(shí)間的一半以上，這對(duì)于提高計(jì)算機(jī)的運(yùn)行速度有一定的影響。此時(shí)排序算法的高效率顯得尤為重要。</p><p>　　在排序算法匯中，歸并排序（Merging sort）是與插入排序、交換排序、選擇排序不同的另一類(lèi)排序方法。歸并的含義是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。歸并排序可分為多路歸并排序，

5、兩路歸并排序，既可用于內(nèi)排序，也可以用于外排序。這里僅對(duì)內(nèi)排序的兩路歸并排序進(jìn)行討論。</p><p>　　而我們這里所探究學(xué)習(xí)的二路歸并排序，設(shè)計(jì)思路更加清晰、明了，程序本身也不像堆結(jié)構(gòu)那樣復(fù)雜，同時(shí)時(shí)間復(fù)雜度僅為0(N)，同時(shí)在處理大規(guī)模歸并排序的時(shí)候，排序速度也明顯優(yōu)于冒泡法等一些排序算法，提高排序算法的效率。</p><p><b>　　正 文</b><

6、/p><p><b>　　2.1設(shè)計(jì)內(nèi)容</b></p><p>　　設(shè)計(jì)一個(gè)利用二路歸并算法實(shí)現(xiàn)的排序算法，針對(duì)輸入的一組無(wú)序的數(shù)，利用?；蛘邤?shù)組機(jī)芯存儲(chǔ)，然后進(jìn)行數(shù)據(jù)的兩兩分組、比較，構(gòu)造新的棧或者數(shù)組，依次類(lèi)推，直到得到一個(gè)有序數(shù)組或者棧，最后輸出有序數(shù)據(jù)，得到有序數(shù)據(jù)。</p><p><b>　　2.2設(shè)計(jì)要求</b>

7、;</p><p>　　假設(shè)初始序列含有n 個(gè)數(shù)據(jù)（n是已經(jīng)確定的數(shù)據(jù)個(gè)數(shù)），首先把n 個(gè)記錄看成n個(gè)長(zhǎng)度為1的有序序列，進(jìn)行兩兩歸并，得到[n/2]個(gè)長(zhǎng)度為2的有序序列，再兩兩歸并直到所有記錄歸并成一個(gè)長(zhǎng)度為n的有序序列為止。</p><p><b>　　2.3設(shè)計(jì)思想</b></p><p>　　對(duì)于任意一組數(shù)據(jù)，先利用?；蛘邤?shù)組將數(shù)據(jù)存儲(chǔ)

8、起來(lái)，其中，我們會(huì)用到線(xiàn)性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)方法。然后對(duì)存儲(chǔ)的數(shù)據(jù)進(jìn)行查找和篩選、排序，在出棧的過(guò)程中，同時(shí)對(duì)所取數(shù)據(jù)進(jìn)行分組、排列，再次構(gòu)造新的存儲(chǔ)?；蛘邤?shù)組，依次類(lèi)推，直到得到一個(gè)有序的數(shù)據(jù)時(shí)，執(zhí)行出棧命令，輸出最后的排序結(jié)果。 </p><p>　　為了更清晰地說(shuō)清楚這里的思想，大家來(lái)看圖1，我們將本是無(wú)序的數(shù)組序列{16,7,13,10,9,15,3,2,5,8,12,1,11,4,6,14}

9、，通過(guò)兩兩合并排序后，再合并，最終獲得了一個(gè)有序的數(shù)組。仔細(xì)觀察它的形狀，很像一棵倒置的完全二叉樹(shù)，利用兩兩的比較，一次進(jìn)行遞歸排序，最終得到一個(gè)從小到大的有序序列。</p><p><b>　　圖 1</b></p><p><b>　　2.4 主要模塊</b></p><p>　　主要模塊式有四個(gè)階段，依次是：輸入一組

10、無(wú)序的數(shù)列，用數(shù)據(jù)結(jié)構(gòu)或者鏈?zhǔn)浇Y(jié)構(gòu)進(jìn)行存儲(chǔ)，然后進(jìn)行查找、分組，進(jìn)行最后的歸并排序。（如圖2所示）</p><p><b>　　圖 2</b></p><p><b>　　2.5排序設(shè)計(jì)內(nèi)容</b></p><p>　　此次操作要用到順序結(jié)構(gòu)的存儲(chǔ)，順序表的查找，以及二路歸并排序。</p><p>

11、　　2.5.1 順序表的存儲(chǔ)</p><p>　　首先利用順序存儲(chǔ)結(jié)構(gòu)，把所有學(xué)生的成績(jī)按每個(gè)班，每個(gè)學(xué)校，每個(gè)縣，每個(gè)市，用線(xiàn)性表的順序存儲(chǔ)機(jī)構(gòu)分別存儲(chǔ)起來(lái)。</p><p>　　順序表的基本操作如下：</p><p>　　Initlist(&L) 操作結(jié)果：構(gòu)造一個(gè)空的線(xiàn)性表L;</p>

12、<p>　　Destroylist(&L) 操作結(jié)果：銷(xiāo)毀線(xiàn)性表L;</p><p>　　Clearlist((&lL) 操作結(jié)果：將L重置為空表（線(xiàn)性表L已經(jīng)存在）；</p><p>　　Iiselength(L) 操作結(jié)果:

13、返回L中數(shù)據(jù)元素的個(gè)數(shù)；</p><p>　　GetElem(L,I,&e) 操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值；2.5.2 順序表的查找</p><p>　　Int Search-Sep(SSTable ST , KeyType key)</p><p>　　{//在順序表ST中順序查找其關(guān)鍵字等于Ke

14、y的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0</p><p>　　ST.elem[0].Key=key; 哨兵；</p><p>　　For(i=ST.length; !EQ(ST.elem[i].key.key)) 從后往前找；</p><p>　　Return I;

15、 找不到是i為0；</p><p><b>　　}</b></p><p>　　//Search-Sep</p><p>　　2.5.3 歸并排序</p><p><b>　　代碼：</b></p><p>　　/* 對(duì)順序表L作歸并

16、排序 */</p><p>　　void MergeSort(SqList *L){ </p><p>　　MSort(L->r,L->r,1,L->length);</p><p><b>　　}</b></p><p><b>　　2.6算法設(shè)計(jì)&

17、lt;/b></p><p>　　本次設(shè)計(jì)主要用用到下面的算法：</p><p>　　2.6.1歸并排序算法的實(shí)現(xiàn)      </p><p>　　遞歸算法就是對(duì)n個(gè)數(shù)據(jù)進(jìn)行兩兩歸并，得到[n/2]個(gè)長(zhǎng)度為2的有序序列，再兩兩歸并直到所有記錄歸并成一個(gè)長(zhǎng)度為n的有序序列為止。</p><p&

18、gt;　　遞歸算法實(shí)現(xiàn)中，最重要的就是對(duì)[n/2]進(jìn)行很多次的歸并遞歸排序算法的設(shè)計(jì)，調(diào)用函數(shù)MSort中采用了遞歸的算法思想，用較簡(jiǎn)短的語(yǔ)句，實(shí)現(xiàn)了多次遞歸排序。假設(shè)現(xiàn)在要對(duì)數(shù)組{50,10,90,30,70,40,80,60,20}進(jìn)行排序，L.length=9，一下就是MSort主要代碼及實(shí)現(xiàn)過(guò)程。</p><p>　　/* 將SR[s..t]歸并排序?yàn)門(mén)R1[s..t] */</

19、p><p>　　1 void MSort(int SR[],int TR1[],int s, int t)</p><p><b>　　2 {</b></p><p><b>　　int m;</b></p><p&g

20、t;　　int TR2[MAXSIZE+1];</p><p><b>　　if(s==t)</b></p><p>　　TR1[s]=SR[s];</p><p><b>　　Else</b></p><p><b>　　{</b></p><p

21、>　　m=(s+t)/2;   /* 將SR[s..t]平分為SR[s..m]和SR[m+1..t] */</p><p>　　MSort(SR,TR2,s,m); /* 遞歸地將SR[s..m]歸并為有序的TR2[s..m] */</p><p>　　MSort(SR,TR2,m+1,t); 

22、/* 遞歸地將SR[m+1..t]歸并為有序TR2[m+1..t] */</p><p>　　Merge(TR2,TR1,s,m,t); /* 將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t] */</p><p><b>　　}</b></p><p><b>　

23、　}</b></p><p>　　MSort被調(diào)用時(shí)，SR與TR1都是{50,10,90,30,70,40,80,60,20}，s=1，t=9，最終我們的目的就是要將TR1中的數(shù)組排好順序。</p><p>　　第5行，顯然s不等于t，執(zhí)行第8～13行語(yǔ)句塊。</p><p>　　第9行，m=(1+9)/2=5。m就是序列的正中間下標(biāo)</p>

24、<p>　　此時(shí)第10行，調(diào)用“MSort(SR,TR2,1,5);”的目標(biāo)就是將數(shù)組SR中的第1～5的關(guān)鍵字歸并到有序的TR2（調(diào)用前TR2為空數(shù)組），第11行，調(diào)用“MSort(SR,TR2,6,9);”的目標(biāo)就是將數(shù)組SR中的第6～9的關(guān)鍵字歸并到有序的TR2。也就是說(shuō)，在調(diào)用這兩句代碼之前，代碼已經(jīng)準(zhǔn)備將數(shù)組分成兩組。如圖4所示：</p><p><b>　　圖4</b>

25、;</p><p>　　第12行，函數(shù)Merge的代碼細(xì)節(jié)一會(huì)再講，調(diào)用“Merge(TR2,TR1,1,5,9);”的目標(biāo)其實(shí)就是將第10和11行代碼獲得的數(shù)組TR2（注意它是下標(biāo)為1～5和6～9的關(guān)鍵字分別有序）歸并為T(mén)R1，此時(shí)相當(dāng)于整個(gè)排序就已經(jīng)完成了。如圖5所示：</p><p><b>　　圖5</b></p><p>　　第10行

26、遞歸調(diào)用進(jìn)去后，s=1，t=5，m=(1+5)/2=3。此時(shí)相當(dāng)于將5個(gè)記錄再為三個(gè)和兩個(gè)。繼續(xù)遞歸進(jìn)去，直到細(xì)分為一個(gè)記錄填入TR2，此時(shí)s與t相等，遞歸返回，如圖6的左圖。每次遞歸返回后都會(huì)執(zhí)行當(dāng)前遞歸函數(shù)的第12行，將TR2歸并到TR1中。如圖6的右圖。最終使得當(dāng)前序列有序。</p><p><b>　　圖6</b></p><p>　　同樣的第11行也是類(lèi)似方

27、式，如圖7。 </p><p><b>　　圖7</b></p><p>　　此時(shí)也就是剛才所講的最后一次執(zhí)行第12行代碼，將{10,30,50,70,90}與{20,40,60,80}歸并為最終有序的序列。以下是對(duì)此段遞歸算法程序的圖示：(如圖8)</p><p><b>　　圖8</b></p>

28、<p>　　2.6.2歸并排序算法的整合</p><p>　　在經(jīng)過(guò)每個(gè)新的排序片段以后，程序產(chǎn)生新的數(shù)組，如何讓新的數(shù)組依然按照一定順序進(jìn)行排序, 即將SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]，此時(shí)就要進(jìn)行Merge()函數(shù)的調(diào)用。一下就是Merge()函數(shù)實(shí)現(xiàn)的詳細(xì)過(guò)程：</p><p>　　/* 將有序的SR[i..m]和SR[m+1.

29、.n]歸并為有序的TR[i..n] */</p><p>　　1 void Merge(int SR[],int TR[],int i,int m,int n)</p><p><b>　　2 {</b></p><p>　　int j,k,l;

30、</p><p>　　4  for(j=m+1,k=i;i<=m && j<=n;k++) /* 將SR中記錄由小到大歸并入TR */</p><p><b>　　5  {</b></p><p>　　6  

31、 if (SR[i]<SR[j])</p><p>　　7    TR[k]=SR[i++];</p><p><b>　　else</b></p><p>　　9    TR[k]=SR[j++];</p><p>

32、;<b>　　10  }</b></p><p>　　11  if(i<=m)</p><p><b>　　12  {</b></p><p>　　13   for(l=0;l<=m-i;l++)14 

33、0;  TR[k+l]=SR[i+l];  /* 將剩余的SR[i..m]復(fù)制到TR */</p><p><b>　　15  }</b></p><p>　　16  if(j<=n)</p><p><b>　　{</b&

34、gt;</p><p>　　18   for(l=0;l<=n-j;l++)</p><p>　　19    TR[k+l]=SR[j+l];  /* 將剩余的SR[j..n]復(fù)制到TR */</p><p><b>　　20 &#

35、160;}</b></p><p><b>　　21 }</b></p><p>　　1) 假設(shè)我們此時(shí)調(diào)用的Merge就是將{10,30,50,70,90}與{20,40,60,80}歸并為最終有序的序列，因此數(shù)組SR為{10,30,50,70,90,20,40,60,80}，i=1，m=5，n=9。</p><p

36、>　　2) 第4行，for循環(huán)，j由m+1=6開(kāi)始到9，i由1開(kāi)始到5，k由1開(kāi)始每次加1，k值用于目標(biāo)數(shù)組TR的下標(biāo)。</p><p>　　3) 第6行，SR[i]=SR[1]=10，SR[j]= SR[6]=20，SR[i]<SR[j]，執(zhí)行第7行，TR[k]=TR[1]=10，并且i++。如圖9。</p><p><b>　　圖9</b

37、></p><p>　　4) 再次循環(huán)，k++得到k=2，SR[i]=SR[2]=30，SR[j]= SR[6]=20，SR[i]>SR[j]，執(zhí)行第9行，TR[k]=TR[2]=20，并且j++，如圖10。</p><p><b>　　圖10</b></p><p>　　5) 再次循環(huán)，k++得到k=3，SR[

38、i]=SR[2]=30，SR[j]= SR[7]=40，SR[i]<SR[j]，執(zhí)行第7行，TR[k]=TR[3]=30，并且i++，如圖11。</p><p><b>　　圖11</b></p><p>　　6) 接下來(lái)完全相同的操作，一直到j(luò)++后，j=10，大于9退出循環(huán)。如圖12。</p><p><b>　　

39、圖12</b></p><p>　　7) 第11～20行的代碼，其實(shí)就將歸并剩下的數(shù)組數(shù)據(jù)，移動(dòng)到TR的后面。當(dāng)前k=9，i=m=5，執(zhí)行第13～20行代碼，for循環(huán)l=0，TR[k+l]=SR[i+l]=90。大功告成。</p><p>　　2.7 程序運(yùn)行說(shuō)明</p><p>　　首先輸入需要進(jìn)行二路歸并排序的個(gè)數(shù)N，然后輸入需要進(jìn)行二路

40、歸并排序的數(shù)據(jù)，期間有空格或者是回車(chē)均可，最后輸出結(jié)果。</p><p>　　2.8 程序運(yùn)行截圖</p><p>　　輸入本是無(wú)序的數(shù)組序列{16,7,13,10,9,15,3,2,5,8,12,1,11,4,6,14}，運(yùn)行結(jié)果如下（圖13）：</p><p><b>　　圖13</b></p><p><b&

41、gt;　　小 結(jié)</b></p><p>　　通過(guò)本次課程設(shè)計(jì)，我對(duì)于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，線(xiàn)性表的查找以及歸并排序有了更近一步的了解。開(kāi)始對(duì)很多東西感到莫名其妙，很難理解各個(gè)簡(jiǎn)單游戲和系統(tǒng)的管理及編程，總覺(jué)得他們是很抽象的東西，但是在學(xué)習(xí)了《數(shù)據(jù)結(jié)構(gòu)與算法》這門(mén)課程之后，我慢慢地體會(huì)到了其中的奧妙，首先要捕捉他有哪些具體化、數(shù)字化的信息，這也就說(shuō)明了想要把生活中的信息轉(zhuǎn)化到計(jì)算機(jī)中必須用數(shù)字來(lái)完整的構(gòu)成一

42、個(gè)信息庫(kù)。</p><p>　　當(dāng)然對(duì)于此設(shè)計(jì)也存在很多的缺點(diǎn)。比如說(shuō)，對(duì)于線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)，雖然，可以隨機(jī)存儲(chǔ)任意元素，但是插入和刪除元素是需要移動(dòng)大量的元素，而且，在計(jì)算機(jī)內(nèi)需要預(yù)先分配最大的存儲(chǔ)空間;而在順序表的查找過(guò)程中，如果數(shù)據(jù)元素過(guò)多，對(duì)于順序查找很不方便。</p><p>　　計(jì)算機(jī)中實(shí)現(xiàn)這么一個(gè)很簡(jiǎn)單的想法就需要涉及到很多專(zhuān)業(yè)知識(shí)，為了完成設(shè)計(jì)，在前期工作中，基本都是以

43、學(xué)習(xí)C語(yǔ)言為主，所以浪費(fèi)了很多時(shí)間，但是我在這次課設(shè)中也學(xué)到了很多。把我在書(shū)本上難以理解的東西都給解決了，同時(shí)還鍛煉了我的動(dòng)手操作能力。我很感激這次的課題設(shè)計(jì)。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]嚴(yán)蔚敏 吳偉民 著， 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），清華大學(xué)出版社，2007.4</p><p>　　[2]李春葆 著，

44、數(shù)據(jù)結(jié)構(gòu)教程，清華大學(xué)出版社，2005.1</p><p>　　[3] [美]Deitel,H.M.，[美]Deitel,P.J.著, C程序設(shè)計(jì)經(jīng)典教程，清華大學(xué)出版社，2006</p><p>　　[4] 孫鑫.VC++深入詳解.北京：電子工業(yè)出版社.2007</p><p>　　[5]錢(qián)能.C++程序設(shè)計(jì)教程.北京：清華大學(xué)出版社.2009</p>

45、<p><b>　　附 錄</b></p><p>　　#include <stdio.h></p><p>　　void merge( int a[ ] , int b[ ] , int l , int m , int h )</p><p>　　{//將有序的a[l..m]和b[m+1..h]合并成有序表b[l..

46、h]</p><p>　　int i,j,k;</p><p><b>　　i=l;</b></p><p><b>　　j=m+1;</b></p><p><b>　　k=l;</b></p><p>　　//將兩個(gè)有序表中較小的放入b中</p

47、><p>　　while( i<=m && j<=h){</p><p>　　if( a[i] < a[j])</p><p>　　b[k++]=a[i++];</p><p><b>　　else</b></p><p>　　b[k++]=a[j++];</p

48、><p><b>　　}</b></p><p>　　while( i<=m )</p><p>　　b[k++]=a[i++];</p><p>　　while( j<=h )</p><p>　　b[k++]=a[j++];</p><p>　　for(int

49、q=l; q<=h; q++)//必要操作，有的課本會(huì)遺漏此步，使a與b相等</p><p>　　a[q]=b[q];</p><p><b>　　}</b></p><p>　　void merge_sort(int a[ ] ,int b[ ] ,int l ,int h)</p><p><b>　

50、　{</b></p><p>　　if( l == h )</p><p>　　b[l]=a[l];</p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　int m;</b><

51、;/p><p>　　m = (l+h)/2;</p><p>　　merge_sort( a , b , l , m );//對(duì)第一部分調(diào)用遞歸排序</p><p>　　merge_sort( a , b , m+1 , h );//對(duì)第二部分調(diào)用遞歸排序</p><p>　　merge( b , a , l , m , h );//將兩個(gè)有序表

52、合并為一個(gè)有序表</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void binary(int a[ ] ,int n)</p><p><b>　　{</b></p><p><b>　　

53、int *b;</b></p><p>　　b=new int[n];//b為臨時(shí)數(shù)組，函數(shù)結(jié)束后釋放</p><p>　　merge_sort( a , b , 0 , n-1 );</p><p><b>　　}</b></p><p>　　int main( )</p><p>

54、<b>　　{</b></p><p><b>　　int n,i;</b></p><p><b>　　int *a;</b></p><p>　　for(i = 0; i < 60; i++) printf("*");</p><p>　　prin

55、tf("\nplese enter what the number of compare:");</p><p>　　scanf("%d",&n);</p><p>　　a=new int[n];</p><p>　　for(int i=0; i<n ;i++)</p><p>　　sca

56、nf("%d",&a[i]);</p><p>　　binary( a , n);</p><p>　　for(int i=0; i<n-1 ;i++)</p><p>　　printf("%d,",a[i]);</p><p>　　printf("%d",a[n-1]