1、.*大學本科生課程設計論文題 目：排序算法集成學生姓名：學 號：專 業：計算機班 級：指導教師：2013年5月20日*大學課程設計任務書課程名稱數據結構課程設計設計題目排序算法集成指導教師時間2013.5.20-2013.5.30一、教學要求1. 掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力2. 初步掌握軟件開發過程的問題分析、系統設計、程序編碼、測試等基本方法和技能3. 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力4. 訓練用系統的觀點和軟件開發一般規范進行軟件開發，培養軟件工作者所應具備的科學的工作方法和作風二、設計資料及參數每個學生在教師提供的課程設計題目中任意

2、選擇一題，獨立完成，題目選定后不可更換。排序算法集成定義動態數組類（或類模板）以表示待排序數據，在此基礎上實現多種排序算法。要求設計函數模板來實現下列排序算法：v 直接插入排序v 冒泡排序v 簡單選擇排序v 希爾排序v 快速排序v 堆排序 并設計主函數測試動態數組類（或類模板），測試各排序算法的函數模板。三、設計要求及成果1. 分析課程設計題目的要求2. 寫出詳細設計說明3. 編寫程序代碼，調試程序使其能正確運行4. 設計完成的軟件要便于操作和使用5. 設計完成后提交課程設計報告四、進度安排資料查閱與討論（1天）系統分析（2天）系統的開發與測試（5天）編寫課程設計說明書和驗收（2天）五、評分標

3、準1. 根據平時上機考勤、表現和進度，教師將每天點名和檢查2. 根據課程設計完成情況，必須有可運行的軟件。3. 根據課程設計報告的質量，如有雷同，則所有雷同的所有人均判為不及格。4. 根據答辯的情況，應能夠以清晰的思路和準確、簡練的語言敘述自己的設計和回答教師的提問六、建議參考資料1數據結構 （C語言版）嚴蔚敏、吳偉民 主編 清華大學出版社 2004.112數據結構課程設計案例精編（用C/C+描述），李建學 等 編著，清華大學出版社 2007.23.數據結構:用面向對象方法與C+語言描述，殷人昆 主編， 清華大學出版社 2007.6目 錄目錄3引言4一算法的設計思想4二算法的流程圖4

4、三算法的設計與分析53.1建立數組53.2 算法思想53.3主要函數63.4主要函數聲明63.5 主要變量說明10四程序源代碼11五運行結果與分析（測試）18六總結（收獲與體會）20七參考文獻21引 言本課程設計主要解決幾種不同排序方法以及在各種不同排序的過程中某一趟的具體排序結果。通過觀察各種排序的具體排序過程，加深對不同排序方法的認識，加深對不同排序算法的掌握。一算法設計的思想數據結構是與數據相關的一門重要學科，不論是想通過升學考試還是想把程序編得有水平，都要對這門學科下一點功夫才行。而課程設計是讓我們更好的掌握這門學科的重要方式。排序是計算機程序中的一種重要操作，它的功能是將一個數據元素

5、（或記錄）的任意序列重新排列成一個按關鍵字有序的序列。而內部排序中包括各種不同的排序，本課程設計主要討論的是插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序。 完成這幾種排序最主要的就是弄好不同排序的算法，只有深刻的認識了這不同排序的算法，才能了解不同排序的優點與缺點。通過對不同排序算法的分析，了解它們的優劣特點。據對題目的分析，首先要根據插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序的不同算法，寫出實現各個排序算法的函數。然后通過在主函數中對不同排序的子函數的調用來實現對某個序列的具體排序。內部排序的方法很多，但就其全面性而言，很難提出一種被認為是最好的方法，每一種方法都有

6、各自的優缺點，適合不同的環境。通常，在排序的過程中需進行兩種基本操作：（1）比較兩個關鍵字的大小；（2）將記錄從一個位置移動至另一位置。前一個操作對大多數排序方法來說都是必要的，而后一個操作可以通過改變記錄的存儲方式來予以避免。二算法的流程圖如圖2.1建立數組設計main函數建立各排序函數結束開始圖2.1 主要設計思想流程圖三算法的設計與分析3.1建立數組在程序中建立一個數組data ，用于存儲程序運行中的數據。3.2算法思想（1）插入排序 插入排序的主要算法思想是將一個記錄插入到已排好的有序表中，從而得到一個新的、記錄數增1的有序表。（2）希爾排序 希爾排序的基本思想是先將整個待排記錄列分割

