《（时间管理）算法时间复杂度》由会员分享，可在线阅读，更多相关《（时间管理）算法时间复杂度（6页珍藏版）》请在金锄头文库上搜索。
1、实验一 算法的时间复杂度一、实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对算法分析基础知识的理解。二、实验内容:掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。三、实验题定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排序对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况：1、数组中的数据随机生成；2、数组中的数据已经是非递减有序。四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实
2、验报告。五、实验程序#include#include#includeusing namespace std;void SelectSort(int r , int n) int i;int j;int index;int temp; for (i=0; in-1; i+) index=i; for (j=i+1; jn; j+) if (rjrindex) index=j; if (index!=i) temp=ri; ri=rindex; rindex=temp; for(i=0;in;i+) coutri ; coutn;void BubbleSort(int r, int n)int t
3、emp;int exchange;int bound; exchange=n-1; while (exchange) bound=exchange; exchange=0; for (int j=0; jrj+1) temp=rj; rj=rj+1; rj+1=temp; exchange=j; for(int i=0;in;i+) coutri ;coutn;int Partition(int r, int first, int end)int i=first; int j=end;int temp; while (ij) while (ij & ri= rj)j-; if (ij) tem
4、p=ri; ri=rj; rj=temp; i+; while (ij & ri= rj) i+; if (ij) temp=rj; rj=ri; ri=temp; j-; return i; /快速排序void QuickSort(int r, int first, int end) if (firstend) int pivot=Partition(r, first, end); QuickSort(r, first, pivot-1); QuickSort(r, pivot+1, end); void Merge(int r, int r1, int s, int m, int t)in
5、t i=s;int j=m+1;int k=s; while (i=m & j=t) if (ri=rj) r1k+=ri+; else r1k+=rj+; if (i=m) while (i=m) r1k+=ri+; else while (j=t) r1k+=rj+; void MergePass(int r , int r1 , int n, int h)int i=0;int k; while (i=n-2*h) Merge(r, r1, i, i+h-1, i+2*h-1); i+=2*h; if (in-h) Merge(r, r1, i, i+h-1, n); else for
6、(k=i; k=n; k+) r1k=rk;void MergeSort2(int r, int r1, int r2,int s, int t) int m;if (s=t) r1s=rs; else m=(s+t)/2; MergeSort2(r, r2, r1, s, m); MergeSort2(r, r2, r1, m+1, t); Merge(r2, r1, s, m, t); int main()int b100; const int numv=100;clock_t t=clock(); for(int k=0;k100;k+)bk=rand()%100; coutbk ; c
7、out n起泡排序结果为： n; BubbleSort(b, numv); coutclock()-tmsendl; coutn 简单选择排序结果为：n;SelectSort(b, numv); coutclock()-tmsendl;coutn 快速排序结果为：n;QuickSort(b,0,100);for(int j=0;j100;j+) coutbj ;coutn; coutclock()-tmsendl;const int h=100;int b1h;for(int i=0;ih;i+)b1i=rand()%k;int a1h;int c1h;coutn 归并排序结果为：n;Merg
8、eSort2(b1,a1,c1,0,h-1);for(int m=0; m h; m+) couta1m ; coutn; cout(clock()-t)msendl; return 0; 六 实验结果当随机数为10时：起泡排序结果为：4ms简单选择排序结果为：7ms快速排序结果为：12ms归并排序结果为：16ms当随机数为100时：起泡排序结果为：20ms简单选择排序结果为：41ms快速排序结果为：61ms归并排序结果为：82ms当随机数为1000时：起泡排序结果为：289ms简单选择排序结果为：480ms快速排序结果为：720ms归并排序结果为：993ms 七、实验分析通过本实验知道了最快排序的方法，明白了各种排序法的时间复杂度。
