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

《归并排序与快速排序实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、实验内容：对二路归并排序和快速排序对于逆序的顺序数的排序时间复杂度比较。二、所用算法的基本思想及复杂度分析：1、归并排序1）基本思想：运用分治法，其分治策略为：①划分：将待排序列r1,r2,……,rn划分为两个长度相等的子序列r1,……,rn/2和rn/2+1,……,rn。②求解子问题：分别对这两个子序列进行排序，得到两个有序子序列。③合并：将这两个有序子序列合并成一个有序子序列。2）复杂度分析：二路归并排序的时间代价是O(nlog2n)。二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间

2、，因此其空间复杂性O(n)。2、快速排序：1）基本思想：运用分治法，其分治策略为：①划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1……ri-1和ri+1……rn，轴值的位置i在划分的过程中确定，并且前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值。②求解子问题：分别对划分后的每一个子序列递归处理。③合并：由于对子序列r1……ri-1和ri+1……rn的排序是就地进行的，所以合并不需要执行任何操作。2）复杂度分析：快速排序在平均时间复杂性是O(nlog

3、2n)。最坏的情况下是O(n^2)。三、源程序及注释：1、归并排序#include#include#include"windows.h"usingnamespacestd;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++];//取r[i]和r[j]中较小的放入r1[k]中elser1[k++]=r[

4、j++];}if(i<=m)while(i<=m)r1[k++]=r[i++];//第一个没处理完，进行收尾elsewhile(j<=t)r1[k++]=r[j++];//第二个没处理完，进行收尾for(intl=0;l

5、排序前半个子序列MergeSort(r,r1,m+1,t);//归并排序后半个子序列Merge(r1,r,s,m,t);//合并两个已排序的子序列}return0;}voidmain(){inta[];inta1[10000];intn,i;intb[3]={1000,3000,5000};//产生3个数组。for(intj=0;j<3;j++){n=b[j];for(i=1;i<=n;i++)a[i]=n;LARGE_INTEGERBegainTime;LARGE_INTEGEREndTime;LAR

6、GE_INTEGERFrequency;QueryPerformanceFrequency(&Frequency);QueryPerformanceCounter(&BegainTime);intc=MergeSort(a,a1,0,n-1);QueryPerformanceCounter(&EndTime);cout<<"数据个数为"<

7、QuadPart<#include#include"windows.h"usingnamespacestd;intPartition(intdata[],intfirst,intend){inti,j;i=first;j=end;while(i

8、a[j]=temp;//将较小的放到前面i++;}while(i