數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告---各種內(nèi)排序性能比較

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：20 大?。?99.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告---各種內(nèi)排序性能比較_第1頁

已閱讀1頁，還剩19頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告　　題目：各種內(nèi)排序性能比較 　　學生姓名： 　　學號： 　　班級： 　　指導教師：

2、 　　2011-6-13　　目錄　　需求分析說明............................2　　1.1 所需完成的任務(wù)及要求

3、　1.2 程序?qū)崿F(xiàn)的功能　　總體設(shè)計................................3　　2.1 總體設(shè)計說明　　2.2 總體流程圖　　2.3 各主程序詳細流程圖 　　詳細設(shè)

4、計................................7　　3.1 使用的算法思想　　3.2 各個算法的效率簡析　　實現(xiàn)部分................................8　　4.1程序算法的代碼

5、程序測試...............................15　　5.1 程序運行的主界面　　5.2 各算法運行界面　　總結(jié)...................................18　　需求分析說明<

6、/p>　　排序是數(shù)據(jù)處理中經(jīng)常遇到的一種重要操作。然而排序的算法有很多，各有其優(yōu)缺點和使用場合。本程序的設(shè)計的主要目的是通過比較各種內(nèi)部排序（包括：插入法排序、起泡法、選擇法、快速法、合并法排序）的時間復(fù)雜度，即元素比較次數(shù)和移動次數(shù)，來分析各種算法優(yōu)缺點和適合排列何種序列。達到在實際應(yīng)用中選擇合適的方法消耗最短的時間完成排序。　　所需完成的任務(wù)及要求</p&g

7、t;　　任務(wù)：　　用程序?qū)崿F(xiàn)插入法排序、起泡法、選擇法、快速法、合并法排序；　　輸入的數(shù)據(jù)形式為任何一個正整數(shù)，大小不限。　　要求：排序后的數(shù)組是從小到大的；　　程序?qū)崿F(xiàn)的功能

8、;　　使用隨機函數(shù)實現(xiàn)數(shù)組初始化，生成多組元素個數(shù)不同的數(shù)組；　　用列表打印出每種排序下的各趟排序結(jié)果；　　打印使用各種排序算法以后元素比較和交換的次數(shù)；　　設(shè)計合理的打印列表來打印。　　總體設(shè)計（從總體上說明該題目的框架，用文字

9、和圖表說明）　　2.1 總體設(shè)計說明　　采用插入氣泡，選擇，快速，合并的方法實現(xiàn)各種排序算法，并且在實現(xiàn)過程中插入適當變量來實現(xiàn)計數(shù)元素交換次數(shù)和比較次數(shù)的統(tǒng)計。對于每一趟比較之后元素順序以及最后的結(jié)果使用單獨的函數(shù)來實現(xiàn)，形成單獨的一個模塊；　　2.2 總體流程圖</

10、p>　　2.3 各主程序詳細流程圖 　?、僦骱瘮?shù)流程圖：　　②插入法函數(shù)流程圖　?、燮鹋莘ê瘮?shù)流程圖　　④選擇法函數(shù)流程圖：<

11、;/p>　　詳細設(shè)計　　3.1 使用的算法思想　　對主界面的menu菜單，在主函數(shù)里面用switch語句調(diào)用各個模塊的功能調(diào)用；　　在插入法時，其算法思想是：將第一個元素作為單獨的一個數(shù)組獨立出來，對剩下的元素，逐個與前面的數(shù)組從后往前進行比較，一

12、旦發(fā)現(xiàn)當前的元素大于或是等于前面已經(jīng)排序好的元素中某個元素，則在這個元素之后插入即可；　　在起泡法時，其算法思想是：將待排序的數(shù)組從后往前，依次比較相鄰的兩個元素，如果發(fā)現(xiàn)逆序則交換序列，使得數(shù)值、比較小的元素逐漸往前排列，在這個算法時要用flag作為標記位，用來判斷元素是否交換，用以減少不必要的交換次數(shù)；　　對于選擇法，其排序思想是:從第一個元素開始

13、，并且標記當前元素的位置，比較后面所有的元素，找到其中最小的元素，也標記當前元素的位置，然后把兩個標記位的元素進行交換，前面的標記位不斷地向后移動，直到最后一個元素的位置，則排序完成；　　對于快速法，其算法思想是：一般取數(shù)組中的第一個元素為基準，通過一趟排序?qū)⒋判蛟胤譃樽笥覂蓚€子序列，左子序列的所有元素都小于或等于右子序列的所有元素，然后將左右兩個序列按照與此相同的原理進行排序，直至整個序列

