分治法實(shí)現(xiàn)歸并排序算法算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告

1、算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱分治法實(shí)現(xiàn)歸并排序算法評(píng)分實(shí)驗(yàn)日期年月曰指導(dǎo)教師姓名專業(yè)班級(jí)學(xué)號(hào)1 .實(shí)驗(yàn)要求1 .了解用分治法求解的問題：當(dāng)要求解一個(gè)輸入規(guī)模為n,且n的取值相當(dāng)大的問題時(shí)，如果問題可以分成k個(gè)不同子集合，得到k個(gè)不同的可獨(dú)立求解的子問題，其中1<kwn,而且子問題與原問題性質(zhì)相同，原問題的解可由這些子問題的解合并得出。那末，對(duì)于這類問題分治法是十分有效的。2 .掌握分治法的一般控制流程。DanQp,q)globaln,A1:n;integerm,p,q;/1<p<nifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);

2、/p<m<qreturnCombine(DanC(p,m),DanC(m+1,q);endifendDanC3 .實(shí)現(xiàn)典型的分治算法的編程與上機(jī)實(shí)驗(yàn)，驗(yàn)證算法的時(shí)間復(fù)雜性函數(shù)。2 .實(shí)驗(yàn)內(nèi)容1 .編程實(shí)現(xiàn)歸并排序算法，程序中加入比較次數(shù)的計(jì)數(shù)功能，輸出排序結(jié)果和比較次數(shù)。2 .輸入10組相同的數(shù)據(jù)，驗(yàn)證排序結(jié)果和完成排序的比較次數(shù)。3 .與復(fù)雜性函數(shù)所計(jì)算的比較次數(shù)比較。4 .用表格列出比較結(jié)果。5 .給出文字分析。3 .程序算法1 .歸并排序算法procedureMERGESORT(low,high)/A(low;high)是一個(gè)全程數(shù)組，它含有high-low+1>0個(gè)待

3、排序的元素/integerlow,high;iflow<high;thenmid/求這個(gè)集合的分割點(diǎn)/callMERGESORT(low,mid)/將一個(gè)子集合排序/callMERGESORT(mid+1,high)/將另一個(gè)子集合排序callMERGE(low,mid,high)/歸并兩個(gè)已排序的子集合/endifendMERGESORT歸并兩個(gè)已排序的集合procedureMERGE(low,mid,high)/A(low:high)是一個(gè)全程數(shù)組/輔助數(shù)組B(low;high)/integerh,i,j,k；hlow;ilow;jmid+1;whileh<midandj<

4、;highdo/當(dāng)兩個(gè)集合都沒取盡時(shí)/ifA(h)<A(j)thenB(i)-A(h);h-h+1elseB(i)-A(j);j-j+1endifi-i+1repeatifh>midthenforkjtohighdo/處理剩余的元素/B(i)-A(k);i-i+1repeatelseforkhtomiddoB(i)-A(k);i-i+1repeatendif將已歸并的集合復(fù)制到AendMERGE2.快速排序算法QuickSort(p,q)將數(shù)組A1:n中的元素Ap,Ap+1,.,Aq按不降次序排列,并假定An+1是一一個(gè)確定的、且大于A1:n中所有的數(shù)。/intp,q;global

5、n,A1:n;ifp<qthenj=Partition(p,q+1);/劃分后j成為劃分元素的位置QuickSort(p,j-1);QuickSort(j+1,q);endifendQuicksortprocedurePARTITION(m,p)/退出過程時(shí)，p帶著劃分元素所在的下標(biāo)位置。/integerm,p,i;globalA(m:p-1)vA(m);im/A(m)是劃分元素looploopii+1untilA(i)looppp-1untilA(p)ifi<pthencallINTERCHANGE(A(i)elseexitendifrepeatA(m)-A(p);A(p)-v/

6、EndPARTITION四.程序代碼>vrepeat/i由左向右移<vrepeat/p由右向左移,A(p)/A(i)和A(p)換位/劃分元素在位置p1 .歸并排序#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include<time.h>#defineM11typedefintKeyType;typedefintElemType;structrecKeyTypekey;ElemTypedata;typedefrecsqlistM;classguibingpublic

7、:guibing(sqlistb)for(inti=0;i<M;i+)ri=bi;voidoutput(sqlistr,intn)(for(inti=0;i<n;i+)cout<<setw(4)<<ri.key;cout<<endl;)voidxuanze(sqlistb,intm,intn)(inti,j,k;for(i=m;i<n-1;i+)(k=i;for(j=i;j<n;j+)if(bk.key>bj.key)k=j;if(k!=i)(rectemp=bk;bk=bi;bi=temp;)voidmerge(intl,in

8、tm,inth,sqlistr2)(xuanze(r,l,m);xuanze(r,m,h);output(r,M);inti,j,k;k=i=l;for(j=m;i<m&&j<h;k+)(if(ri.key<=rj.key)(r2k=ri;i+;)else(r2k=rj;j+；)output(r2,M);)while(j<h)(r2k=rj;j+；k+;)while(i<=m)(r2k=ri;i+;k+;)output(r2,M);)private:sqlistr;);voidmain()(cout<<"guibingfa1運(yùn)

9、行結(jié)果：n"sqlista,b;inti,j=0,k=M/2,n=M;srand(time(0);for(i=0;i<M;i+)(ai.key=rand()%80;bi.key=0;)guibinggx(a);cout<<"排序前數(shù)組：n"gx.output(a,M);cout<<"數(shù)組排序過程演示：n"gx.merge(j,k,n,b);cout<<"排序后數(shù)組:n"gx.output(b,M);cin.get();)2 .快速排序#include<iostream.h>

10、;#include<iomanip.h>#include<stdlib.h>#include<time.h>#defineMAXI10typedefintKeyType;typedefintElemType;structrecKeyTypekey;ElemTypedata;);typedefrecsqlistMAXI;classkuaisupublic:kuaisu(sqlista,intm):n(m)for(inti=0;i<n;i+)bi=ai;)voidquicksort(ints,intt)inti;if(s<t)i=part(s,t);

11、quicksort(s,i-1);quicksort(i+1,t);)elsereturn;)intpart(ints,intt)inti,j;recp;i=s;j=t;p=bs;while(i<j)(while(i<j&&bj.key>=p.key)j-;bi=bj;while(i<j&&bi.key<=p.key)i+;bj=bi;bi=p;output();returni;voidoutput()(for(inti=0;i<n;i+)cout<<setw(4)<<bi.key;cout<&l

12、t;endl;private:sqlistb;intn;voidmain()(cout<<"kuaisu1.cpp運(yùn)行結(jié)果：n"sqlista1;inti,n=MAXI,low=0,high=9;srand(time(0);for(i=0;i<n;i+)a1i.key=rand()%80;kuaisupx(a1,n);cout<<"數(shù)組排序過程演示：n"px.quicksort(low,high);cout<<"排序后數(shù)組：n"px.output();cin.get();五.程序調(diào)試中的問題相

13、同數(shù)字在比較的過程中會(huì)使用很多的時(shí)間，不能提高排序的速度六.實(shí)驗(yàn)結(jié)果1.歸并排序：，算法實(shí)會(huì)'分治法Uebuz'guibingfalexebribing"工運(yùn)行結(jié)果；排序前數(shù)組:232271231364214123G32散組排序過程演示:1322232371221234163642QQ008000002138用0000&0213216000068021321220000S002132122230000802132122232300陰0021321222323230000213212223232341S00213212223232341638021321222323234163640213212223232341636471排序后數(shù)組：2132122232323416364712.快速排序a%