1、程設計課程設計名稱：排序綜合專業班級：學生姓名：學 號:指導教師：課程設計時間：計算機應用技術專業課程設計任務書學生姓名專業班級學號JS目排序綜合課題性質A課題來源D指導教師同組姓名無主要內容運用c語言的知識對程序進行模塊化設計；運用數據結構的知識分別對七種排序方法進行設計；采用菜單式對排序結果進行輸出；任務要求綜合運用這一年來所學的C語言知識與數據結構的知識對所選的課題進行 詳細的設計，任務分為9個模塊進行設計分別為：插入排序函數、冒泡排序函 數、快速排序函數、選擇排序函數、希爾排序函數、歸并排序函數、堆排序函 數以及選擇函數與主函數。參考文獻數據結構（C語言版）嚴蔚敏 清華大學出版社C語言

2、程序設計（第三版）譚浩強清華大學出版社數據結構教程（C語言版）西安電子科技大學數據結構教程上機實驗指導清華大學出版社審査意見指導教師簽字：教研室主任簽字：2014年6月15日 TOC o 1-5 h z HYPERLINK l bookmark4 o Current Document 1、需求分析：4 HYPERLINK l bookmark6 o Current Document 2、概要設計4 HYPERLINK l bookmark8 o Current Document 3、運行環境51）、軟件環境52）、硬件環境5 HYPERLINK l bookmark10 o Current D

3、ocument 4開發工具和編程語言5 HYPERLINK l bookmark12 o Current Document 5詳細設計5 HYPERLINK l bookmark14 o Current Document 6調試分析12 HYPERLINK l bookmark16 o Current Document 7測試結果12一、泗!試方法:12二、測試結果：12 HYPERLINK l bookmark18 o Current Document 參考文獻15 HYPERLINK l bookmark20 o Current Document 心得體會161 X需求分析：排序綜合問題，

4、用數據結構的思想對一些數字進行排序，實現以下排序功能:1、插入排序2、冒泡排序3、快速排序4、選擇排序5、希爾排序6、歸并排序7、堆排序2、概要設計1、程序總體框架圖如下：2、程序中各函數簡單說明見如表1函數說明所示:返回值函數名參數表函數說明iiitmamvoid主函數voidDJnseilRecoidTvpe R插入排序voidBubbleSoitRecoidTvpe R冒泡排序iiitPartitionRecoidTvpe R劃分算法voidQuicksortRecoidTvpe R快速排序voidSelectSoilRecoidTvpe R選擇排序voidShellSoitRecoid

5、Tvpe R希爾排序voidMeigeSortRecoidTvpe R歸并排序voidHeapAdjustRecoidTvpe R堆排序voidDisplay顯不表1函數3、運行環境、軟件環境操作系統：windows7windows8、硬件環境處理器：Intel Pentium 166MX或更高內存:64MB硬盤空間：1T顯卡：SVGA顯示適配4開發工具和編程語言編程珂:境：Dev-C+ 5.0 beta 9.2 (4.9.9.2)編程語言：C語言，ANSI C895詳細設計/*排序綜合*/# iiiclude#define MAXSIZE 300tvpedef stmctint key；ch

6、ar data;RecoidType；/*插入排序*/void D_Insen(RecoidT?pe R,mt n)M 11個記錄序列Rl-Rn進行直接插入排序intij;for(i=2;iR0 .key)/*將關鍵字值人于Ri.kevQ即此時的R0.key的所有l,i-2,)順序后移一個記錄位置*/RU+l=Rj；J-；Rj+1=RO;/*冒泡排序*/void BubbleSon(RecoidTvpe R.mt n)/對RlRn這n個記錄進行冒泡排序int i,j,swap;fbr(i=l;in;i-H-)swap=0;for(j=ljRj+l.key)如果Rj.key大于Rj+l.key則

7、交換它倆RO=R|J；Rj=Rj+l；Rj+1=RO;swap=l;if(swap=0)break;嚴快速排序*/mt Panition(RecoidTvpe R.iiit Lmt j)劃分算法/對Ri卜Rj,以Ri為基準記錄進行劃分，并返回RKi在劃分后的正確位置RO=Ri；wlule(ij)while(i=RO.key)從左向右掃描查找第一個關鍵字小于RO.key的記錄R卜；if(ij)/當i小于j時則R|j.key小于RO.key將Rj交換到表的左端 R】=R|；i+；while(ij &Ri .kev=RO .key)從左當右打描查找第一個關鍵字大于RO.key的記錄Ri i+；Rj=

8、Ri；j-；Ri=RO;retuin i;void QuickSoit(RecordType Rjnt s,int t)/進行快速排序int i;if(st)i=Partition(R,s,t);/l為基準記錄的位置并由此將表分為RsRi-l和Ri+1卜Rt兩部分QuickSoit(R.sj-l);QuickSort(Rj+1 ,t);/*選擇排序*/void SelectSort(RecordType Rjnt n)對于RlbRn這n個記錄進行選擇排序int i,j,k;fbi(i=l;in;i-H-)k=i;for(j=i+l;j=nj+)if(R|j .keyRk .key)k=J；if

