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

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

2、记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1ri-1和ri+1rn，轴值的位置i在划分的过程中确定，并且前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值。 求解子问题：分别对划分后的每一个子序列递归处理。 合并：由于对子序列r1ri-1和ri+1rn的排序是就地进行的，所以合并不需要执行任何操作。2） 复杂度分析： 快速排序在平均时间复杂性是O(nlog2n)。最坏的情况下是O(n2)。三、源程序及注释：1、 归并排序#include#include#include windows.husing namespace std;void Merge(int

3、 r,int r1,int s,int m,int t )int i=s;int j=m+1;int k=s;while(i=m&j=t)if(ri=rj)r1k+=ri+;/取ri和rj中较小的放入r1k中else r1k+=rj+;if(i=m)while(i=m)r1k+=ri+;/第一个没处理完，进行收尾else while(j=t)r1k+=rj+;/第二个没处理完，进行收尾for(int l=0;lk;l+)rl=r1l;/将合并完成后的r1序列送回r中int MergeSort(int r,int r1,int s,int t)if(s=t)r1s=rs;elseint m;m=

4、(s+t)/2;MergeSort(r,r1,s,m);/归并排序前半个子序列MergeSort(r,r1,m+1,t); /归并排序后半个子序列Merge(r1,r,s,m,t);/合并两个已排序的子序列return 0;void main()int a100000;int a110000; int n,i; int b3= 1000,3000,5000;/产生3个数组。 for(int j=0; j3; j+) n=bj; for(i=1; i=n; i+) ai=n;LARGE_INTEGER BegainTime ; LARGE_INTEGER EndTime ; LARGE_INTE

5、GER Frequency; QueryPerformanceFrequency(&Frequency); QueryPerformanceCounter(&BegainTime) ; int c=MergeSort(a,a1,0,n-1);QueryPerformanceCounter(&EndTime);cout 数据个数为n时归并排序的时间为（单位：s）： (double)( EndTime1.QuadPart - BegainTime1.QuadPart )/ Frequency1.QuadPart endl; 2、快速排序#include#include#include window

6、s.husing namespace std;int Partition (int data,int first,int end)int i,j;i=first;j=end; while(ij)while(ij&datai=dataj)j-;/从左侧扫描if(ij)int temp; temp=datai;datai=dataj;dataj=temp;/将较小的放到前面i+;while(ij&datai=dataj)i+;/从右侧扫描if(ij)int temp1;temp1=datai;datai=dataj;dataj=temp1;/将较小的放到后面j-;return i;int quic

7、ksort(int c,int first,int end)int i;if(firstend) i=Partition(c,first,end);/对chs到cht进行一次划分quicksort(c,first,i-1);/递归处理左区间quicksort(c,i+1,end);/递归处理右区间return 0;void main()int a100000,n,i; int b3= 1000,3000,5000;/3个数据范围 for(int j=0; j3; j+) n=bj; for(i=1; i=n; i+) ai=n;LARGE_INTEGER BegainTime ; LARGE_

8、INTEGER EndTime; LARGE_INTEGER Frequency ; QueryPerformanceFrequency(&Frequency); QueryPerformanceCounter(&BegainTime) ; int c= quicksort(a,0,n);QueryPerformanceCounter(&EndTime); cout 数据个数为n时快速排序的时间为（单位：s）： (double)( EndTime.QuadPart - BegainTime.QuadPart )/ Frequency.QuadPart endl; 四、运行输出结果： 归并排序快速排序五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：1、在归并排序中，书中最后应将递归后的r1数组送回r数组中，即rl=r1l，否