实验1归并排序分治策略的设计与实现(报告).doc

湖南大学 算法分析与设计实验报告 实验1 归并排序分治策略的设计与实现一、实验目的1、熟悉分治法求解问题的抽象控制策略；2、熟悉在顺序存储表示下求解分类问题的递归算法设计；3、通过实例转换, 掌握分治法应用。二、实验内容1、学习分治方法的原理 ；2、针对分治问题设计递归算法实现归并排序算法；3、根据归并排序的递归算法改写成迭代算法。4、测试程序与验收并进一步将程序改写成模块化可用程序。三、实验程序的功能模块【模块】void Merge(int r,int r1,int s,int m,int t) 实现数组中的已分好类的两部分进行合并 void MergeSort(int r,int r1,int s,int t) 对数组中从下标low开始到heigh结束的部分进行分类 【递归实现】/合并数组void Merge(int r,int r1,int s,int m,int t) / r为待排序数列 r1用来存放排好序的数列 三个int型变量 s m t ，分别为数组的最左，中间，最右 int i=s;int j=m+1;int k=s; while(i=m & j=t) if(ri=rj) /左右两边的数组从头开始比，选择小者放入r1r1k+=ri+; else r1k+=rj+; if(i=m) /若比完之后，左边有剩下，依次填入r1 while(i=m) r1k+=ri+; else /比完之后，右边有剩下，依次填入r1while(j=t) r1k+=rj+; for(int l=0;lt-s+1;l+) /复制会原数组，此步骤可省去 rl=r1l; /归并算法void MergeSort(int r,int r1,int s,int t) /结束归并条件，数组内只有一个元素if(s=t) r1s=rs; else int m=(s+t)/2; /规定变量m，数组中间 MergeSort(r,r1,s,m); /左边归并MergeSort(r,r1,m+1,t); /右边归并Merge(r1,r,s,m,t); /合并【迭代实现】/合并算法 sort为合并后数组，list为待合并数组，low,center,high分别为待合并数组的最左边，中间，最右边void merge(int *sort, int *list, int low, int center, int high) int i,j,k; /i,j分别代表两个小数组的最左边，通过比较，选择小者放入合并后数组for(i=low,j=(center+1),k=low; i=center & j listj) /若左边数组大，放右边数组未用的最左边的元素进sortsortk = listj+; else sortk = listi+; while(i=center) /若左边数组还有元素，依次填入sortsortk+ = listi+; while(j=high) /若右边数组还有元素，依次填入sortsortk+ = listj+; /每次步长分组 a是分组后数组，b是待分组数组，length为步长（小组长度），n为大数组总长void merge_pass(int *a, int *b, int length, int n) int i; /从数组最左边开始，按照步长分组，直到不够元素达到步长可以分组（剩最后一组）for(i=0; i=n-2*length; i+=2*length) int center = (i + i + 2*length - 1)/2; /定义每个小组的中间merge(a, b, i, center, i+2*length-1); /每个小组调用合并算法，最左边就是i,最右边是i+2*length-1 if(i+length)n) /最右边的一个分组，若此组最右边还未到达大数组最右边(此数组长度大于步长) int center = (i + i + 2*length - 1)/2; /定义此小组的中间merge(a, b, i, center, n-1); /调用合并算法，最右边是n-1 else /最后一个分组不够元素达到步长，复制 while(in) ai = bi; +i; /归并算法 array 为待排序数组，n为数组长度void m_sort(int *array, int n) int extra30; int length = 1; while(length n) /以步长为分的标准 /分组归并，结果放到extramerge_pass(extra, array, length, n);/步长增长为两倍length *= 2; /再次分组归并，结果放回arraymerge_pass(array, extra, length, n); length *= 2; 四、递归算法改写成迭代算法的一般方法1、递归一般分为三部分，开始状态，一般状态，结束状态。递归调用的过程一般可以用循环代替。两者的开始状态是一样的，结束条件也是一样，循环需要一个变量衡量结束，可以是递归里的返回变量把每步递归的操作移植到每步循环操作。以下是例子。递归 Fun(x)If(结束条件） Return;Else 每步递归操作； Fun(变量变化)迭代For（开始状态；结束状态；变量变化） 每步迭代操作。五、C+阐述分治法递归抽象控制策略问题p，子问题p，合并merge()，简单解决ADHOc(P)void fun(p)if(p=n0)return (ADHOc(P)；elseDivide p into p0pk;For(i=0;ik;i+)Fun(pi);Merge();六、思考题1、应用分治法抽象控制策略实现快速分类。解答：先分大类，再分小类，再分细节，层层细分。如单词appeal