《算法设计与分析》实验二分治策略运用练习

学号算法设计与分析实验报告二学生姓名专业、班级指导教师唐国峰成绩电子与信息工程系2013 年 4 月 15 日实验二：分治策略运用练习一、实验目的本次实验是针对分治策略运用的算法设计及应用练习，旨在加深学生对该部分知识点的理 解，提高学生运用该部分知识解决问题的能力。二、实验步骤与要求1实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；2学生独自完成实验指定内容；3实验结束后，用统一的实验报告模板编写实验报告。4提交说明：（1）电子版提交说明：a 需要提交 Winrar 压缩包，文件名为“算法设计与分析实验二 _学号_姓名”， 如“算法设计与分析实验二_09290101_张三”。b 压缩包内为一个“算法设计与分析实验二 _学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。（2）打印版提交说明：a 不可随意更改模板样式。b 字体：中文为宋体，大小为 10 号字，英文为 Time New Roman ，大小为 10 号 字。c 行间距：单倍行距。（3）提交截止时间：2012 年 4 月 29 日 16:00。三、实验项目1对用户输入的杂乱无序的数字序列按照由小到大的顺序排序。要求分别运用合并排序和 快速排序完成该题目要求。四、实验过程（一） 题目一：对于用户随意输入的 7 个无序数字，用合并排序的方法，按照从小到大的顺 序进行排序。1. 题目分析：将待排序元素分成大致相同的两个子集合，分别对两个子集合进行排序，最 终将排好序的子集合合并成所要求的排好序的集合。2. 算法构造：调用三个函数来实现，MergePass用于合并排好序的相邻数组段，具体的合 并算法由 Merge 用来实现， MergeSort 函数为合并算法，调用 Merge、MergePass 函数来 实现数的合并排序3. 算法实现#includetemplatevoid MergeSort(Type a,int n)Type*b=new Type;int s=1;while(sn)MergePass(a,b,s,n);/将a中的元素合并到数组bs+=s;MergePass(b,a,s,n);/将b中的元素合并到数组as+=s;templatevoid Merge(Type c,Type d, int l,int m,int r) /合并 cl,m和 xm+l,r到 yl,rint i=l,j=m+1,k=l;while(i=m)&(j=r)if(cim)for(int q=j;q=r;q+)dk+=cq;elsefor(int q=i;q=m;q+)dk+=cq;templatevoid MergePass(Type x,Type y,int s,int n)/合并大小为 s 的相邻序列子数组int i=0;while(i=n-2*s)/合并大小为 s 的相邻 2 字段数组Merge(x,y,i,i+sT,i+2*sT);/合并 xi,i+sT和 xi+s,i+2*sT到 yi,i+2*s-l i=i+2*s;if(i+sn)/处理剩下的元素少于2sMerge(x,y,i,i+s-1,n-1);elsefor(int j=i;j=n-1;j+) yj=xj;void main()int a7,i;printf(请输入7个数字：n);for( i=0;i7;i+)scanf(%d,&ai);MergeSort(a,7);printf(最终排序结果为：n);for(int e=0;e7;e+)printf(%dt,ae);printf(n);4. 运行结果5. 经验归纳：我主要参考书上的程序来做的，我感觉主要是做好合并数组二)题目二：对用户输入的无序的数字，按照快速排序方法，由小到大的顺序排序。1. 题目分析：通过一趟扫描，就能确保某个数并以它为基准点的左边各数都比它小，右边 各数都比它大。然后又用同样的方法处理，它左右两边的数，直到基准点的左右只有一 个元素为止2. 算法构造：定义轴测元素，然后从两端各个和轴测元素比较后放在相应的位置，相比元 素一样，将轴测元素放到中间。对排好序的两边，重复上述操作。3. 算法实现#includevoid quickSort(int a,int l,int r)int i,j,t;i=l; j=r;t=al;/轴测元素 t 为数组最左侧的元素if(lr)return;while(i!=j)/ 扫描完，结束时语句 while(aj=t & ji)j-;/ 如果右侧指针元素比轴测元素大，指针元素左移if(ji)ai+=aj;while(aii)i+;/ 如果左侧指针元素比轴测元素小，指针元素右移if(ji)aj-=ai;ai=t;quickSort(a,l,i-1); / 对左边进行排序quickSort(a,i+1,r); / 对右边进行排序void main()int i,f7;prin tf(请输入7个无序的数字：n);for(i = 0; i 7; i +) scanf(%d,&fi); quickSort(f,0,7);printf(快速排序后：n);for(i=0;i7;i+)printf(%d ,fi);printf(n);4. 运行结果I C:US ERSA N DVD ES KTOP农算法设计与分析实验一_1029021曉妙氐血小快速宀h Le5醫排323速49序35 :9后14273Press any key to continue5. 经验归纳：主要找出轴测元素和两端元素进行比较，依次进行这样就行五、实验总结通过这次实验我了解并理解了合并排序和快速排序，以前只是学习了快速排序的思想并没有 编程，合并的编程我参照课本上的程序，马马虎虎把它做下来了，快速排序我主要是查看了一些 资料，来编写的，这次实验让我在合并和快速排序上面的编程有了更加进一步的理解。