算法时间复杂度

实验一算法的时间复杂度一、实验目的与要求熟悉C/C++语言的集成开发环境；通过本实验加深对算法分析基础知识的理解。二、实验内容:掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。三、实验题定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排序对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况：1、数组中的数据随机生成；2、数组中的数据已经是非递减有序。四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序#includeiostream#includetime.h#includewindows.husingnamespacestd;voidSelectSort(intr[],intn){inti;intj;intindex;inttemp;for(i=0;in-1;i++){index=i;for(j=i+1;jn;j++)if(r[j]r[index])index=j;if(index!=i){temp=r[i];r[i]=r[index];r[index]=temp;}}for(i=0;in;i++)coutr[i];cout\n;}voidBubbleSort(intr[],intn){inttemp;intexchange;intbound;exchange=n-1;while(exchange){bound=exchange;exchange=0;for(intj=0;jbound;j++)if(r[j]r[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;}}for(inti=0;in;i++)coutr[i];cout\n;}intPartition(intr[],intfirst,intend){inti=first;intj=end;inttemp;while(ij){while(ij&&r[i]=r[j])j--;if(ij){temp=r[i];r[i]=r[j];r[j]=temp;i++;}while(ij&&r[i]=r[j])i++;if(ij){temp=r[j];r[j]=r[i];r[i]=temp;j--;}}returni;}//快速排序voidQuickSort(intr[],intfirst,intend){if(firstend){intpivot=Partition(r,first,end);QuickSort(r,first,pivot-1);QuickSort(r,pivot+1,end);}}voidMerge(intr[],intr1[],ints,intm,intt){inti=s;intj=m+1;intk=s;while(i=m&&j=t){if(r[i]=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}if(i=m)while(i=m)r1[k++]=r[i++];elsewhile(j=t)r1[k++]=r[j++];}voidMergePass(intr[],intr1[],intn,inth){inti=0;intk;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);elsefor(k=i;k=n;k++)r1[k]=r[k];}voidMergeSort2(intr[],intr1[],intr2[],ints,intt){intm;if(s==t){r1[s]=r[s];}else{m=(s+t)/2;MergeSort2(r,r2,r1,s,m);MergeSort2(r,r2,r1,m+1,t);Merge(r2,r1,s,m,t);}}intmain(){intb[100];constintnumv=100;clock_tt=clock();for(intk=0;k100;k++)b[k]=rand()%100;coutb[k];cout\n起泡排序结果为：\n;BubbleSort(b,numv);coutclock()-tmsendl;cout\n简单选择排序结果为：\n;SelectSort(b,numv);coutclock()-tmsendl;cout\n快速排序结果为：\n;QuickSort(b,0,100);for(intj=0;j100;j++)coutb[j];cout\n;coutclock()-tmsendl;constinth=100;intb1[h];for(inti=0;ih;i++)b1[i]=rand()%k;inta1[h];intc1[h];cout\n归并排序结果为：\n;MergeSort2(b1,a1,c1,0,h-1);for(intm=0;mh;m++)couta1[m];cout\n;cout(clock()-t)msendl;return0;}六实验结果当随机数为10时：起泡排序结果为：4ms简单选择排序结果为：7ms快速排序结果为：12ms归并排序结果为：16ms当随机数为100时：起泡排序结果为：20ms简单选择排序结果为：41ms快速排序结果为：61ms归并排序结果为：82ms当随机数为1000时：起泡排序结果为：289ms简单选择排序结果为：480ms快速排序结果为：720ms归并排序结果为：993ms七、实验分析通过本实验知道了最快排序的方法，明白了各种排序法的时间复杂度。