归并排序实验报告.doc

[标签:标题] [标签:标题] 2016 PAGE18 / NUMPAGES18 感谢观看本文谢谢 归并排序实验报告 一、实验内容： 对二路归并排序和快速排序对于逆序的顺序数的排序时间复杂度比较。 二、所用算法的基本思想及复杂度分析： 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)。 三、源程序及注释： 1、归并排序 #include #include #include“windows.h” usingnamespacestd; voidMerge(intr[],intr1[],ints,intm,intt) } intMergeSort(intr[],intr1[],ints,intt) { } voidmain() inti=s;intj=m+1;intk=s;while(iinta[100000];inta1[10000]; intn,i; intb[3]={1000,3000,5000};//产生3个数组。 for(intj=0;j{ n=b[j]; for(i=1;ia[i]=n; LARGE_INTEGERBegainTime;LARGE_INTEGEREndTime;LARGE_INTEGERFrequency;QueryPerformanceFrequency(Frequency);QueryPerformanceCounter(BegainTime);intc=MergeSort(a,a1,0,n-1);QueryPerformanceCounter(EndTime);cout} } 2、快速排序 #include #include #include“windows.h” usingnamespacestd; intPartition(intdata[],intfirst,intend) { inti,j; }while(iintquicksort(intc[],intfirst,intend) { inti;if(first}}quicksort(c,i+1,end);//递归处理右区间return0; voidmain() { inta[100000],n,i; intb[3]={1000,3000,5000};//3个数据范围 for(intj=0;j{ n=b[j]; for(i=1;iLARGE_INTEGERBegainTime;LARGE_INTEGEREndTime;LARGE_INTEGERFrequency;QueryPerformanceFrequency(Frequency);QueryPerformanceCounter(BegainTime);intc=quicksort(a,0,n);QueryPerformanceCounter(EndTime);cout} } 四、运行输出结果： 归并排序 实验报告 实验一合并排序、快速排序 一．实验目的 学习合并排序和快速排序算法的思想，掌握原理。 运用合并排序和快速排序算法的思想进行编程实现，以加深理解。 二．实验内容 输入几个整数，运用合并排序的思想进行编程实现，输出正确的排序结果。 输入10个整数，运用快速排序的思想进行编程实现，输出正确的排序结果 三．实验代码 (1)合并排序源代码如下： #include//调用setw #include//将b[0]至b[right-left+1]拷贝到a[left]至a[right]template voidCopy(Ta[],Tb[],intleft,intright) {intsize=right-left+1; for(inti=0;i{ a[left++]=b[i]; } }//合并