數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)排序算法集成

1、xx大學(xué)本科生課程設(shè)計(jì)論文題 目：排序算法集成學(xué)生姓名：學(xué) 號(hào)：專(zhuān) 業(yè)：計(jì)算機(jī)班 級(jí)： 指導(dǎo)教師： 2013年 5月20日xx大學(xué)課程設(shè)計(jì)任務(wù)書(shū)課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目排序算法集成指導(dǎo)教師時(shí)間一、教學(xué)要求1. 掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力2. 初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能3. 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力4. 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)二、設(shè)計(jì)資料及參數(shù)每個(gè)學(xué)生在教師提供的課程設(shè)計(jì)題目中任意選擇一題，獨(dú)立完成，題目選定后

2、不可更換。排序算法集成定義動(dòng)態(tài)數(shù)組類(lèi)（或類(lèi)模板）以表示待排序數(shù)據(jù)，在此基礎(chǔ)上實(shí)現(xiàn)多種排序算法。要求設(shè)計(jì)函數(shù)模板來(lái)實(shí)現(xiàn)下列排序算法：v 直接插入排序v 冒泡排序v 簡(jiǎn)單選擇排序v 希爾排序v 快速排序v 堆排序 并設(shè)計(jì)主函數(shù)測(cè)試動(dòng)態(tài)數(shù)組類(lèi)（或類(lèi)模板），測(cè)試各排序算法的函數(shù)模板。三、設(shè)計(jì)要求及成果1. 分析課程設(shè)計(jì)題目的要求2. 寫(xiě)出詳細(xì)設(shè)計(jì)說(shuō)明3. 編寫(xiě)程序代碼，調(diào)試程序使其能正確運(yùn)行4. 設(shè)計(jì)完成的軟件要便于操作和使用5. 設(shè)計(jì)完成后提交課程設(shè)計(jì)報(bào)告四、進(jìn)度安排資料查閱與討論（1天）系統(tǒng)分析（2天）系統(tǒng)的開(kāi)發(fā)與測(cè)試（5天）編寫(xiě)課程設(shè)計(jì)說(shuō)明書(shū)和驗(yàn)收（2天）五、評(píng)分標(biāo)準(zhǔn)1. 根據(jù)平時(shí)上機(jī)考勤、表現(xiàn)

3、和進(jìn)度，教師將每天點(diǎn)名和檢查2. 根據(jù)課程設(shè)計(jì)完成情況，必須有可運(yùn)行的軟件。3. 根據(jù)課程設(shè)計(jì)報(bào)告的質(zhì)量，如有雷同，則所有雷同的所有人均判為不及格。4. 根據(jù)答辯的情況，應(yīng)能夠以清晰的思路和準(zhǔn)確、簡(jiǎn)練的語(yǔ)言敘述自己的設(shè)計(jì)和回答教師的提問(wèn)六、建議參考資料1數(shù)據(jù)結(jié)構(gòu) （C語(yǔ)言版）嚴(yán)蔚敏、吳偉民 主編 清華大學(xué)出版社 2004.112數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)案例精編（用C/C+描述），李建學(xué) 等 編著，清華大學(xué)出版社 2007.23.數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蠓椒ㄅcC+語(yǔ)言描述，殷人昆 主編， 清華大學(xué)出版社 2007.6目 錄目 錄3引言4一算法的設(shè)計(jì)思想4二算法的流程圖4三算法的設(shè)計(jì)與分析53.1建

4、立數(shù)組53.2 算法思想53.3主要函數(shù)63.4主要函數(shù)聲明63.5 主要變量說(shuō)明10四程序源代碼11五運(yùn)行結(jié)果與分析（測(cè)試）18六總結(jié)（收獲與體會(huì)）20七參考文獻(xiàn)21引 言本課程設(shè)計(jì)主要解決幾種不同排序方法以及在各種不同排序的過(guò)程中某一趟的具體排序結(jié)果。通過(guò)觀察各種排序的具體排序過(guò)程，加深對(duì)不同排序方法的認(rèn)識(shí)，加深對(duì)不同排序算法的掌握。一算法設(shè)計(jì)的思想數(shù)據(jù)結(jié)構(gòu)是與數(shù)據(jù)相關(guān)的一門(mén)重要學(xué)科，不論是想通過(guò)升學(xué)考試還是想把程序編得有水平，都要對(duì)這門(mén)學(xué)科下一點(diǎn)功夫才行。而課程設(shè)計(jì)是讓我們更好的掌握這門(mén)學(xué)科的重要方式。排序是計(jì)算機(jī)程序中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列重新排列

