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

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

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

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

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

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

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

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

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

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

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

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

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

13、返回L中數(shù)據(jù)元素的個數(shù)；</p><p>　　GetElem(L,I,&e) 操作結(jié)果：用e返回L中第i個數(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>　　/* 對順序表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è)計&

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

18、gt;　　遞歸算法實現(xiàn)中，最重要的就是對[n/2]進行很多次的歸并遞歸排序算法的設(shè)計，調(diào)用函數(shù)MSort中采用了遞歸的算法思想，用較簡短的語句，實現(xiàn)了多次遞歸排序。假設(shè)現(xiàn)在要對數(shù)組{50,10,90,30,70,40,80,60,20}進行排序，L.length=9，一下就是MSort主要代碼及實現(xiàn)過程。</p><p>　　/* 將SR[s..t]歸并排序為TR1[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)用時，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行語句塊。</p><p>　　第9行，m=(1+9)/2=5。m就是序列的正中間下標</p>

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

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

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

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

28、<p>　　2.6.2歸并排序算法的整合</p><p>　　在經(jīng)過每個新的排序片段以后，程序產(chǎn)生新的數(shù)組，如何讓新的數(shù)組依然按照一定順序進行排序, 即將SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]，此時就要進行Merge()函數(shù)的調(diào)用。一下就是Merge()函數(shù)實現(xiàn)的詳細過程：</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è)我們此時調(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開始到9，i由1開始到5，k由1開始每次加1，k值用于目標數(shù)組TR的下標。</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) 接下來完全相同的操作，一直到j(luò)++后，j=10，大于9退出循環(huán)。如圖12。</p><p><b>　　

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

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

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

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

43、學(xué)習(xí)C語言為主，所以浪費了很多時間，但是我在這次課設(shè)中也學(xué)到了很多。把我在書本上難以理解的東西都給解決了，同時還鍛煉了我的動手操作能力。我很感激這次的課題設(shè)計。</p><p><b>　　參考文獻</b></p><p>　　[1]嚴蔚敏 吳偉民 著， 數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(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īng)典教程，清華大學(xué)出版社，2006</p><p>　　[4] 孫鑫.VC++深入詳解.北京：電子工業(yè)出版社.2007</p><p>　　[5]錢能.C++程序設(shè)計教程.北京：清華大學(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>　　//將兩個有序表中較小的放入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++)//必要操作，有的課本會遺漏此步，使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 );//對第一部分調(diào)用遞歸排序</p><p>　　merge_sort( a , b , m+1 , h );//對第二部分調(diào)用遞歸排序</p><p>　　merge( b , a , l , m , h );//將兩個有序表

52、合并為一個有序表</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ù)結(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]