14、有序為止，排序完成。　　對于合并法，其排序思想是：將兩個有序子區(qū)間合并成一個有序子區(qū)間，一次合并完成后，有序子區(qū)間的數(shù)目會減少一半，并且區(qū)間長度增加一倍，當區(qū)間長度從1增至n時，則排序完成。　　3.2 各個算法的效率簡析　　插入排序需要一個輔助空間用于元素交換，時間復(fù)雜度為O（n2）；&l

15、t;p>　　起泡排序算法的時間復(fù)雜度為O（n2）；　　選擇排序算法的時間復(fù)雜度為O（n2）數(shù)量級，并且當所需排序的元素過多是，通常比直接插入排序的執(zhí)行速度要快一些；　　僅僅討論元素比較次數(shù)來討論快速法的時間復(fù)雜度，理論上，快速排序的時間復(fù)雜度為O（nlog2n）最壞時間復(fù)雜度為O（n2）?？焖倥判蛩加玫妮o助空間為棧的深度，故最好空間復(fù)雜度為O（l

16、og2n），最壞為O（n）；　　合并排序的時間復(fù)雜度為O（nlog2n）。用合并排序進行排序時，需要利用與待排序數(shù)組相同的輔助數(shù)組作為臨時單元，故該排序方法的空間復(fù)雜度為O（n）,比前面介紹的其他排序方法占用的空間都大。　　4、實現(xiàn)部分　　4.1 各個核心算法的代碼：<

17、;/p>　　#include <iostream>　　#include <cstdlib>　　#include <ctime>　　using namespace std;　　const int M=100;&

18、lt;/p>　　int A=0,B=0;//用于快速排序中計算元素比較的次數(shù)和交換的次數(shù)　　int C=0,D=0,K=0;//用于合并排序中計算元素比較的次數(shù)和交換的次數(shù)　　void showout(int r[], int n)　　{</

19、p>　　for(int i=0;i<n;i++)　　{　　cout.width(5);　　cout<<r[i];　　}<

20、p>　　cout<<endl<<endl;　　}　　void insertsort(int r[],int n) //直接插入法排序　　//待排序元素用一個數(shù)組r表示，數(shù)組有n個元素

21、　　{　　int a=0,b=0,k=1;//a表示元素比較的次數(shù)，b表示元素交換的次數(shù),k表示趟數(shù)　　cout<<"插入排序的每一次的結(jié)果如下："<<endl<<endl;　　cout<<"初始狀態(tài):";

22、　　showout(r,n);　　for(int i=1;i<n;i++) //i表示插入次數(shù)，共進行n-1次插入　　{　　int temp=r[i]; //把待排序元素賦給temp

23、　int j=i-1;　　while((j>=0)&&(temp<r[j]))　　{　　a++;　　r[j+1]=r[j];j--; //順序比較和移動</p&

24、gt;　　}　　a++;　　r[j+1]=temp;　　b++;　　cout<<"第"<<k

25、<<"趟: ";　　k++;　　showout(r,n);　　}　　cout<<"元素比較的次數(shù)為"<<a<&l

26、t;"次\n";　　cout<<"元素交換的次數(shù)為"<<b<<"次\n";　　}　　void bubblesort(int r[],int n) //冒泡排序

27、　　{　　int a=0,b=0,k=1,flag=1; //當flag=0時停止排序(flag用于判斷元素是否進行過交換)　　cout<<"冒泡排序的每一次的結(jié)果如下："<<endl<<endl;

28、　cout<<"初始狀態(tài):";　　showout(r,n);　　for(int i=1;i<n;i++) //i表示趟數(shù)，最多n-1趟　　{　　flag=0; //開始時元素未交換</p&g

29、t;　　for(int j=n-1;j>=i;j--)　　{　　a++;　　if(r[j]<r[j-1])　　{</p

30、>　　//發(fā)生逆序　　int t=r[j];　　r[j]=r[j-1]; //元素后移　　r[j-1]=t;flag=1; //交換，并標記發(fā)生了交換　　b++;&l

31、t;/p>　　}　　flag=1;　　if(flag==0)break;　　}　　cout<<"第"

32、;<<k<<"趟: ";　　k++;　　showout(r,n);　　}　　cout<<"元素比較的次數(shù)為"<&

33、lt;a<<"次\n";　　cout<<"元素交換的次數(shù)為"<<b<<"次\n";　　}　　void selectsort(int r[],int n)//直接選擇排

34、序　　{　　int i,j,m,t,a=0,b=0,k=1;　　cout<<"選擇排序的每一次的結(jié)果如下："<<endl<<endl;　　cout<<"初始

35、狀態(tài):";　　showout(r,n);　　for(i=0;i<n-1;i++)　　{　　m=i;　　for(j=i+1;j<n;j

36、++)　　if(r[j]<r[m])　　{　　a++;　　m=j;　　}

