实验一 算法的时间复杂度

算法时间复杂度实验学院：计算机科学与技术班级：软件082班姓名：黄健学号：20084350242算法的时间复杂度一、实验目的与要求熟悉C/C++语言的集成开发环境；通过本实验加深对算法分析基础知识的理解。二、实验内容:掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。三、实验题定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排序对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况：1、数组中的数据随机生成；2、数组中的数据已经是非递减有序。四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序#includetime.h#includeiostreamusingnamespacestd;voidMergeSort(int[],int,int);voidMerge(int[],int,int,int);intmain(){inth=0;constintn=5000;intt[n];clock_tstart,end;clock_tstart1,end1;for(inti=0;in;i++){t[i]=rand()%n;}for(intj=0;j100;j++){coutt[j];}cout\n排序中.......endl;cout\n数组排序后的前100位：endl;start=clock();MergeSort(t,0,n-1);end=clock();for(intb=0;b100;b++){coutt[b];;}cout\n随机赋值数组的归并排序时间：(end-start)endl;start1=clock();MergeSort(t,0,n-1);end1=clock();cout\n非递减有序数组的归并排序时间：(end1-start1)endl;return0;}voidMerge(intr[],ints,intm,intt){inti=s;intj=m+1;intk=s;intr1[5000];while(i=m&&j=t){if(r[i]=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}if(i=j){while(j=t)r1[k++]=r[j++];}else{while(i=m)r1[k++]=r[i++];}if(i=m){while(i=m)r1[k++]=r[i++];}else{while(j=t)r1[k++]=r[j++];}for(intg=s;g=t;g++){r[g]=r1[g];}}voidMergeSort(intr[],ints,intt){if(st){intm=(s+t)/2;MergeSort(r,s,m);MergeSort(r,m+1,t);Merge(r,s,m,t);}}intPartition(int[],int,int);voidQuickSort(int[],int,int);intmain(){inth=0;intt[10000];clock_tstart,end;clock_tstart1,end1;for(inti=0;i10000;i++){t[i]=rand()%10000;}for(intk=0;k100;k++){coutt[k];}cout\n排序中.....endl;cout\n数组排序后的前100位：endl;start=clock();QuickSort(t,0,i-1);end=clock();for(intj=0;j100;j++){coutt[j];}cout\n随机赋值数组的快速排序时间：(end-start)endl;start1=clock();QuickSort(t,0,6359);end1=clock();cout\n非递减有序数组的快速排序时间：(end1-start1)endl;return0;}voidQuickSort(intr[],intfirst,intend){intpivot;if(firstend){pivot=Partition(r,first,end);QuickSort(r,first,pivot-1);QuickSort(r,pivot+1,end);}}intPartition(intr[],intfirst,intend){inti=first;intj=end;inth;intk;//初始化while(ij){while(ij&&r[i]=r[j])j--;//右侧扫描if(ij){h=r[i];r[i]=r[j];r[j]=h;//将较小记录交换到前面i++;}while(ij&&r[i]=r[j])i++;//左侧扫描if(ij){k=r[i];r[i]=r[j];r[j]=k;//将较大记录交换到后面j--;}}returni;//i为轴值记录的最终位置}voidBubbleSort(int[],int);intmain(){inth=0;intt[10000];clock_tstart,end;clock_tstart1,end1;for(inti=0;i10000;i++){t[i]=rand()%10000;}for(intk=0;k100;k++){coutt[k];}cout\n排序中......endl;cout\n数组排序后的前100位：endl;start=clock();BubbleSort(t,10000);end=clock();for(intp=0;p100;p++){coutt[p];}cout\n随机赋值数组的起泡排序时间：(end-start)endl;start1=clock();BubbleSort(t,10000);end1=clock();cout\n非递减有序数组的起泡排序时间：(end1-start1)endl;return0;}voidBubbleSort(intr[],intn){intexchange;intbound;intm;exchange=n;while(exchange){bound=exchange;exchange=0;for(intj=0;jbound;j++)if(r[j]r[j+1]){m=r[j];r[j]=r[j+1];r[j+1]=m;exchange=j;}}}voidSelectSort(int[],int);intmain(){inth=0;intt[10000];clock_tstart,end;clock_tstart1,end1;for(inti=0;i10000;i++){t[i]=rand()%10000;}for(intj=0;j100;j++){coutt[j];}cout\n排序中......endl;cout\n数组排序后的前100位：endl;start=clock();SelectSort(t,10000);end=clock();for(intk=0;k100;k++){coutt[k];}cout\n随机赋值数组的简单选择排序时间：(end-start)endl;start1=clock();SelectSort(t,10000);end1=clock();cout\n非递减有序数组的简单选择排序时间：(end1-start1)endl;return0;}voidSelectSort(intr[],intn){inttemp;intq;for(inti=0;in-1;i++)//对n个记录进行n-1趟简单选择排序{q=i;for(intj=i+1;jn;j++)//在无序区中选取最小记录if(r[j]r[q])q=j;if(q!=i)temp=r[i];r[i]=r[q];r[q]=temp;}}六、实验结果