实验一-算法的时间复杂度

实验一算法的时间复杂度一、 实验目的与要求熟悉C/C++语言的集成开发环境；通过本实验加深对算法分析基础知识的理解。二、实验内容：掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。三、实验题定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排序对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况：1、数组中的数据随机生成；2、数组中的数据已经是非递减有序。四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序#include<iostream>#include<time.h>usingnamespacestd;constintn=5000：〃可根据需要更改数组大小classSort(public:voidRadom();〃生成一个随机数数组voidOrder。;//生成一个非递减数组voidBubbleSort(intr[],intn);〃冒泡排序voidSelectSort(intr[],intn);/徜单选择排序intPartition(intr[],intfirst,intend);〃快速排序一次划分算法voidQuickSort(intr[],intfirst,intend);〃快速排序voidMerge(intr[],intrl[J,ints,intm,intt);/一次归并排序voidMergeSort(intr[],intrl[],ints,int并排序inta[n];〃存放随机数的数组intal[n];〃存放非递减数据的数组intexchange;〃冒泡排序中记载每次记录交换的位置intbound;〃冒泡排序中记录无序区的最后一个记录intindex;〃简单选择排序中记录在一趟比较过程中关键码最小的记录位置intpivot;〃快速排序中的基准记录inttemp;〃用于排序中的交换｝；〃==========================等成随机数组======================voidSort::Radom()//srand(unsigned(time(NULL)));for(inti=O;i<n;i++)随机数}//=====================================.//=======================^成非递减数组===voidSort::Order()(for(inti=0;i<n;i++)al[i]=i；}〃 〃==============================冒泡排序=======voidSort::BubbleSort(intr[],intn)(exchanges-1;〃第一趟冒泡排序的范围是r[0倒r[n]while(exchange){bound=exchange;exchange=O;for(intj=0;j<bound;j++)if(r|j]>r[j+l])(temp=r[j+l];r[j+ll=r[j]；r[j]=temp;exchange=j;}))〃======================================================〃===========================简单选择排序=====================voidSort::SelectSort(intr[],intn)(for(inti=0;i<n;i++)(index=i;for(intj=i+1;j<=n;j++)(if(r[j]<r[index])index=j;)if(index!=i){temp=r[i];r[i]=r[index];r[index]=temp;)〃=====================^速排序一次划分算法==============intSort::Partition(intr[],intfirst,intend)(inti=first;intj=end;while(i<j)(while(i<j&&r[i]<=r[j-l])j--;〃右侧扫描if(i<j)(temp=r[i];r[i]=r[j];r[j]=temp;〃将较小记录换到前面i++；while(i<j&&r[i]<=r[j-l])i++;〃左侧扫描if(i<j)(temp=r[i];r[i]=r[j];r(j]=temp;〃将较大记录换到后面j-；))returni;//i为轴值记录的最终位置//=======================我速排序=======================voidSort::QuickSort(intr[J,intfirst,intend)(if(first<end)(pivot=Partition(r,hrst,end);〃——次戈U分Quicksorts,first,pivot-1);/健归地对左侧子序列进行快速排序QuickSort(r,pivot+l,end);/健归地*j右侧子序歹U进行快速排序//====================================================================voidSort::Merge(intr[],intrl[],ints,intm,intt)(inti=s;intj=m+l;intk=s;while(i<=m&&j<=t)(if(r[i]<=rUDrl[k++]=r[i++];elserl[k++]=r[j++];)if(i<=m)while(i<=m)//若第一个子序列没处理完，则进行收尾处理rl[k++]=r[i++l；elsewhile(j<=t) 〃若第二个子序列没处理完，则进行收尾处理r1[k++[=r[J++]；)〃===========================================================〃=========================归并排序(递归)========================voidSort::MergeSort(intr[],intrl[],ints,intt)if(s=t)rl[s]=r[s];else(intm=(s+t)/2;MergeSort(r,rl,s,m);〃归并排序前半个子序列MergeSort(r,rl,m+l,t);〃归并排序前半个子序列Merge(rl,r,s,m,t)；〃将两个已排序的子序列归并))//====================================================================//===========================主函数=========================intmain()(Sorts;clock_tstart,end;s.Radom();start=clock();s.BubbleSort(s.a,n);end=clock();coutvv”随机数组冒泡排序所需时间为："vv(double)(end・start)vv"ms"vvendl;s.Radom();start=clock();s.SelectSort(s.a,n);end=clock();coutvv”随机数组简单选择排序所需时间为：”vv(double)(end-start)vv"ms"vvendl;s.Radom();start=clock();s.QuickSort(s.a,0,n-1);end=clock();coutvv”随机数组快速排序所需时间为：,,«(double)(end-start)«,'ms,'«endl;s.Radom();intb[n]={0};start=clock();s.MergeSort(s.a,b,0,n-1);end=clock();coutvv”随机数组归并排序所需时间为："vv(double)(end・start)vv”ms"«endl;cout«endl;start=clock();s.BubbleSort(s.al,n);end=clock();coutvv”非递减数组冒泡排序所需时间为：,,«(double)(end-start)«,,ms,,«endl;s.Radom();start=clock();s.SelectSort(s.al,n);end=clock();cout«”非递减数组简单选择排序所需时间为：”vv(double)(end-start)«"ms"v<endl：start=clock();s.QuickSort(s.al,0,n-l);end=clock();cout<<"非递减数组快速排序所需时间为："vv(double)(end-start)vv"ms"vvendl;start=clock();s.MergeSort(s.a1,b,O,n-1);end=clock();cout<<”非递减数组归并排序所需时间为：n«(double)(end-start)«MmsM«endl;return0;)六、实验结果当n=1000时：当n=3000时:当n=5000时:46ns:递减数组0ns47ns:递减数组归并由anykeytocontinue当n=7000时:，盘并46ns:递减数组0ns47ns:递减数组归并由anykeytocontinue当n=7000时:，盘并组组组组数数数矶矶矶矶-屋嘉而所予r—/7V1.，二，lF.fc-w二二二.<-141ms时间为：62ms为：0ms为：0nsy-—冒泡排序所需k回为： :递减数组简堂选择排序昉需时间为:港速教喊到瀛鹦麟公anukeytocontinue矶矶ylyl组组组组---EJ-------B-n-&t、st、当n=9000时:203ns:递减数组：0nsanykeytocontinue递减数组简懿曷:递减数组怏速排序班:递减数组向并扉声防需时间为।188ms同为：172ms同为：15ms203ns:递减数组：0nsanykeytocontinue递减数组简懿曷:递减数组怏速排序班:递减数组向并扉声防需时间为।188ms同为：172ms同为：15ms当n=U000时:予择序序—7♦zV3<，■，，4P♦=二1速并组组组组ea：921ns时间为：391ns为：15ms需时间为：0ns：453ns时间为：I蠹呷［BJ为：0nST需时间为:0ns■当n=13000时:三递减数组冒泡排序所需毁回为：0msE递减数组葡单连择价序防错时间为：407ms实验结果制表:随机数组排序所需时间随机数组n=1000n=3000n=5000n=7000n=9000n=11000n=13000冒泡排序1662141281453656921简单选择排序03162109203282391快速排序000160015归并排序00000150非递减数组排序所花时间非递减数组n=1000n=3000n=5000n=7000n=9000n=11000n=13000冒泡排序0000000简单选择排序01646110188282407快速排序03147941721归并排序0000151

