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

《实验1归并排序分治策略的设计与实现(报告)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、湖南大学算法分析与设计实验报告实验1归并排序分治策略的设计与实现一、实验目的1、熟悉分治法求解问题的抽象控制策略；2、熟悉在顺序存储表示下求解分类问题的递归算法设计；3、通过实例转换,掌握分治法应用。二、实验内容1、学习分治方法的原理；2、针对分治问题设计递归算法实现归并排序算法；3、根据归并排序的递归算法改写成迭代算法。4、测试程序与验收并进一步将程序改写成模块化可用程序。三、实验程序的功能模块【模块】voidMerge(intr[],intr1[],ints,intm,intt){实现数组中的已分好类

2、的两部分进行合并}voidMergeSort(intr[],intr1[],ints,intt){对数组中从下标low开始到heigh结束的部分进行分类}【递归实现】//合并数组voidMerge(intr[],intr1[],ints,intm,intt)//r[]为待排序数列r1[]用来存放排好序的数列三个int型变量smt，分别为数组的最左，中间，最右{inti=s;intj=m+1;intk=s;while(i<=m&&j<=t){if(r[i]<=r[j])//左右两边的数组从头开始比，选择小者

3、放入r1r1[k++]=r[i++];elser1[k++]=r[j++];5湖南大学算法分析与设计实验报告}if(i<=m)//若比完之后，左边有剩下，依次填入r1while(i<=m)r1[k++]=r[i++];else//比完之后，右边有剩下，依次填入r1while(j<=t)r1[k++]=r[j++];for(intl=0;l

4、/结束归并条件，数组内只有一个元素if(s==t)r1[s]=r[s];else{intm=(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分别为待合并数组的最左边，中间，最右边voidmerge(int*sort,int*list,intlow,intcente

5、r,inthigh){inti,j,k;//i,j分别代表两个小数组的最左边，通过比较，选择小者放入合并后数组for(i=low,j=(center+1),k=low;i<=center&&j<=high;++k){if(list[i]>list[j])//若左边数组大，放右边数组未用的最左边的元素进sortsort[k]=list[j++];else5湖南大学算法分析与设计实验报告sort[k]=list[i++];}while(i<=center)//若左边数组还有元素，依次填入sortsort[k+

6、+]=list[i++];while(j<=high)//若右边数组还有元素，依次填入sortsort[k++]=list[j++];}//每次步长分组a是分组后数组，b是待分组数组，length为步长（小组长度），n为大数组总长voidmerge_pass(int*a,int*b,intlength,intn){inti;//从数组最左边开始，按照步长分组，直到不够元素达到步长可以分组（剩最后一组）for(i=0;i<=n-2*length;i+=2*length){intcenter=(i+i+2*l

7、ength-1)/2;//定义每个小组的中间merge(a,b,i,center,i+2*length-1);//每个小组调用合并算法，最左边就是i,最右边是i+2*length-1}if((i+length)

8、e(i