1、課程設計任務書學生姓名：_ 專業班級：_指導教師： _ 工作單位：題目：歸并排序的設計與實現初始條件：理論：學習了數據結構課程，掌握了基本的數據結構和常用的算 法；實踐：計算機技術系實驗室提供計算機及軟件開發環境。要求完成的主要任務: :（包括課程設計工作量及其技術要求，以及說明書撰寫 等具體要求）1、系統應具備的功能：（1）輸入一組數,用遞歸和非遞歸程序實現歸并排序（2）分析歸并排序的復雜度（3）將歸并排序的思想用于外部排序中2、數據結構設計；3、主要算法設計；4、編程及上機實現；5、撰寫課程設計報告，包括：（1）設計題目；（2）摘要和關鍵字（中文和英文）；（3）正文，包括引言、需求分析、數

2、據結構設計、算法設計、程序實現 及測試、設計體會等；（4）結束語；（5）參考文獻。時間安排：20102010 年元月 1010 日一 1414 日（第 1919 周）元月10日查閱資料元月11日系統設計，數據結構設計，算法設計元月12日-13日編程并上機調試元月14日撰寫報告元月15日 驗收程序，提交設計報告書。歸并排序的設計和實現摘要：該程序主要由五個部分組成：把一組待排的數據信息放在結構體里，2- 路歸并排序，對數組作一趟歸并排序，對數組作歸并排序，主函數。Abstract: The program mainly consists of five parts: the a row of d