7、成若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。（3）冒泡排序函數 冒泡排序首先將第一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序則將兩個記錄交換，然后比較第二個記錄和第三個記錄的關鍵字，依次類推。（4）選擇排序函數 選擇排序的基本思想是：每一趟在n-i+1(i=1,2,n-1)個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。（5）堆排序 先將一個序列進行建堆，然后將大頂堆的第一個元素和最后一個元素對換（或將小頂堆的最后一個元素和第一個元素對換），再對除最后一個元素的序列進行求大頂堆（或對除第一個元素的序列進行求小頂堆），依次

8、類推。 3.3 主要函數（1）插入排序函數void insertion_sort(int,int);/*插入排序*/（2）希爾排序函數void shell_sort(int,int);/*希爾排序*/（3）冒泡排序函數void bubble_sort(int,int);/*冒泡排序*/（4）選擇排序函數void select_sort(int,int);/*選擇排序*/（5）將數據調整為堆的函數void adjust(int,int);/*將數據調整為堆樹*/3.4主要函數聲明插入排序插入排序的主要算法思想是將一個記錄插入到已排好的有序表中，從而得到一個新的、記錄數增1的有序表。void in

9、sertion_sort(int data,int size)/*插入排序*/int base,compare,temp,i,j=0; for(base=1;base<size;base+)/*當數據小于第一個時，則插于前方，否則與后面數據對比找出插入位置*/ temp=database; compare=base; j+; while(compare>0 && datacompare-1>temp) datacompare=datacompare-1; compare-; datacompare=temp; printf("第%d 趟排序:&quo

10、t; ,j); for(i=0;i<size;i+) printf("%d ",datai); printf("n"); printf("n最終排序結果:");for(i=0;i<size;i+) printf("%d ",datai);printf("n");希爾排序希爾排序的基本思想是先將整個待排記錄列分割成若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。void shell_sort(int data,int size)/*希

11、爾排序*/int i,j,k,incr,temp,num=0;incr=size/2;printf("n");while(incr>0)for(i=incr+1;i<size;i+)j=i-incr;while(j>0) if(dataj>dataj+incr)/*比較每部分的數據大小順序不對則交換*/ temp=dataj; dataj=dataj+incr; dataj+incr=temp; j=j-incr;else j=0;num+;printf("n第%d 趟排序:",num);for(k=1;k<size;k+)

12、 printf("%d ",datak);incr=incr/2;printf("n最終排序結果：");for(i=1;i<size;i+) printf("%d ",datai);printf("n");冒泡排序冒泡排序首先將第一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序則將兩個記錄交換，然后比較第二個記錄和第三個記錄的關鍵字，依次類推。void bubble_sort(int data,int size)/*冒泡排序*/int i,j,flag,k,temp,num=0; for(i=0;i&l

13、t;size-1;i+) flag=0; for(j=0;j<size-1;j+)/*讓數據兩兩比較，將小的置于前*/ if(dataj>dataj+1) flag=1; temp=dataj; dataj=dataj+1; dataj+1=temp; num+; printf("n第%d趟排序：",num); for(k=0;k<size;k+) printf("%d ",datak); printf("n"); printf("n最終排序結果：");for(i=0;i<size;i+)

14、printf("%d ",datai); printf("n"); if(flag!=1) break; 選擇排序選擇排序的基本思想是：每一趟在n-i+1(i=1,2,n-1)個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。void select_sort(int data,int size)/*選擇排序*/int base,compare,min,temp,i,num=0; for(base=0;base<size-1;base+)/*將目前數據與后面數據中最小的對調*/ min=base; for(compare=base+1;compa

15、re<size;compare+) if(datacompare<datamin) min=compare; temp=datamin; datamin=database; database=temp; num+; printf("第%d趟排序：",num); for(i=0;i<size;i+) printf("%d ",datai); printf("n"); printf("n最終排序結果：");for(i=0;i<size;i+) printf("%d ",dat

16、ai); printf("n");3.5主要變量說明Int data :整型數組，用于儲存序列 Int size:整型變量，用于記錄序列長度 Int temp:整型變量，用于交換元素 Int m,n,k,i,j,num:一般整型變量四程序源代碼*include<stdio.h> void insertion_sort(int,int);/*插入排序*/void shell_sort(int,int);/*希爾排序*/void bubble_sort(int,int);/*冒泡排序*/void select_sort(int,int);/*選擇排序*/void a