37、;　　if(m!=i)　　{　　t=r[i];　　r[i]=r[m];　　r[m]=t;</

38、b>　　b++;　　}　　cout<<"第"<<k<<"趟: ";　　k++;</b&g

39、t;　　showout(r,n);　　}　　cout<<"元素比較的次數(shù)為"<<a<<"次"<<endl;　　cout<<"

40、元素交換的次數(shù)為"<<b<<"次"<<endl;　　}　　void quicksort(int r[],int left,int right,int n)//快速排序,因為涉及遞歸調(diào)用，所以使用全局變量，并且結(jié)果在main函數(shù)中實現(xiàn)

41、　　{　　int i=left,j=right,k=1;　　int temp=r[i];　　while(i<j)　　{　　wh

42、ile((r[j]>temp)&&(j>i))//同時滿足兩個條件時才會執(zhí)行j--,即向前移動j,并且如果沒有發(fā)現(xiàn)r[j]中沒有比temp小的則當i=j時停止　　{　　A++;//A用于快速排序中計算元素比較的次數(shù)　　j=j-1;

43、　　}　　if(j>i)//當這種情況下一定是因為r[j]中存在比temp小的值　　{　　r[i]=r[j];

44、　　i=i+1;　　B++;//B用于快速排序中計算元素交換的次數(shù)　　cout<<"第"<<K<<"趟: ";　　K++;　　sho

45、wout(r,n);　　}　　while((r[j]<=temp)&&(j>i))　　{　　A++;<

46、;p>　　i=i+1;　　}　　if(i<j)　　{　　B++;<

47、;/p>　　r[j]=r[i];　　j=j-1;　　}　　} 　　r[i]=temp; //一次劃分得到基準值的正確位置</

48、p>　　if(left<i-1)　　quicksort(r,left,i-1,n); //遞歸調(diào)用左子區(qū)間　　if(i+1<right)　　quicksort(r,i+1,right,n); //遞歸調(diào)用右子區(qū)間

49、　}　　void merge( int r[],int a[],int s,int m,int t)//將兩個子區(qū)間人r[s]~r[m]和r[m+1]~r[t]合并，結(jié)果存入a　　{　　int i,j,temp;&

50、lt;b>　　i=s;　　j=m+1;　　while((i<=m)&&(j<=t))　　{　　C++;&

51、lt;/p>　　if(r[i]>=r[j])　　{　　D++;　　temp=r[j];　　for(int k=j-1;k>=i;k--)

52、　　{　　r[k+1]=r[k];　　}　　r[i]=temp;　　j++;

53、　　}　　else　　{　　i++;　　}

54、;　　}　　for(int l=s;l<=t;l++)　　a[l]=r[l];　　}　　void mergepass(int r[],int a[],int n,int c)<p

55、>　　//對r數(shù)組做一趟歸并，結(jié)果存入a數(shù)組中，n為元素個數(shù)，c為區(qū)間長度　　{　　int i,j;　　i=0;　　while(i+2*c-1<=

56、n-1)　　{//長度均為c的兩個區(qū)間合并成一個區(qū)間　　merge(r,a,i,i+c-1,i+2*c-1);　　i+=2*c;　　}

57、if(i+c-1<n) //長度不等的兩個區(qū)間合并成一個區(qū)間　　merge(r,a,i,i+c-1,n-1);　　else //僅剩一個區(qū)間時直接復(fù)制到a中　　for(j=i;j<=n-1;j++)

58、;　　a[j]=r[j];　　}　　void mergesort(int r[],int n)//二路歸并　　{　　int c=1,i=0,k=1;&

59、lt;p>　　int a[M];　　cout<<"二路歸并排序的每一次的結(jié)果如下："<<endl<<endl;　　cout<<"初始狀態(tài):";　　showout(r,n);</

60、p>　　while(c<n)　　{　　mergepass(r,a,n,c);　　i=i+1;　　cout<<"第"<<

61、k<<"趟: ";　　k++;　　showout(r,n);　　c*=2;　　mergepass(a,r,n,c);&l

62、t;b>　　i=i+1;　　cout<<"第"<<k<<"趟: ";　　k++;　　showout(r,n);

63、　c*=2;　　}　　}　　int suiji()　　{　　int m;<

64、;/b>　　srand((unsigned)time(NULL));　　m=rand()%5+5;　　return m;　　}　　void menu