3、atato be placed on structure, the 2 - way merge sort, for a trip to the array Merge sort,merge sort on the array as the main function.關鍵字:模型化,2-路歸并，一趟歸并，歸并Keywords: modeli ng, 2 - way merge, a trip to merge, merge0.引言歸并排序是一種穩定的內部排序，“歸并”的含義是將兩個或兩個以上的有 序表組合成一個新的有序表。無論是順序存儲結構還是鏈表存儲結構，都可在0(m+n的時間量級上實現。利

4、用歸并的思想容易實現排序。2路歸并排序：假設初始序列含有n個記錄，則可看成是n個有序的子序 列，每個子序列的長度為1,然后兩兩歸并，得到不小于n/2整數個長度為2或1的有序子序列；再兩兩歸并，如此重復，直至得到一個長度為n的有序序 列為止。1. 算法把握1.1 歸并排序算法的具體分析咋一看，歸并排序時一種“費力不討好”的排序方法，因為最后一趟始終要對整個序列進行排序，這會使的前幾趟的排序似乎是在做無用功，其實不然。對初始關鍵字兩兩分組并進行組內排序后，在下一次處理中，并不是簡單地在組容量擴大一倍的基礎上重新排序， 而是把上一趟已經排好序的兩組數組重新合并成 一個新的有序組。指導教師簽名:201

5、02010年元月 1010 日系主任（或責任教師）簽名:20102010年元月 1010 日這個把兩個有序組合并到一個新的有序組的過程要比單獨排序 快得多。歸并排序的核心操作時合并有序組。對于最開始的兩兩分組，也可以看成是兩個只含有1個關鍵字的組進行合并。1.2除了核心的合并操作外，需要先把序列進行分組，每次組容量減半，直到組內只有一個關鍵字為止，再對組進行合并，直到所有關鍵字都屬于一組為止。 實際上，分組采用遞歸的方法更加方便。2. 需求分析(1)通過建立一個結構體，用來存放數據信息，包括數據的個數，本身記錄。(2) 2路歸并排序的算法，實現兩兩歸并。(3)主函數初始化數據，選擇歸并排序的方

6、法及打印數據結果。3. 數據結構設計用結構體存儲待排的數據。#i nclude#define MAX 100 /*定義MAX是最大的允許輸入數字個數*/typedef structint n;/* n為文件中的記錄個數，nM AXNUM */int dataMAX;lqlist;4. 算法設計4.1 2-路歸并排序的非遞歸算法II將有序的SRi.m和SRm+1.n歸并為有序的TRi.nvoid merge(RcdType SR,RcdType&TR,int i,int m,int n)for(j=m+1,k=I;i=m&jv=n ;k+)II將SR中記錄由小到大的并入TRif(

7、LQ(SRi.key,SRj.key)TRk=SRi+;else TRk=SRj+;if(i=m)TRk.n=SRi.m; /將剩余的SRi.m復制到TRif(j=n)TRk.n=SRj.n; /將剩余的SRi.m復制到TR/merge4.2 2-路歸并排序的遞歸形式void Msort(RcdType SR,RcdType&TR1,int s,int t)/將SR歸并排序為TRif(s=t)TR1s=SRs;elsem=(s+t)/2; /將平分為SRs.t和SRm+1.tMsort(SR,TR2,s,m);/遞歸的將SRs.m歸并為有序的TR2s.mMsort(SR,TR2,m+1

8、,t);/遞歸地將SRm+1.t歸并為有序的TRm+1.tMerge(TR2,TR1,s,m,t);/將TR2s.m和TR2m+1.t歸并到TR1s.t/mergesort/mergesort4.3 對順序表 L 作歸并排序Void mergesort(SqList &L)Msort(L.r,L.r,1,L.le ngth);/mergesort4.4 非遞歸形式歸并算法void merge(i nt r, int r1, int low, int m, int high)/* rlow到rm和rm+1到rright是兩個有序段*/int i = low, j = m + 1, k =

9、 low;while ( i = m & j = high )/*反復復制兩個段的第一個記錄中較小的*/if (ri = rj)r1k+ = ri+;elser1k+ = rj+;while (i = m)r1k+ = ri+; /*復制第一個段的剩余記錄*/while (j = high)r1k+ = rj+;/*復制第二個段的剩余記錄*/4.5 對 r 做一趟歸并的算法void mergePass(i nt r, int r1, int n, int len gth) int i = 0, j;/*length為本趟歸并的有序子段的長度*/while(i + 2*le ngth -

10、 1 n)/*歸并長length的兩個子段*/merge(r, r1, i, i+length-1, i + 2*length - 1);i += 2*le ngth;if(i + length - 1 n - 1)/*剩下兩段，后一段長度小于len gth */merge(r, r1, i, i+le ngth-1, n-1);else/*將剩下的一段復制到數組r1 */for(j = i; j n; j+) r1j = rj;4.6 對整個數據進行歸并的算法void mergeSort(SortObject * p )int dataMAXNUM;in t le ngth = 1;whil

11、e (le ngth n)/*一趟歸并，結果存放在數組record中*/mergePass(p-record, record, p-n, len gth);len gth *= 2;/*一趟歸并，結果存回*/mergePass(record, p-record, p-n, len gth);len gth *= 2;4.7 主程序main()*cout* *e ndl;cout歸并排序的遞歸和非遞歸實現*e ndl；Iqlist p;int i=0, z, m,k;coutvv請輸入所要比較的數字組，以10000結束： z;while (z!=10000&i z;p.n =i;cout

12、排序前的數組是：endl;for(i=0;ip.n ;i+)coutvvp.data i;coutvv請選擇需要歸并排序的方法endl1.選擇遞歸方法。endl;cout2.選擇非遞歸方法。m;if(m=1)M(&p);else if(m=2)mergesort2(&p);elsecoutvv輸入有誤。endl;coutvve ndlvv排序后的數組：e ndl;for(i=0;ip.n ;i+)e ndl;cout/*輸出排序前的數組*/coutvp.dataivv ;coute ndl;cout請選擇服務:endl;if(m=1)cout1.選擇非遞歸方法。e ndl;el

13、secout1.選擇遞歸方法。endl;cout2.退出。 k;if(m=1 &k=1)M(&p);/*選擇遞歸方法進行歸并排序*/else if(m=2&k=1)mergesort2(&p); /*選擇非遞歸方法進行歸并排序*/else if (k=2)return 0;coute ndlvv排序后的數組：e ndl;for(i=0;ip.n ;i+)/*輸出遞歸排序后的數組*/coutvp.dataivv;coute ndl;return 0;5. 程序的實現5.1 完整程序#i nclude#defi ne MAX 100typedef structint

14、 n;int dataMAX;lqlist;void merge(int a,int s1,int e1,int s2,int e2,int b)int k=s1;int i=s1;while(s1=e1)&(s2=e2)if(as1v=as2)/*將數組as1和數組as2中小的數據暫存到數組b中*/bk=as1;k+;s1+;else /*將數組as1和數組as2中小的數據暫存到數組b中*/bk=as2;k+;s2+;while(s1=e1) /*將第一個數組中剩余的數據暫存到數組b中*/bk=as1;k+;s1+;while(s2=i) /*將暫存數組b中的數據村回到a中*/ak=

15、bk;k-;void mergesort(i nt a,i nt i,i nt j,i nt b)int k;if(idata,0, q-n-1,c);void merge2 (int r,i nt r1,i nt low,i nt m,i nt high)/*rlow至到rm和rm+1到rright是兩個有序段*/int i=low,j=m+1,k=low;while (i=m&jv=high) /*反復復制兩個段的第一個記錄中的較小的*/if(ri=rj)r1k=ri;k+;i+;else r1k=rj;k+;j+;while(i=m) /*復制第一個段的剩余記錄*/r1k=ri;

16、k+;i+；while(jv=high)/*復制第二個段的剩余記錄*/r1k=rj;k+;j+；/*對r做一趟歸并，結果放在r1中*/void mergepass2(i nt r,i nt r1,i nt n ,i nt len gth)/*length為本趟歸并的有序子段的長度*/int i=0,j;while(i=n-2*le ngth+1) /*剩下兩段，后一段長度小于len gth*/merge2(r,r1,i,i+length-1,i+2*length-1);/*歸并長length的兩個子段*/i+=2*le ngth;if(i n-le ngth+1)/*剩下兩段，后一段長度小于l

17、en gth */merge2(r,r1,i,i+le ngth-1, n-1);else/*將剩下的一段復制到數組r1 */for(j=i;jn)/*一趟歸并，結果存在數組record中*/mergepass2(p-data,data,p-n ,le ngth);len gth*=2;/*一趟歸并，結果存回*/mergepass2(data,p-data,p- n,le ngth);len gth*=2;mai n()/*歸并排序的遞歸和非遞歸實現e ndl;*lqlist p;int i=0, z,m,k;coutvv請輸入所要比較的數字組，以10000結束： z;while (z!=10

18、000&i z;* *e ndl;cout* *e ndl;coutp.n =i;cout排序前的數組是：endl;for(i=0;ip.n ;i+)coutvvp.data i;coutvv請選擇需要歸并排序的方法endl1.選擇遞歸方法。endl;cout2.選擇非遞歸方法。endl;cinm;if(m=1)M(&p);else if(m=2)mergesort2(&p);elsecout輸入有誤。endl;coute ndlvv排序后的數組：e ndl;for(i=0;ip.n ;i+) /*輸出歸并前的數組*/coutp.datai ;coute ndl;cou

19、t請選擇服務:endl;if(m=1)cout1.選擇非遞歸方法。e ndl;elsecout1.選擇遞歸方法。endl;cout2.退出。 k; /*再次進行選擇服務(另一種排序方法還是退出)*/if(m=1 &k=1)M(&p);/*將用遞歸方法進行歸并排序*/else if(m=2&k=1)mergesort2(&p); /*將用非遞歸方法進行歸并*/else if (k=2)return 0;coute ndlvv排序后的數組：e ndl;for(i=0;ip.n ;i+)coutvp.dataivv;coute ndl;return 0;5.2 程序運

20、行過程說明該程序的功能是實現歸并排序，程序的運行過程中需要實驗者輸入所要進行 歸并排序的數字組(最多不能超過 皿硏)，并且以10000結束，輸入數字組后， 程序會輸出實驗者輸入的數字組(不包括最后實驗者輸入的10000),并需要實驗者自己選擇需要歸并的方法(遞歸方法或非遞歸方法)，當實驗者輸入一種歸 并排序的方法后程序會運用該方法進行歸并排序，并輸出該方法排序的結果，并 繼續需要實驗者選擇進行另一種排序方法還是需要退出，當實驗者選擇另一種方法時，程序會進行另一種歸并排序的方法，并輸出排序后的結果，然后程序自動結束。如果實驗者在第二次選擇時直接選擇退出，程序不會進行另一種歸并排序 方法，直接結束

21、程序。5.3 程序運行結果6. 歸并排序的復雜度分析遞歸排序所消耗的時間有兩部分組成：分組時間和合并時間。給定序列中有n個元素，同時為了方便計算，假設n為2的幕，這樣的每次分組，會分成偶數 的兩部分。用于合并的時間隨著元素數量的增加時線性增長的，這個時間不超過cn(c為某個常數)，所以歸并算法所消耗的時間為T(n)=2T(n/2)+cn.最后化簡 得：T(n)=n+cnlogn.所以最后得出歸并排序的時間復雜度是0 (nlogn)。歸并排序的最大不足在于它需要與原序列大小相同的輔助空間，而且分組合并后還需要把輔助空間的數據復制回原序列，這會進一步降低算法的速度。7. 設計體會通過這次實驗我也著

22、實又感受了一次編程的樂趣，從中也學到了不少知識。 做程序是一個比較累的工作，特別是當遇到困難時，程序通不過時，真的很令人 沮喪。但是改正一個錯誤時，那種喜悅心情也很令人期盼，這種心情堪比久旱見 甘霖的喜悅。就是因為有這種令人身心愉悅的可能， 我才得以能夠整晚不睡來改 程序中的不足之處。編程中有苦有樂，其中的苦樂只有親身經歷才能體會到。 要 想做出好的程序，必須做好忍受其間痛苦的準備。雖然都說“程序二數據結構+算法”，但我在學習運用數據結構編程之前， 并沒能深刻體會到這一點，直到這次課設實踐。我感受最深的一點是：以前用c、C+編程，只是注重如何編寫函數能夠完成所需要的功能， 似乎沒有明確的戰術，

23、 只是憑單純的意識和簡單的語句來堆砌出一段程序，只要能完成任務就行。但現 在編程感覺完全不同了。在編寫一個程序之前，自己能夠綜合考慮各種因素，首 先選取自己需要的數據結構，是樹還是圖或是別的什么？然后選定一種或幾種存 儲結構來具體的決定后面的函數的主要風格。最后在編寫每一個函數之前，可以 仔細斟酌比對，挑選出最適合當前狀況的算法。 這樣，即使在完整的程序還沒有 寫出來之前，自己心中已經有了明確的原圖了。這樣無形中就提高了自己編寫的 程序的質量。另外，我還體會到深刻理解數據結構的重要性。 只有真正理解這樣定義數據 類型的好處，才能用好這樣一種數據結構。 了解典型數據結構的性質是非常有用 的， 它往