分治法实现归并排序算法算法设计与分析试验报告

1、算法设计与分析实验报告实验名称分治法实现归并排序算法评分实验日期年月曰指导教师姓名专业班级学号一 .实验要求1 .了解用分治法求解的问题：当要求解一个输入规模为 n,且 n 的取值相当大的问题时，如果问题可以分成 k 个不同子集合，得到 k 个不同的可独立求解的子问题，其中 1kwn,而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。2 .掌握分治法的一般控制流程。DanQp,q)globaln,A1:n;integerm,p,q;/1pnifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);/pm0

2、 个待排序的元素/integerlow,high;iflowhigh;thenmid/求这个集合的分割点/callMERGESORT(low,mid)/将一个子集合排序/callMERGESORT(mid+1,high)/将另一个子集合排序callMERGE(low,mid,high)/归并两个已排序的子集合/endifendMERGESORT归并两个已排序的集合procedureMERGE(low,mid,high)/A(low:high)是一个全程数组/辅助数组 B(low;high)/integerh,i,j,k；hlow;ilow;jmid+1;whilehmidandjhighdo/

3、当两个集合都没取尽时/ifA(h)midthenforkjtohighdo/处理剩余的元素/B(i)-A(k);i-i+1repeatelseforkhtomiddoB(i)-A(k);i-i+1repeatendif将已归并的集合复制到 AendMERGE2.快速排序算法QuickSort(p,q)将数组 A1:n中的元素Ap,Ap+1,.,Aq按不降次序排列,并假定 An+1是一一个确定的、且大于A1:n中所有的数。/intp,q;globaln,A1:n;ifpqthenj=Partition(p,q+1);/划分后 j 成为划分元素的位置QuickSort(p,j-1);QuickSo

4、rt(j+1,q);endifendQuicksortprocedurePARTITION(m,p)/退出过程时，p 带着划分元素所在的下标位置。/integerm,p,i;globalA(m:p-1)vA(m);im/A(m)是划分元素loop1 .归并排序#include#include#include#include#defineM11typedefintKeyType;typedefintElemType;structrecKeyTypekey;ElemTypedata;typedefrecsqlistM;classguibingpublic:guibing(sqlistb)for(i

5、nti=0;iM;i+)ri=bi;loopii+1untilA(i)looppp-1untilA(p)ifivrepeat/i 由左向右移vrepeat/p 由右向左移,A(p)/A(i)和 A(p)换位/划分元素在位置 pvoidoutput(sqlistr,intn)(for(inti=0;in;i+)coutsetw(4)ri.key;coutendl;)voidxuanze(sqlistb,intm,intn)(inti,j,k;for(i=m;in-1;i+)(k=i;for(j=i;jbj.key)k=j;if(k!=i)(rectemp=bk;bk=bi;bi=temp;)vo

6、idmerge(intl,intm,inth,sqlistr2)(xuanze(r,l,m);xuanze(r,m,h);output(r,M);inti,j,k;k=i=l;for(j=m;im&jh;k+)(if(ri.key=rj.key)(r2k=ri;i+;)else(r2k=rj;j+；)output(r2,M);)while(jh)(r2k=rj;j+；k+;)while(i=m)(r2k=ri;i+;k+;)output(r2,M);)private:sqlistr;);voidmain()(coutguibingfa1 运行结果：n;sqlista,b;inti,j=

7、0,k=M/2,n=M;srand(time(0);for(i=0;iM;i+)(ai.key=rand()%80;bi.key=0;)guibinggx(a);cout排序前数组：n;gx.output(a,M);cout数组排序过程演示：n;gx.merge(j,k,n,b);cout排序后数组:n;gx.output(b,M);cin.get();)2 .快速排序#include#include#include#include#defineMAXI10typedefintKeyType;typedefintElemType;structrecKeyTypekey;ElemTypedata

8、;);typedefrecsqlistMAXI;classkuaisupublic:kuaisu(sqlista,intm):n(m)for(inti=0;in;i+)bi=ai;)voidquicksort(ints,intt)inti;if(st)i=part(s,t);quicksort(s,i-1);quicksort(i+1,t);)elsereturn;)intpart(ints,intt)inti,j;recp;i=s;j=t;p=bs;while(ij)(while(i=p.key)j-;bi=bj;while(ij&bi.key=p.key)i+;bj=bi;bi=p

9、;output();returni;voidoutput()(for(inti=0;in;i+)coutsetw(4)bi.key;coutendl;private:sqlistb;intn;voidmain()(coutkuaisu1.cpp 运行结果：n;sqlista1;inti,n=MAXI,low=0,high=9;srand(time(0);for(i=0;in;i+)a1i.key=rand()%80;kuaisupx(a1,n);cout数组排序过程演示：n;px.quicksort(low,high);cout排序后数组：n;px.output();cin.get();五.程

10、序调试中的问题相同数字在比较的过程中会使用很多的时间，不能提高排序的速度六.实验结果1.归并排序：，：， 算法实会算法实会 分治法分治法Uebuzguibingfalexebribing工运行结果；排序前数组:232271231364214123G32散组排序过程演示:1322232371221234163642QQ008000002138用0000&0213216000068021321220000S002132122230000802132122232300阴0021321222323230000213212223232341S00213212223232341638021321222323234163640213212223232341636471排序后数组：2132122232323416364712.快速排序a%算法实会分治法 ezeaisul cjppj互行2吉果二题组排序过程演示：3?2