17、djust(int,int);/*將數據調整為堆樹*/void insertion_sort(int data,int size)/*插入排序*/int base,compare,temp,i,j=0; for(base=1;base<size;base+)/*當數據小于第一個時，則插于前方，否則與后面數據對比找出插入位置*/ temp=database; compare=base; j+; while(compare>0 && datacompare-1>temp) datacompare=datacompare-1; compare-; datacompa

18、re=temp; printf("第%d 趟排序:" ,j); for(i=0;i<size;i+) printf("%d ",datai); printf("n"); printf("n最終排序結果:"); for(i=0;i<size;i+) printf("%d ",datai); printf("n");void shell_sort(int data,int size)/*希爾排序*/ int i,j,k,incr,temp,num=0; incr=si

19、ze/2; printf("n"); while(incr>0) for(i=incr+1;i<size;i+)j=i-incr; while(j>0) if(dataj>dataj+incr)/*比較每部分的數據大小順序不對則交換*/ temp=dataj; dataj=dataj+incr; dataj+incr=temp; j=j-incr; else j=0; num+; printf("n第%d 趟排序:",num); for(k=1;k<size;k+) printf("%d ",datak)

20、; incr=incr/2; printf("n最終排序結果："); for(i=1;i<size;i+) printf("%d ",datai); printf("n");void bubble_sort(int data,int size)/*冒泡排序*/int i,j,flag,k,temp,num=0; for(i=0;i<size-1;i+) flag=0; for(j=0;j<size-1;j+)/*讓數據兩兩比較，將小的置于前*/ if(dataj>dataj+1) flag=1; temp=da

21、taj; dataj=dataj+1; dataj+1=temp; num+; printf("n第%d趟排序：",num); for(k=0;k<size;k+) printf("%d ",datak); printf("n"); printf("n最終排序結果："); for(i=0;i<size;i+) printf("%d ",datai); printf("n"); if(flag!=1) break; void select_sort(int data

22、,int size)/*選擇排序*/int base,compare,min,temp,i,num=0; for(base=0;base<size-1;base+)/*將目前數據與后面數據中最小的對調*/ min=base; for(compare=base+1;compare<size;compare+) if(datacompare<datamin) min=compare; temp=datamin; datamin=database; database=temp; num+; printf("第%d趟排序：",num); for(i=0;i<

23、size;i+) printf("%d ",datai); printf("n"); printf("n最終排序結果："); for(i=0;i<size;i+) printf("%d ",datai); printf("n");void adjust(int i,int n)/*將數據調整為堆樹*/int data20,j,k,done=0; k=datai; j=2*i; while(j<=n)&&(done=0) if(j<n)&&(dat

24、aj<dataj+1)j+; if(k>=dataj)done=1; else dataj/2=dataj; j=2*j; dataj/2=k;void main()int data20; int size=0,m=0,i,j,num,k,temp,n=0; printf("n請輸入初始關鍵字（輸入0結束）:n"); do scanf("%d",&datasize); m+; while(datasize+!=0); printf("你輸入的初始關鍵字為：");for(j=0;j<m-1;j+)printf(

25、"%d ",dataj);printf("n排序方法：n");printf("n1、插入排序n");printf("n2、希爾排序n");printf("n3、冒泡排序n");printf("n4、選擇排序n");printf("n5、堆排序n");printf("n請選擇排序方法：n");scanf("%d",&num);switch(num)case 1: printf("*插入排序*n&quo

26、t;); for(i=0;i<50;i+)printf("-");printf("n"); insertion_sort(data,-size); for(i=0;i<50;i+)printf("-");printf("n"); break;case 2:printf("*希爾排序*n");for(m=0;m<50;m+)printf("-"); shell_sort(data,-size);for(i=0;i<50;i+)printf("-

27、");printf("n"); break;case 3:printf("*冒泡排序*n");for(i=0;i<50;i+)printf("-");printf("n"); bubble_sort(data,-size); for(i=0;i<50;i+)printf("-");printf("n"); break;case 4:printf("*選擇排序*n");for(i=0;i<50;i+)printf("-&

28、quot;);printf("n"); select_sort(data,-size); for(i=0;i<50;i+)printf("-");printf("n"); break;case 5:size=size-1;printf("*堆排序*n");for(i=0;i<50;i+)printf("-");for(i=size/2;i>0;i-) adjust(i,size);printf("n堆：");for(k=1;k<size;k+)printf("%d ",datak);for(i=size-2;i>0;i-)temp=datai+1; datai+1=data1; data1=temp;/*將樹根和最后的節點交換*/ adjust(1,i);/*再重新調整為堆樹*/ n+; printf("n第%d趟排序：",n); for(k=1;k<size;k+) printf("%d ",