2022年分治法实现归并排序算法算法设计与分析实验报告 .pdf
算法设计与分析实验报告实验名称分治法实现归并排序算法评分实验日期年月日指导教师姓名专业班级学号一.实验要求1.了解用分治法求解的问题：当要求解一个输入规模为n，且 n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1kn，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。2.掌握分治法的一般控制流程。DanC(p,q)global n，A1:n;integer m,p,q;/1p q n if Small(p,q)then return G(p,q);else m=Divide(p,q);/pmq return Combine(DanC(p,m),DanC(m+1,q);endif end DanC 3实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。二.实验内容1.编程实现归并排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。2.输入 10组相同的数据，验证排序结果和完成排序的比较次数。3.与复杂性函数所计算的比较次数比较。4.用表格列出比较结果。5.给出文字分析。三.程序算法1.归并排序算法procedure MERGESORT(low，high)/A(low；high)是一个全程数组，它含有high-low+10个待排序的元素/integer low，high；if lowmid then for kj to high do /处理剩余的元素/B(i)A(k)；i i+1 repeat else for kh to mid do B(i)A(k)；i i+1 repeat endif 将已归并的集合复制到A end MERGE 2.快速排序算法QuickSort(p,q)/将数组 A1:n 中的元素 Ap,Ap+1,Aq按不降次序排列，并假定 An+1 是一个确定的、且大于 A1:n中所有的数。/int p,q;global n,A1:n;if pq then j=Partition(p,q+1);/划分后 j 成为划分元素的位置名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 8 页 -QuickSort(p,j-1);QuickSort(j+1,q);endif end QuickSort procedure PARTITION(m，p)/退出过程时，p带着划分元素所在的下标位置。/integer m，p，i；global A(m：p-1)vA(m)；i m /A(m)是划分元素/loop loop ii+1 until A(i)v repeat /i由左向右移/loop pp-1 until A(p)v repeat /p由右向左移/if ip then call INTERCHANGE(A(i)，A(p)/A(i)和A(p)换位/else exit endif repeat A(m)A(p)；A(p)v /划分元素在位置p/End PARTITION四.程序代码1.归并排序#include#include#include#include#define M 11 typedef int KeyType;typedef int ElemType;struct rec KeyType key;ElemType data;typedef rec sqlistM;class guibing public:guibing(sqlist b)for(int i=0;iM;i+)ri=bi;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 8 页 -void output(sqlist r,int n)for(int i=0;in;i+)coutsetw(4)ri.key;coutendl;void xuanze(sqlist b,int m,int n)int i,j,k;for(i=m;in-1;i+)k=i;for(j=i;jbj.key)k=j;if(k!=i)rec temp=bk;bk=bi;bi=temp;void merge(int l,int m,int h,sqlist r2)xuanze(r,l,m);xuanze(r,m,h);output(r,M);int i,j,k;k=i=l;for(j=m;im&jh;k+)if(ri.key=rj.key)r2k=ri;i+;else 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 8 页 -r2k=rj;j+;output(r2,M);while(jh)r2k=rj;j+;k+;while(i=m)r2k=ri;i+;k+;output(r2,M);private:sqlist r;void main()coutguibingfa1运行结果:n;sqlist a,b;int i,j=0,k=M/2,n=M;srand(time(0);for(i=0;iM;i+)ai.key=rand()%80;bi.key=0;guibing gx(a);cout 排序前数组:n;gx.output(a,M);cout 数组排序过程演示:n;gx.merge(j,k,n,b);名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 8 页 -cout 排序后数组:n;gx.output(b,M);cin.get();2.快速排序#include#include#include#include#define MAXI 10 typedef int KeyType;typedef int ElemType;struct rec KeyType key;ElemType data;typedef rec sqlistMAXI;class kuaisu public:kuaisu(sqlist a,int m):n(m)for(int i=0;in;i+)bi=ai;void quicksort(int s,int t)int i;if(st)i=part(s,t);quicksort(s,i-1);quicksort(i+1,t);else return;int part(int s,int t)int i,j;rec p;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 8 页 -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;output();return i;void output()for(int i=0;in;i+)coutsetw(4)bi.key;coutendl;private:sqlist b;int n;void main()coutkuaisu1.cpp运行结果:n;sqlist a1;int i,n=MAXI,low=0,high=9;srand(time(0);for(i=0;in;i+)a1i.key=rand()%80;kuaisu px(a1,n);cout 数组排序过程演示:n;px.quicksort(low,high);cout 排序后数组:n;px.output();cin.get();名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 8 页 -五.程序调试中的问题相同数字在比较的过程中会使用很多的时间，不能提高排序的速度六.实验结果1.归并排序2.快速排序名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 8 页 -
