归并排序与快速排序实验报告

1一、实验内容：对二路归并排序和快速排序对于逆序的顺序数的排序时间复杂度比较。二、所用算法的基本思想及复杂度分析：1、归并排序1）基本思想：运用分治法，其分治策略为：①划分：将待排序列r1,r2,……,rn划分为两个长度相等的子序列r1,……,rn/2和rn/2+1,……,rn。②求解子问题：分别对这两个子序列进行排序，得到两个有序子序列。③合并：将这两个有序子序列合并成一个有序子序列。2）复杂度分析：二路归并排序的时间代价是O(nlog2n)。二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂性O(n)。2、快速排序：1）基本思想：运用分治法，其分治策略为：①划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1……ri-1和ri+1……rn，轴值的位置i在划分的过程中确定，并且前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值。②求解子问题：分别对划分后的每一个子序列递归处理。③合并：由于对子序列r1……ri-1和ri+1……rn的排序是就地进行的，所以合并不需要执行任何操作。2）复杂度分析：快速排序在平均时间复杂性是O(nlog2n)。最坏的情况下是O(n^2)。三、源程序及注释：1、归并排序#includeiostream#includefstream#includewindows.husingnamespacestd;voidMerge(intr[],intr1[],ints,intm,intt)2{inti=s;intj=m+1;intk=s;while(i=m&&j=t){if(r[i]=r[j])r1[k++]=r[i++];//取r[i]和r[j]中较小的放入r1[k]中elser1[k++]=r[j++];}if(i=m)while(i=m)r1[k++]=r[i++];//第一个没处理完，进行收尾elsewhile(j=t)r1[k++]=r[j++];//第二个没处理完，进行收尾for(intl=0;lk;l++){r[l]=r1[l];//将合并完成后的r1[]序列送回r[]中}}intMergeSort(intr[],intr1[],ints,intt){if(s==t)r1[s]=r[s];else{intm;m=(s+t)/2;MergeSort(r,r1,s,m);//归并排序前半个子序列MergeSort(r,r1,m+1,t);//归并排序后半个子序列Merge(r1,r,s,m,t);//合并两个已排序的子序列}return0;}voidmain()3{inta[100000];inta1[10000];intn,i;intb[3]={1000,3000,5000};//产生3个数组。for(intj=0;j3;j++){n=b[j];for(i=1;i=n;i++)a[i]=n;LARGE_INTEGERBegainTime;LARGE_INTEGEREndTime;LARGE_INTEGERFrequency;QueryPerformanceFrequency(&Frequency);QueryPerformanceCounter(&BegainTime);intc=MergeSort(a,a1,0,n-1);QueryPerformanceCounter(&EndTime);cout数据个数为n时归并排序的时间为（单位：s）：(double)(EndTime1.QuadPart-BegainTime1.QuadPart)/Frequency1.QuadPartendl;}}2、快速排序#includeiostream#includefstream#includewindows.husingnamespacestd;intPartition(intdata[],intfirst,intend){inti,j;4i=first;j=end;while(ij){while(ij&&data[i]=data[j])j--;//从左侧扫描if(ij){inttemp;temp=data[i];data[i]=data[j];data[j]=temp;//将较小的放到前面i++;}while(ij&&data[i]=data[j])i++;//从右侧扫描if(ij){inttemp1;temp1=data[i];data[i]=data[j];data[j]=temp1;//将较小的放到后面j--;}}returni;}intquicksort(intc[],intfirst,intend){inti;if(firstend){i=Partition(c,first,end);//对c[hs]到c[ht]进行一次划分5quicksort(c,first,i-1);//递归处理左区间quicksort(c,i+1,end);//递归处理右区间}return0;}voidmain(){inta[100000],n,i;intb[3]={1000,3000,5000};//3个数据范围for(intj=0;j3;j++){n=b[j];for(i=1;i=n;i++)a[i]=n;LARGE_INTEGERBegainTime;LARGE_INTEGEREndTime;LARGE_INTEGERFrequency;QueryPerformanceFrequency(&Frequency);QueryPerformanceCounter(&BegainTime);intc=quicksort(a,0,n);QueryPerformanceCounter(&EndTime);cout数据个数为n时快速排序的时间为（单位：s）：(double)(EndTime.QuadPart-BegainTime.QuadPart)/Frequency.QuadPartendl;}}四、运行输出结果：归并排序6快速排序五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：1、在归并排序中，书中最后应将递归后的r1[]数组送回r[]数组中，即r[l]=r1[l]，否则将无法进行。2、运行程序后发现，对于1000,3000,5000个数的归并排序和快速排序时间上差不多，相差不是很大，在1000和3000时快速排序略快一些，但到5000时归并排序就变快了，可能是由于逆序数的原因，对于数量越大的数，归并排序显示出了它的优势。