5、成一個(gè)按關(guān)鍵字有序的序列 。而內(nèi)部排序中包括各種不同的排序，本課程設(shè)計(jì)主要討論的是插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序。 完成這幾種排序最主要的就是弄好不同排序的算法，只有深刻的認(rèn)識(shí)了這不同排序的算法，才能了解不同排序的優(yōu)點(diǎn)與缺點(diǎn)。通過(guò)對(duì)不同排序算法的分析，了解它們的優(yōu)劣特點(diǎn)。據(jù)對(duì)題目的分析，首先要根據(jù)插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序的不同算法，寫(xiě)出實(shí)現(xiàn)各個(gè)排序算法的函數(shù)。然后通過(guò)在主函數(shù)中對(duì)不同排序的子函數(shù)的調(diào)用來(lái)實(shí)現(xiàn)對(duì)某個(gè)序列的具體排序。內(nèi)部排序的方法很多，但就其全面性而言，很難提出一種被認(rèn)為是最好的方法，每一種方法都有各自的優(yōu)缺點(diǎn)，適合不同的環(huán)

6、境。通常，在排序的過(guò)程中需進(jìn)行兩種基本操作：（1）比較兩個(gè)關(guān)鍵字的大??；（2）將記錄從一個(gè)位置移動(dòng)至另一位置。前一個(gè)操作對(duì)大多數(shù)排序方法來(lái)說(shuō)都是必要的，而后一個(gè)操作可以通過(guò)改變記錄的存儲(chǔ)方式來(lái)予以避免。二算法的流程圖如圖2.1建立數(shù)組設(shè)計(jì)main函數(shù)建立各排序函數(shù)結(jié)束開(kāi)始圖2.1 主要設(shè)計(jì)思想流程圖三算法的設(shè)計(jì)與分析3.1建立數(shù)組在程序中建立一個(gè)數(shù)組data ，用于存儲(chǔ)程序運(yùn)行中的數(shù)據(jù)。3.2算法思想（1）插入排序 插入排序的主要算法思想是將一個(gè)記錄插入到已排好的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。（2）希爾排序 希爾排序的基本思想是先將整個(gè)待排記錄列分割成若干子序列分別進(jìn)行直接插

7、入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。（3）冒泡排序函數(shù) 冒泡排序首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序則將兩個(gè)記錄交換，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字，依次類(lèi)推。（4）選擇排序函數(shù) 選擇排序的基本思想是：每一趟在n-i+1(i=1,2,n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。（5）堆排序 先將一個(gè)序列進(jìn)行建堆，然后將大頂堆的第一個(gè)元素和最后一個(gè)元素對(duì)換（或?qū)⑿№敹训淖詈笠粋€(gè)元素和第一個(gè)元素對(duì)換），再對(duì)除最后一個(gè)元素的序列進(jìn)行求大頂堆（或?qū)Τ谝粋€(gè)元素的序列進(jìn)行求小頂堆），依次類(lèi)推。 3.3 主要函數(shù)（

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

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

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

11、,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)/*比較每部分的數(shù)據(jù)大小順序不對(duì)則交換*/ 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(&quo

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

13、 flag=0; for(j=0;j<size-1;j+)/*讓數(shù)據(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最終排序結(jié)果：");for(i=0;i<size;i+) printf("

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

15、ompare+) 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最終排序結(jié)果：");for(i=0;i<size;i+) printf("%d ",datai); printf(

16、"n");3.5主要變量說(shuō)明 Int data :整型數(shù)組，用于儲(chǔ)存序列 Int size:整型變量，用于記錄序列長(zhǎng)度 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 adjust(int,i

17、nt);/*將數(shù)據(jù)調(diào)整為堆樹(shù)*/void insertion_sort(int data,int size)/*插入排序*/int base,compare,temp,i,j=0; for(base=1;base<size;base+)/*當(dāng)數(shù)據(jù)小于第一個(gè)時(shí)，則插于前方，否則與后面數(shù)據(jù)對(duì)比找出插入位置*/ temp=database; compare=base; j+; while(compare>0 && datacompare-1>temp) datacompare=datacompare-1; compare-; datacompare=temp; pr

18、intf("第%d 趟排序:" ,j); for(i=0;i<size;i+) printf("%d ",datai); printf("n"); printf("n最終排序結(jié)果:"); 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=size/2; print

19、f("n"); while(incr>0) for(i=incr+1;i<size;i+)j=i-incr; while(j>0) if(dataj>dataj+incr)/*比較每部分的數(shù)據(jù)大小順序不對(duì)則交換*/ 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); incr=incr

20、/2; printf("n最終排序結(jié)果："); 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+)/*讓數(shù)據(jù)兩兩比較，將小的置于前*/ if(dataj>dataj+1) flag=1; temp=dataj; dataj=

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

22、*選擇排序*/int base,compare,min,temp,i,num=0; for(base=0;base<size-1;base+)/*將目前數(shù)據(jù)與后面數(shù)據(jù)中最小的對(duì)調(diào)*/ 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<size;i+) pr

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

24、+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請(qǐng)輸入初始關(guān)鍵字（輸入0結(jié)束）:n"); do scanf("%d",&datasize); m+; while(datasize+!=0); printf("你輸入的初始關(guān)鍵字為：");for(j=0;j<m-1;j+)printf("%d &q

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

26、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("-");pri

27、ntf("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("-");prin

28、tf("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;/*將樹(shù)根和最后的節(jié)點(diǎn)交換*/ adjust(1,i);/*再重新調(diào)整為堆樹(shù)*/ n+; printf("n第%d趟排序：",n); for(k=1;k<size;k+) printf("%d "