軟件算法綜合設計報告書-排序

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