65、()　　{　　cout<<" ************************** "<<endl; 　　cout<<" ******

66、**各種內(nèi) 排序性能比較******** "<<endl; 　　cout<<"************************************************************"<<endl; 　　cout<<"

67、 ------------------------------------------------------------"<<endl; 　　cout<<" * 請選擇您要進行的操作 * "<<endl;　　cout

68、<<" (1). 插入法 "<<endl;　　cout<<" (2). 冒泡法 "<<endl;　　cout

69、<<" (3). 選擇法 "<<endl; 　　cout<<" (4). 快速法 "<<endl;

70、　　cout<<" (5). 合并法 "<<endl; 　　cout<<" (0). 退出 "<<endl; &

71、lt;p>　　cout<<" ------------------------------------------------------------"<<endl; 　　cout<<" ************************************************************&quo

72、t;<<endl; 　　cout<<endl;　　cout<<"請輸入你需要的排序方法(輸入在0~5之間的數(shù)字)"<<endl;　　}　　int main()<

73、/p>　　{　　int k;//因為使用地址傳遞方式，所以不能使用同一個數(shù)組，只能把同樣的內(nèi)容放在不同的數(shù)組里面　　int* R =new int [20];　　int* T=new int [20];

74、k=suiji();　　cout<<"數(shù)組下標范圍是0~"<<k-1<<endl;　　srand((unsigned)time(NULL));　　cout<<"以下是隨機生成的數(shù)組:"<<endl;</p&g

75、t;　　for(int i=0;i<k;i++)　　T[i]=rand()%500;　　showout(T,k);　　do　　{

76、;　　for(int i=0;i<k;i++)//每次執(zhí)行do...while語句時，先將T里面的值賦給R，保證每次排序的數(shù)組是隨機的　　R[i]=T[i];　　menu();　　int select;　　cin>>

77、select;　　switch (select)　　{ 　　case 0:　　delete [] R;　　delete [] T;

78、　　exit(0);　　case 1:　　insertsort(R,k);//插入排序 　　break; 　　case 2:<

79、/b>　　bubblesort(R,k); //冒泡排序 　　break;　　case 3:　　selectsort(R,k); //選擇排序

80、;　　break;　　case 4:　　{　　cout<<"快速排序的每一次的結(jié)果如下："<<endl<<endl;<

81、;/p>　　if(A!=0)　　A=0;　　if(B!=0)　　B=0;　　quicksor

82、t(R,0,k-1,k); //快速排序　　cout<<"元素比較的次數(shù)為"<<A<<"次\n";　　cout<<"元素交換的次數(shù)為"<<B<<"次\n"; <p

83、>　　break; 　　}　　case 5:　　{　　if(C!=0)<p&

84、gt;　　C=0;　　if(D!=0)　　D=0;　　mergesort(R,k); //合并排序　　cout<<"元素比較的次數(shù)

85、為"<<C<<"次\n";　　cout<<"元素交換的次數(shù)為"<<D<<"次\n"; 　　break;　　}</b&g

86、t;　　default:　　{　　cout<<"輸入錯誤!請重新輸入...."<<endl; 　　break;&l

87、t;/p>　　}　　}　　}while(1);　　return 0;　　}

88、;　　程序測試　　5.1 程序運行的主界面（數(shù)組下標以及數(shù)組中的各個元素均由隨機函數(shù)產(chǎn)生）　　5.2 各算法運行界面　?、俨迦敕?lt;/b>　　②起泡法</b&g

89、t;　　③選擇法　?、芸焖俜?lt;/b>　?、莺喜⒎?lt;/b>　　總結(jié)　　這次課程設(shè)計運用到了大學C

90、++語言和大二所學習到的數(shù)據(jù)結(jié)構(gòu)知識點，課設(shè)題目要求不僅要求對課本知識有較深刻的了解，同時要求程序設(shè)計者有較強的思維和動手能力。這次課設(shè)使我了解我編程思想和編程技巧，也認識了軟件生命周期的各個環(huán)境，包括構(gòu)思、設(shè)計、編寫、調(diào)試、發(fā)布、文檔化、維護和修訂。編程的風格也很重要，同學只關(guān)心程序運行的結(jié)果，而對程序代碼的結(jié)構(gòu)的良好絲毫不在意。這是非常不可取的，如果我們希望將來從事編程工作，在這一點上該引起足夠的重視。這是嚴謹?shù)膽B(tài)度，很重要！<

91、;/p>　　在寫程序的過程中遇到的麻煩不是很多，由于課本上都把最基本的算法寫的很清楚，我們只需要去理解，把分散的知識聚攏來，用學過的知識把一個一個的排序恰當?shù)倪B接起來就能把程序的主要部分寫好，再加一修改就可以了，而且在這一學期的學習生活中，我們已經(jīng)把大多數(shù)的排序都寫好了，所以這對于我們來說還是比較輕松的一件事，但是在寫程序的過程中還是會遇到一些麻煩，那就需要我們的小心謹慎和積極探索的精神了，爭取把程序?qū)懙母?/p>

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告---各種內(nèi)排序性能比較

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告---各種內(nèi)排序性能比較

文檔簡介

溫馨提示

最新文檔

評論

免費下載