分治算法实验分析

算法分析与设计实验报告第 二 次实验姓名学号班级时间10.17上午地点工训楼309实验名称分治算法实验（用分治法实现归并排序算法）实验目的通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据，利用分治法的思想，将数据进行排序并将排好的数据进 行输出。程序思路：（1）简单的将原始序列划分为两个子序列；（2）分别对每一个子序列递归排序；（3）最后将排好序的子序列合并成一个有序序列。实验步骤 先解决小规模的问题。 将问题分解，将数组分为两个小的数组。 递归的解各子问题，将 中分解的两个小的数组再进行以上两个步骤 最后都化为小规模问题。 将各子问题的解进行合并最终得到原问题的解。关键代码void merge(int A, int B, int low, int mid, int high) /将两个子序列合并排序成一个有序的序列int i=low;int j=mid+1;int k=low;while(i=mid)& (j二high)/两两比较，将较小的数放在临时的数组中if(Aimid)/如果最后左半边子序列已经全部排完，就将右边子序列剩下的元素直接复制到临时的数组中for (int last二j;last二high;last+)Bk+=Alast;else/如果最后右半边子序列已经全部排完，就将左边子序列剩下的元素直接复制到临时的数组中for(int last二i;last二mid;last+)Bk+=Alast;void mergesort(int a, int b, int left,int right) /分治 法实现归并排序，利用递归实现if (lef t righ t)/如果序列中元素超过一个才会进行划分int mid=(left+right)/2;/将序列从中位数地方划分为两个子序列mergesor t( a,b,lef t,mid);/对左半边子序列递归调用自身，将子序列变成有序mergesor t( a,b,mid+l,righ t);/对右边子序列递归调用自身，将子序列变成有序merge(a,b,lef t,mid,righ t);/调用合并函数，将子序列合并，实现整个数列的有序for(int h=left;h=right;h+)/将临时有序的数组复制回原数组ah=bh;没有输出排序序列的结果:测试结果isisisisis0.0000.0010.0090.060取314请按任意rrr输出排序序列的结果:实验心得对于归并排序，在之前的数据结构已经学过了，本来以为代码实现起来会比较 简单，可是情况并不是这样的。对于分治法这个算法，我存在的困难主要是我 明白分治过程是如何的，但是却很难和代码练习起来，我对于递归过程还是很 不清楚，所以代码实现起来还是很困难。不过幸好我之前有提前准备，提前将 归并排序仔细的研究过了，所以还是磕磕巴巴的将代码实现，也因为这两个分 治法的实验，使我更加深入了解了分治法，对于递归过程也更加明白，相信在 自己练习几次之后，能够掌握这个函数。实验比较观察上面两个不冋的实现方法所花费的时间，我们可以看到，米用非递归的方 法实现，所花费的时间比利用分治法花费的时间多,为什么会出现这样的结果， 我们可以知道在分治法需要比较的次数比非递归方法多，甚至是多得多，所以 它所花费的时间也多，所以对于这种求最大值最小值的问题，利用非递归的方 法相对会好一点。实验得分助教签名附录： 完整代码(分治法) #include #include #include using namespace std;void merge(int A,int B,int low,int mid,int high) /将两个子序列合并，排序成一个有序的序列 int i=low;int j=mid+1;int k=low;while(i=mid)&(j=high) /两两比较，将较小的数放在临时的数组 中 if(Aimid)/如果最后左半边子序列已经全部排完，就将右边子序列剩下的元素直接复制到临时的数组中for(int last=j;last=high;last+)Bk+=Alast;else/如果最后右半边子序列已经全部排完，就将左边子序列剩下的元素直接复制到临时的数组中for(int last=i;last=mid;last+) Bk+=Alast; void mergesort(int a,int b,int left,int right) /分治法实现归并排 序，利用递归实现if(leftright)/如果序列中元素超过一个才会进行划分int mid=(left+right)/2;/将序列从中位数地方划分为两个子序列mergesort(a,b,left,mid);/ 对左半边子序列递归调用自身，将子序列变成有序 mergesort(a,b,mid+1,right);/对右边子序列递归调用自身，将子序列变成有序merge(a,b,left,mid,right);/调用合并函数，将子序列合并，实现整个数列的有序for(int h=left;h=right;h+)/将临时有序的数组复制回原数组II ah=bh;void ran(int * inp ut, int n)/数组随机生成函数int i; srand(time(0); for(i=0;in;i+) inputi=rand();inputi=0; int a1000000;int b1000000;int main()int n;cou t请输入要归并排序的记录个数：endl;for(int j=0;jn;ran(a,n);/生成数组clock_t start,end,over;/计算程序运行时间的算法start=clock();end=clock(); over=end-start;start=clock(); mergesort(a,b,0,n-1);/调用分治法函数for(int i=0;in;i+) coutai ; coutendl; end=clock();pri ntf (The time is %6.3f,(double)(end-s tart-over)/CLK_TCK);/输 出运行时间 system(pause);return 0;完整代码(非递归方法)#include/随机生成数组元素函数#include #include using namespace std;void ran(int *input,int n)int i;srand(time(0); for(i=0;in;i+) inputi=rand();inputi=0;int a1000000;int main()int max=a0,min=a0;int i,j,n;cou t 请输入数据规模：endl;for(j=0;jn;ran(a,n);clock_t start,end,over;/计算程序运行时间的算法start=clock();end=clock(); over=end-start; start=clock();for(i=1;imax) max=ai;if(aimin) min=ai; coutmax minendl;end=clock();printf(The time is %6.3f,(double)(end-start-over)/CLK_TCK); /显 示运行时间system(pause);return 0;