实验一-分治法合并排序

本科实验报告课程名称：算法设计与分析实验项目：分治法合并排序实验地点：专业班级：学号：学生姓名：指导教师：实验一分治法合并排序一、实验目的1.掌握合并排序的基本思想2.掌握合并排序的实现方法3.学会分析算法的时间复杂度4.学会用分治法解决实际问题二、实验内容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境程序设计语言：c++编程工具：microsoftvisualstudio2010四、算法描述和程序代码#includeiostream.h#includeiomanip.h#includestdlib.h#includetime.h#defineM11typedefintKeyType;typedefintElemType;structrec{KeyTypekey;ElemTypedata;};typedefrecsqlist[M];classguibing{public:guibing(sqlistb){for(inti=0;iM;i++)r[i]=b[i];}voidoutput(sqlistr,intn){for(inti=0;in;i++)coutsetw(4)r[i].key;coutendl;}voidxuanze(sqlistb,intm,intn){inti,j,k;for(i=m;in-1;i++){k=i;for(j=i;jn;j++)if(b[k].keyb[j].key)k=j;if(k!=i){rectemp=b[k];b[k]=b[i];b[i]=temp;}}}voidmerge(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(r[i].key=r[j].key){r2[k]=r[i];i++;}else{r2[k]=r[j];j++;}output(r2,M);}while(jh){r2[k]=r[j];j++;k++;}while(i=m){r2[k]=r[i];i++;k++;}output(r2,M);}private:sqlistr;};voidmain(){coutguibingfa1运行结果:\n;sqlista,b;inti,j=0,k=M/2,n=M;srand(time(0));for(i=0;iM;i++){a[i].key=rand()%80;b[i].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();}五、实验结果截图六、实验总结