9、(i!=k)R0=Rk;Rk=Ri;R】=R0;/*希爾排序*/void ShellIiisen(RecoidType R,iiit n.mt d)對R1卜Rn這n個記錄進行希爾排序，d為增長因子(步長)intij;for(i=d+1 ;i0&R0 .key-Rlj -key J=j -d)Rj+d=Rj;Rj+d=RO;void ShellSoit(RecordType R.iiit n)/進行希爾排序int d10,t,k;pnntf(n輸入增量因子的個數n”)；pnntfC*由人到小輸入每個增量因子:n);for(k=0;kt;k+) scanf(”d“,&dk);for(k=0;kt;

10、k+)ShellInsert(R,n,dk);/*歸并排序*/void Merge(RecordTvpe R,RecordType R!,int k,int n)一趟二路歸并 int ijjl,ul,12,u2,m;11=0;m=0:wlule(ll+kn)12=11+k;ul=12-l;if(12+k-ln)u2=12+k-l;elseu2=n-l;for(i=ll J=12 ;i=u 1 &j=u2 ;m+)if(Ri .key=Rj.key)Rlm=Ri+;elseRlm=Rj +;while(i=ul)Rlm+=Ri-H-;while(j=u2)Rlm+=Rj-H-;ll=u2+l;f

11、br(i=ll ;in;i+4ii+)Rli=Ri；void MergeSort(RecordType R,iiit n)非遞歸方法進行歸并排序mt nk;RecordTvpe R1 MAXSIZE;k=l;wlule(kn)Merge(R,Rhk4i);fbr(i=O;in;i+)Ri=Rli；k=2*k;/*堆排序*/void HeapAdjust(RecordType R,int sjnt t)基于人根堆得堆排序 intij;RO=Rs;i=s;for(j=2*ij=t;j=2*j)/關鍵字較人的孩子向卞調整，先假定為左孩子 &Rj.keyRj .key)break;Ri=Rj；l=j;

12、Ri=RO;void HeapSort(RecordType R,int n)/進行堆排序mt i;HeapAdjust(R.iai); fbr(i=n;il;i)fR0=Rl;Rl=Ri;R】=R0；HeapAdjust(R 1 j-1);嚴顯示*7void Display()pnntfC*插入排序按 l*iiM); pnntf(* * * * 冒泡排序按 2* * * *n”); pnntff*快速排序按 3*n”); printf(*選擇排序按 4*n); pnntfC*希爾排序按尹*ir); pnntf(* * * * 歸并排序按 6* * * * *n”); pnntfC*堆排序按

13、7*ir);int i=l,j、x;int Key;RecordTvpe RMAXSIZE; pnntf(Mn*歡迎登陸排序系統*:ir); pnntfCn*以-1作為結束標志*:n”)； pnntf(”n請寫出你要排序的數:n”)； scanff%dt&x);while(x!=-l)Ri.key=x;scanf(”d”、&x);i+;pnntf(”輸出有效數字:n”)； for(j=ljij+)pimtf(%4d,R|j.key);pnntfViiSort*ir)+pnntf(”n請輸入你要選擇的排序類型:n”);DisplayO； piintf(MEnter Key:”)； scanff%

14、cT：&Key);if(Ke 尸=1)pnntf(插入排序如下:”)； D_Insert(Rj-l);else if(Key=:2)pnntf(“冒泡排序如下:”)；BubbleSort(Rj-l);else ifK.cy=rt)pnmf(快速排序如下:”)；QuickSort(R, 1else if(Key=4)prmtfC選擇排序如下:”); SelectSon(Rj-l);else ifKcy=5)希爾排序如卜:”)；ShellSoit(R4-l);else if(Key=6)pnmf(“歸并排序如卞:”)； MebgeSort(Rj-l);else ifKcy=l)printfC堆排序

15、如下:J;HeapSoit(Rj-l);elsepnntf(”請輸入17間的數字”)；for(j=lJij+)pimtf(n%4d,RIj.key);6調試分析1、測試中的問題舉例：在進行快速排序時輸入一行數字當運行時無論怎樣也不出現排序后的 結果，經過多次檢查后發現在進行劃分算法時ij的值取法不當，最后經重新修 改后運行。2、算法改進設想舉例在程序中有很多不如意的地方，在進行歸并排序時用的是非遞歸的排序算 法，算法略顯冗雜。在進行歸并排序時可以采用遞歸排序，釆用遞歸排序的思想 對此進行快速的排序算法，另外還可以設計一個計算程序運行時間的函數并計算 每個排序算法所耗費的時間，選出較為優秀的排序

16、算法。7測試結果一、測試方法如下：1、輸入你想要測試的一組數字，并以T作為結束標志2、選擇你想要進行的測試類型3、調用你想要測試類型的函數4、輸出測試結果二、測試結果如下：1、插入排序結果2、選擇排序結果:3、希爾排序結果:4、歸并排序結果:5、堆排序結果:參考文獻嚴蔚敏，數據結構（C語言版）清華大學出版社譚浩強.C語言程序設計（第三版） 清華大學出版社胡元義數據結構教程（C語言版） 西安電子科技大學李春葆數據結構教程上機實驗指導 清華大學出版社心得體會通過這次的數據結構課程設計我深深地體會到數據結構思想在c語言編程中 的巨大用途，在進行排序綜合這個課程設計題目的過程中，我多處都運用了數據 結構的思想，例如：在我進行快速排序時其中的劃分算法快速排序中起著橋梁的 作用，正是數據結構的這種思想才能簡便而乂快捷的完成快速排序這項功能，另 外堆排序中也運用了二叉樹的思想。完成這次課程設計的過程中還發現了自己的 諸多不足之處，這次課程設計確確實實提高了自己的編程能力。信息科學與工程彥It鎬裡截針嵐債評價來課程名稱：數據結構課程設計設計題目：排序綜合專業：班級：姓名：學號:序號評審項目分數滿分標準說明1內容思路清晰：語言表達準確