軟件算法綜合設(shè)計(jì)報(bào)告書-排序

軟件算法綜合設(shè)計(jì)說明書軟件算法綜合設(shè)計(jì)說明書排序綜合學(xué)院：信息與電氣工程學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：10-02姓名：學(xué)號(hào)：1002102142012.6.28軟件算法綜合設(shè)計(jì)說明書一、課程設(shè)計(jì)目的1、初步具備根據(jù)應(yīng)用需求選擇合理數(shù)據(jù)結(jié)構(gòu)并進(jìn)行算法設(shè)計(jì)的能力；2、進(jìn)一步提升C語言的應(yīng)用能力；3、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；4、提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；5、訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)；6、提升文檔寫作能力二、課程設(shè)計(jì)題目及要求排序綜合（限3人完成）利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（20000以上），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。要求：至少采用三種方法實(shí)現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法。三、題目分析冒泡排序：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對(duì)數(shù)開始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過程，直至最終完成排序。四、大體設(shè)計(jì)五、設(shè)計(jì)詳細(xì)源代碼1.冒泡排序#include<iostream>#include<time.h>usingnamespacestd;#defineN20000voidmain(){ inta[N]; inti,j,temp; srand(time(0)); for(i=0;i<N;i++) { a[i]=rand(); } intflag=1; for(i=0;i<N-1&&flag==1;i++) { flag=0; for(j=0;j<N-i-1;j++) { if(a[j+1]<a[j]) { temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; flag=1; } } } for(i=0;i<N;i++) { printf("%d",a[i]); }}2、統(tǒng)計(jì)性能#include<stdio.h>#include<stdlib.h>#include<time.h>#defineN10000voidmain(){inti,j,k,n;intn1,t;inta[N],b[N];FILE*fp;clock_tstart,finish;inttime1,time2,time3;printf("輸入要產(chǎn)生的隨機(jī)數(shù)個(gè)數(shù):");scanf("%d",&n);srand((unsigned)time(NULL));for(i=0;i<n;i++)a[i]=rand();for(i=0;i<n;i++)b[i]=a[i];printf("**************************\n");printf("\t插入排序\n");printf("**************************\n");start=clock();for(i=1;i<n;i++){t=b[i];for(j=i-1;j>=0&&t<b[j];j--)b[j+1]=b[j];b[j+1]=t;}finish=clock();time1=finish-start;printf("插入排序耗時(shí)%d毫秒!\n\n\n",time1);fp=fopen("output1.txt","w");for(i=0;i<n;i++)fprintf(fp,"%d",b[i]);fclose(fp);for(i=0;i<n;i++)b[i]=a[i];printf("**************************\n");printf("\t選擇排序\n");printf("**************************\n");start=clock();for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(b[k]>b[j])k=j;t=b[i];b[i]=b[k];b[k]=t;}finish=clock();time2=finish-start;printf("選擇排序耗時(shí)%d毫秒!\n\n\n",time2);fp=fopen("output2.txt","w");for(i=0;i<n;i++)fprintf(fp,"%d",b[i]);fclose(fp);for(i=0;i<n;i++)b[i]=a[i];printf("**************************\n");printf("\t冒泡排序\n");printf("**************************\n");start=clock();n1=n-1;while(n1>0){j=0;for(i=0;i<n1;i++)if(b[i]>b[i+1]){t=b[i];b[i]=b[i+1];b[i+1]=t;j=i;}n1=j;}finish=clock();time3=finish-start;printf("冒泡排序耗時(shí)%d毫秒!\n\n\n",time3);fp=fopen("output3.txt","w");for(i=0;i<n;i++)fprintf(fp,"%d",b[i]);fclose(fp);}六、程序的調(diào)試與運(yùn)行結(jié)果說明運(yùn)行結(jié)果1、使用冒泡程序完成題目要求運(yùn)行結(jié)果如圖1：圖1運(yùn)行結(jié)果2、三鐘排序方法耗時(shí)結(jié)果如圖2：圖2結(jié)果說明：插入排序和選擇排序耗費(fèi)時(shí)間較少七、課程設(shè)計(jì)總結(jié)通過這次課程設(shè)計(jì)的學(xué)習(xí)讓我學(xué)會(huì)了許多，加深了對(duì)數(shù)據(jù)結(jié)構(gòu)排序算法的認(rèn)識(shí)。在這次課程設(shè)計(jì)中，我們完成了每種排序算法。排序算法選了三個(gè)，包括：插入排序、選擇排序、冒泡排序。同時(shí)也實(shí)現(xiàn)了隨機(jī)數(shù)的生成。并把排序后的結(jié)果保存在不同的文件中。雖然在算法完成的過程中從網(wǎng)上參考了一些資料，但對(duì)這次課程設(shè)計(jì)的成果還是非常滿意的。這次的課程設(shè)計(jì)還有很多不足之處，如鏈表存儲(chǔ)結(jié)構(gòu)中的堆排序算法，當(dāng)排序個(gè)數(shù)過多時(shí)，就會(huì)等待很長時(shí)間。可能時(shí)調(diào)用的函數(shù)過多的原因造成的，但排序是正確的。用指針代替函數(shù)的調(diào)用。還有就是隨機(jī)數(shù)不能隨時(shí)更改，只能設(shè)定一次。鏈表歸并算法不是對(duì)鏈表直接操作，而是將鏈表中的元素放入數(shù)組中進(jìn)行排序，我想了很多方法都沒有想出對(duì)鏈表的直接操作的算法。由于時(shí)間限制，只在課程設(shè)計(jì)快結(jié)束時(shí)完成了產(chǎn)生隨機(jī)文件這部分，我想以后有時(shí)間再來完成它。同時(shí)在完成這個(gè)課程設(shè)計(jì)后，我也學(xué)到了很多知識(shí)，并能訓(xùn)練的掌握他們了。首先學(xué)會(huì)了隨機(jī)數(shù)的產(chǎn)生。熟練的撐握了C語言的文件讀寫操作。撐握了每種排序算法的基本思想，并從同學(xué)那里學(xué)會(huì)了編寫程序的一般步驟：思考問題，寫出解決方案