實(shí)驗(yàn)2-分治法實(shí)現(xiàn)歸并排序

算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告第2次實(shí)驗(yàn)姓名學(xué)號(hào)班級(jí)時(shí)間10.17上午地點(diǎn)工訓(xùn)樓309實(shí)驗(yàn)名稱利用分治法實(shí)現(xiàn)歸并排序算法實(shí)驗(yàn)?zāi)康耐ㄟ^上機(jī)實(shí)驗(yàn)，要求掌握分治法解決問題，以及二路歸并算法的實(shí)現(xiàn)。實(shí)驗(yàn)原理使用分治法和二路歸并算法，根據(jù)不同的隨機(jī)數(shù)規(guī)模和數(shù)量，能準(zhǔn)確的輸出通過二路歸并排序后的數(shù)組，并計(jì)算出程序運(yùn)行所需要的時(shí)間。實(shí)驗(yàn)步驟①先輸入隨機(jī)數(shù)組的長(zhǎng)度和規(guī)模；②產(chǎn)生一個(gè)隨機(jī)數(shù)組；③計(jì)時(shí)開始，調(diào)用排序函數(shù)；④輸出排序后的數(shù)組，輸出算法話費(fèi)的時(shí)間。關(guān)鍵代碼template<classT>//將b[0]至b[right-left+1]拷貝到a[left]至a[right]voidCopy(Ta[],Tb[],intleft,intright){intsize=right-left+1;for(inti=0;i<size;i++){a[left++]=b[i];}}//合并有序數(shù)組a[left:i],a[i+1:right]到b,得到新的有序數(shù)組btemplate<classT>voidMerge(Ta[],Tb[],intleft,inti,intright){inta1cout=left,//指向第一個(gè)數(shù)組開頭a1end=i,//指向第一個(gè)數(shù)組結(jié)尾a2cout=i+1,//指向第二個(gè)數(shù)組開頭a2end=right,//指向第二個(gè)數(shù)組結(jié)尾bcout=0;//指向b中的元素for(intj=0;j<right-left+1;j++)//執(zhí)行right-left+1次循環(huán){if(a1cout>a1end){b[bcout++]=a[a2cout++];continue;}//如果第一個(gè)數(shù)組結(jié)束，拷貝第二個(gè)數(shù)組的元素到bif(a2cout>a2end){b[bcout++]=a[a1cout++];continue;}//如果第二個(gè)數(shù)組結(jié)束，拷貝第一個(gè)數(shù)組的元素到bif(a[a1cout]<a[a2cout]){b[bcout++]=a[a1cout++];continue;}//如果兩個(gè)數(shù)組都沒結(jié)束，比較元素大小，把較小的放入belse{b[bcout++]=a[a2cout++];continue;}}}//對(duì)數(shù)組a[left:right]進(jìn)行合并排序template<classT>voidMergeSort(Ta[],intleft,intright){T*b=newint[right-left+1];if(left<right){inti=(left+right)/2;//取中點(diǎn)MergeSort(a,left,i);//左半邊進(jìn)行合并排序MergeSort(a,i+1,right);//右半邊進(jìn)行合并排序Merge(a,b,left,i,right);//左右合并到b中Copy(a,b,left,right);//從b拷貝回來}}測(cè)試結(jié)果實(shí)驗(yàn)心得通過這次實(shí)驗(yàn)，我更加理解了分治法的策略和遞歸的調(diào)用。明白了二路歸并排序的實(shí)質(zhì)辦法?？梢员容^在同樣數(shù)據(jù)規(guī)模的情況下，不加入隨機(jī)化過程和加入隨機(jī)化過程的運(yùn)行時(shí)間。特別是在數(shù)據(jù)基本有序的情況下，加入隨機(jī)化過程應(yīng)該能大大提高速度。計(jì)算算法運(yùn)行的時(shí)間和程序運(yùn)行的時(shí)間是不一樣的，剛開始我把計(jì)算算法運(yùn)行時(shí)間的函數(shù)start（）的位置弄錯(cuò)了，自己不知道還是助教學(xué)長(zhǎng)的提醒，才知道自己的錯(cuò)誤，導(dǎo)致后面運(yùn)行的時(shí)候得出來的時(shí)間有7,8秒了，是把我的輸入的時(shí)間也算進(jìn)去了，沒有得到準(zhǔn)確的算法運(yùn)行時(shí)間。改變計(jì)算時(shí)間函數(shù)的位置后，算法運(yùn)行的時(shí)間才正確了。實(shí)驗(yàn)得分助教簽名附錄：完整代碼#include<time.h>#include<iostream>#include<iomanip>#include<stdlib.h>usingnamespacestd;template<classT>//將b[0]至b[right-left+1]拷貝到a[left]至a[right]voidCopy(Ta[],Tb[],intleft,intright){intsize=right-left+1;for(inti=0;i<size;i++){a[left++]=b[i];}}//合并有序數(shù)組a[left:i],a[i+1:right]到b,得到新的有序數(shù)組btemplate<classT>voidMerge(Ta[],Tb[],intleft,inti,intright){inta1cout=left,//指向第一個(gè)數(shù)組開頭a1end=i,//指向第一個(gè)數(shù)組結(jié)尾a2cout=i+1,//指向第二個(gè)數(shù)組開頭a2end=right,//指向第二個(gè)數(shù)組結(jié)尾bcout=0;//指向b中的元素for(intj=0;j<right-left+1;j++)//執(zhí)行right-left+1次循環(huán){if(a1cout>a1end){b[bcout++]=a[a2cout++];continue;}//如果第一個(gè)數(shù)組結(jié)束，拷貝第二個(gè)數(shù)組的元素到bif(a2cout>a2end){b[bcout++]=a[a1cout++];continue;}//如果第二個(gè)數(shù)組結(jié)束，拷貝第一個(gè)數(shù)組的元素到bif(a[a1cout]<a[a2cout]){b[bcout++]=a[a1cout++];continue;}//如果兩個(gè)數(shù)組都沒結(jié)束，比較元素大小，把較小的放入belse{b[bcout++]=a[a2cout++];continue;}}}//對(duì)數(shù)組a[left:right]進(jìn)行合并排序template<classT>voidMergeSort(Ta[],intleft,intright){T*b=newint[right-left+1];if(left<right){inti=(left+right)/2;//取中點(diǎn)MergeSort(a,left,i);//左半邊進(jìn)行合并排序MergeSort(a,i+1,right);//右半邊進(jìn)行合并排序Merge(a,b,left,i,right);//左右合并到b中Copy(a,b,left,right);//從b拷貝回來}}intmain(){while(1){intn;intf;cout<<"請(qǐng)輸入您將要排序的數(shù)目:";cin>>n;cout<<"請(qǐng)輸入隨機(jī)數(shù)的規(guī)模：";cin>>f;int*a=newint[n];cout<<"產(chǎn)生的隨機(jī)數(shù)：";//取隨機(jī)數(shù)srand((unsigned)time(NULL));for(inti=0;i<n;i++){a[i]=(rand()%(f)+0);cout<<a[i]<<'';}//計(jì)時(shí)開始clock_tstart,end,over;start=clock();end=clock();over=end-start;start=clock();MergeSort(a,0,n-1);cout<<endl;cout<<"排序結(jié)果:";