随机数组时间复杂度函数曲线:随机数组数组大小一随机数组数组大小一冒泡排序简单选择排序快速排序归并排序非递减数组时间复杂度函数曲线:非递减数组七、实验分析运行环境：VisualC++6.0CPU：2.53GHz内存：1.92GB系统：MicrosoftWindowsXPProfessional版本2002冒泡排序：在最好情况下，待排序记录序列为正序，算法只执行一趟，进行了n-1次关犍码的比较，不需要移动记录，时间复杂度为O(n)；在最坏情况下，待排序记录序列为反序，每趟排序在无序序列中只有一个最大的记录被交换到最终位置，故算法执行n-1趟，第i(lWiVn)趟排序执行了n-i次关键码的比较和n-i次记录的交换，这样，关键码的比较次数为E(n-i)=n(n-1)/2,记录的移动次数为3n(n-1)/2,因此，时间复杂度为O(n*n)；在平均情况下，冒泡排序的时间复杂度与最坏情况同数量级。冒泡排序是一种稳定的排序方法。简单选择排序：在选择排序中记录的移动次数较少。在待排序列为正序时，记录的移动次数最少，为0；第i趟排序需进行n-i次比较，而选择排序需进行n-1趟排序，总比较次数为：E(n-1)=n(n-1)/2=O(n*n)所以，总的时间复杂度为O(n*n),这是简单选择排序最好、最坏、和平均的时间性能。简单选择排序是一种稳定的排序方法。快速排序：在最好情况下，每次划分对一个记录定位后，该记录的左侧子序列与右侧子序列的长度相同。在具有n个记录的序列中，对一个记录定位要对整个待划分序列扫描一遍，则所需时间为O(n)。设T(n)是对