《实验一算法的时间复杂度.doc》由会员分享，可在线阅读，更多相关《实验一算法的时间复杂度.doc（15页珍藏版）》请在三一文库上搜索。
1、算法时间复杂度实验 学院：计算机科学与技术 班级： 软 件082班 姓名： 黄 健 学号： 20084350242 算法的时间复杂度一、 实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对算法分析基础知识的理解。二、 实验内容:掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。三、 实验题定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排序对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况：1、数组中的数据随机生成；2、数组中的数据已经是非递减有
2、序。四、 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、 实验程序 #include #includeusing namespace std;void MergeSort(int,int,int);void Merge(int ,int,int,int);int main()int h=0; const int n=5000;int tn;clock_t start,end;clock_t start1,end1;for(int i=0;in;i+)ti=rand()%n;for(int j=0;j100;j+)coutt
3、j ; coutn排序中.endl; coutn数组排序后的前100位：endl;start=clock(); MergeSort(t,0,n-1);end=clock();for(int b=0;b100;b+)couttb ;coutn随机赋值数组的归并排序时间：(end - start)endl; start1=clock(); MergeSort(t,0,n-1); end1=clock();coutn非递减有序数组的归并排序时间：(end1 - start1)endl;return 0;void Merge(int r,int s,int m,int t)int i=s;int j=
4、m+1;int k=s;int r15000; while(i=m&j=t)if(ri=rj)r1k+=ri+;else r1k+=rj+;if(i=j)while(j=t)r1k+=rj+;elsewhile(i=m)r1k+=ri+; if (i=m) while (i=m) r1k+=ri+; else while (j=t) r1k+=rj+; for(int g=s;g=t;g+) rg=r1g; void MergeSort(int r,int s,int t)if (st)int m=(s+t)/2;MergeSort(r,s,m);MergeSort(r,m+1,t); Mer
5、ge(r,s,m,t); int Partition(int , int, int);void QuickSort(int , int, int);int main()int h=0;int t10000;clock_t start,end;clock_t start1,end1;for(int i=0;i10000;i+)ti=rand()%10000; for(int k=0;k100;k+) couttk ; coutn排序中.endl; coutn数组排序后的前100位：endl;start=clock();QuickSort(t,0,i-1);end=clock(); for(int
6、 j=0;j100;j+) couttj ;coutn随机赋值数组的快速排序时间：(end - start)endl;start1=clock();QuickSort(t,0,6359); end1=clock();coutn非递减有序数组的快速排序时间：(end1 - start1)endl;return 0;void QuickSort(int r , int first, int end)int pivot; if (firstend) pivot=Partition(r, first, end); QuickSort(r, first, pivot-1); QuickSort(r, p
7、ivot+1, end); int Partition(int r , int first, int end)int i=first;int j=end; int h;int k;/初始化while (ij) while (ij & ri= rj) j-; /右侧扫描 if (ij) h=ri; ri=rj; rj=h; /将较小记录交换到前面 i+; while (ij & ri= rj) i+; /左侧扫描if (ij) k=ri; ri=rj; rj=k; /将较大记录交换到后面 j-; return i; /i为轴值记录的最终位置void BubbleSort(int,int);int
8、 main()int h=0;int t10000;clock_t start,end;clock_t start1,end1;for(int i=0;i10000;i+)ti=rand()%10000; for(int k=0;k100;k+) couttk ; coutn排序中.endl; coutn数组排序后的前100位：endl;start=clock();BubbleSort(t,10000);end=clock(); for(int p=0;p100;p+) couttp ;coutn随机赋值数组的起泡排序时间：(end - start)endl;start1=clock();Bu
9、bbleSort(t,10000); end1=clock();coutn非递减有序数组的起泡排序时间：(end1 - start1)endl;return 0;void BubbleSort(int r , int n) int exchange;int bound;int m; exchange=n; while (exchange) bound=exchange; exchange=0; for (int j=0; jrj+1) m=rj; rj=rj+1; rj+1=m; exchange=j; void SelectSort(int,int);int main()int h=0;in
10、t t10000;clock_t start,end;clock_t start1,end1;for(int i=0;i10000;i+)ti=rand()%10000; for(int j=0;j100;j+) couttj ; coutn排序中.endl; coutn数组排序后的前100位：endl;start=clock();SelectSort(t,10000);end=clock(); for(int k=0;k100;k+) couttk ; coutn随机赋值数组的简单选择排序时间：(end - start)endl; start1=clock();SelectSort(t,10000); end1=clock();coutn非递减有序数组的简单选择排序时间：(end1- start1)endl;return 0;void SelectSort(int r , int n) int temp;int q; for (int i=0; in-1; i+) /对n个记录进行n-1趟简单选择排序 q=i; for (int j=i+1; jn; j+) /在无序区中选取最小记录 if (rjrq) q=j; if (q!=i) temp=ri; ri=rq; rq=temp;六、 实验结果