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

算法设计与分析实验报告实验名称分治法实现归并排序算法评分实验日期年月日指导教师姓名专业班级学号一.实验要求1.了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。2.掌握分治法的一般控制流程。DanC(p,q)globaln，A[1:n];integerm,p,q;//1pqnifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);//pmqreturnCombine(DanC(p,m),DanC(m+1,q));endifendDanC3．实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。二.实验内容1.编程实现归并排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。2.输入10组相同的数据，验证排序结果和完成排序的比较次数。3.与复杂性函数所计算的比较次数比较。4.用表格列出比较结果。5.给出文字分析。三.程序算法1.归并排序算法procedureMERGESORT(low，high)//A(low；high)是一个全程数组，它含有high-low+1≥0个待排序的元素//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；h←low；i←low；j←mid+1；whileh≤midandj≤highdo//当两个集合都没取尽时//ifA(h)≤A(j)thenB(i)←A(h)；h←h+1elseB(i)←A(j)；j←j+1endifi←i+1repeatifhmidthenfork←jtohighdo//处理剩余的元素//B(i)←A(k)；i←i+1repeatelsefork←htomiddoB(i)←A(k)；i←i+1repeatendif将已归并的集合复制到AendMERGE2.快速排序算法QuickSort(p,q)//将数组A[1:n]中的元素A[p],A[p+1],,A[q]按不降次序排列，并假定A[n+1]是一个确定的、且大于A[1:n]中所有的数。//intp,q;globaln,A[1:n];ifpqthenj=Partition(p,q+1);//划分后j成为划分元素的位置QuickSort(p,j-1);QuickSort(j+1,q);endifendQuickSortprocedurePARTITION(m，p)//退出过程时，p带着划分元素所在的下标位置。//integerm，p，i；globalA(m：p-1)v←A(m)；i←m//A(m)是划分元素//looploopi←i+1untilA(i)≥vrepeat//i由左向右移//loopp←p-1untilA(p)≤vrepeat//p由右向左移//ifipthencallINTERCHANGE(A(i)，A(p))//A(i)和A(p)换位//elseexitendifrepeatA(m)←A(p)；A(p)←v//划分元素在位置p//EndPARTITION四.程序代码1.归并排序#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();}2.快速排序#includeiostream.h#includeiomanip.h#includestdlib.h#includetime.h#defineMAXI10typedefintKeyType;typedefintElemType;structrec{KeyTypekey;ElemTypedata;};typedefrecsqlist[MAXI];classkuaisu{public:kuaisu(sqlista,intm):n(m){for(inti=0;in;i++)b[i]=a[i];}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=b[s];while(ij){while(ij&&b[j].key=p.key)j--;b[i]=b[j];while(ij&&b[i].key=p.key)i++;b[j]=b[i];}b[i]=p;output();returni;}voidoutput(){for(inti=0;in;i++)coutsetw(4)b[i].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++)a1[i].key=rand()%80;kuaisupx(a1,n);cout数组排序过程演示:\n;px.quicksort(low,high);cout排序后数组:\n;px.output();cin.get();}五.程序调试中的问题相同数字在比较的过程中会使用很多的时间，不能提高排序的速度六.实验结果1.归并排序2.快速排序