算法分治策略

實(shí)驗(yàn)報(bào)告2016/2017學(xué)年第二學(xué)期）課程名稱算法解析與設(shè)計(jì)實(shí)驗(yàn)名稱分治策略實(shí)驗(yàn)時(shí)間2017年3月30日指導(dǎo)單位計(jì)算機(jī)學(xué)院軟件工程系指導(dǎo)教師張怡婷學(xué)生姓名霍淇濱班級(jí)學(xué)號(hào)學(xué)院(系)計(jì)算機(jī)學(xué)院專業(yè)軟件工程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱分治策略指導(dǎo)教師張怡婷實(shí)驗(yàn)種類考據(jù)型（第4個(gè)實(shí)驗(yàn)密實(shí)驗(yàn)學(xué)時(shí)2實(shí)驗(yàn)時(shí)間2017-3-30碼算法是“設(shè)計(jì)型”）一、實(shí)驗(yàn)?zāi)康暮腿蝿?wù)理解分治法的算法思想，閱讀實(shí)現(xiàn)書上已有的部分程序代碼并完善程序，加深對(duì)分治法的算法原理及實(shí)現(xiàn)過程的理解二、實(shí)驗(yàn)環(huán)境(實(shí)驗(yàn)設(shè)備)VisualStudio2015三、實(shí)驗(yàn)原理及內(nèi)容（包括操作過程、結(jié)果解析等）一、用分治法實(shí)現(xiàn)一組無序序列的兩路合并排序和快速排序。要求清楚合并排序及快速排序的基根源理，編程實(shí)現(xiàn)分別用這兩種方法將輸入的一組無序序列排序?yàn)橛行蛐蛄泻筝敵?。?biāo)頭.h#include<iostream>usingnamespacestd;classSortableList{public:SortableList(intmSize);~SortableList();voidInput();//輸入數(shù)組voidOutput();//輸出數(shù)組voidMergeSort();//兩路合并排序voidQuickSort();//快速排序private:int*l;//數(shù)組指針intmaxSize;//數(shù)組最大長度intn;//數(shù)組已有元素個(gè)數(shù)voidMergeSort(intleft,intright);voidMerge(intleft,intmid,intright);voidSwap(inti,intj);//交換函數(shù)voidQuickSort(intleft,intright);intParition(intleft,intright);//

切割函數(shù)};SortableList::SortableList(intmSize){maxSize=mSize;l=newint[maxSize];n=0;}SortableList::~SortableList(){delete[]l;}voidSortableList::Input(){cout<<"

請(qǐng)輸入待排序的數(shù)組

\n";for(inti=0;i<maxSize;i++){cin>>l[i];if(l[i]==-1)break;n++;}}voidSortableList::Output(){for(inti=0;i<n;i++)cout<<l[i]<<"";}voidSortableList::MergeSort(){MergeSort(0,n-1);}voidSortableList::QuickSort(){QuickSort(0,n-1);}voidSortableList::MergeSort(intleft,intright){if(left<right){intmid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);}}voidSortableList::Merge(intleft,intmid,intright){int*temp=newint[right-left+1];inti=left,j=mid+1,k=0;while((i<=mid)&&(j<=right))if(l[i]<=l[j])temp[k++]=l[i++];elsetemp[k++]=l[j++];while(i<=mid)temp[k++]=l[i++];while(j<=right)temp[k++]=l[j++];for(i=0,k=left;k<=right;)l[k++]=temp[i++];}voidSortableList::Swap(inti,intj){intc=l[i];l[i]=l[j];l[j]=c;}voidSortableList::QuickSort(intleft,intright){if(left<right){intj=Parition(left,right);QuickSort(left,j-1);QuickSort(j+1,right);}}intSortableList::Parition(intleft,intright){inti=left,j=right+1;do{doi++;while(l[i]<l[left]);doj--;while(l[j]>l[left]);if(i<j)Swap(i,j);}while(i<j);Swap(left,j);returnj;}源.app#include<iostream>#include"標(biāo)頭.h"usingnamespacestd;voidmain(){intn=10;SortableListmy1(n);SortableListmy2(n);my1.Input();my2.Input();my1.MergeSort();my2.QuickSort();my1.Output();my2.Output();}二、采用基于“五元中值組取中值切割法”（median-of-median-of-fivepartitioning）的線性時(shí)間選擇算法，找出N個(gè)元素會(huì)集S中的第k個(gè)最小的元素，使其在線性時(shí)間內(nèi)解決。標(biāo)頭.h#include<iostream>usingnamespacestd;enumResultCode{OutOfBounds,Success};classSortableList{public:SortableList(intmSize);~SortableList();voidInput();voidOutput();ResultCodeSelect(int&x,intk);private:int*l;intmaxSize;intn;voidSwap(inti,intj);voidInsertSort(intleft,intright);intPartition(intleft,intright);intSelect(intk,intleft,intright,intr);};SortableList::SortableList(intmSize){maxSize=mSize;l=newint[maxSize];n=0;}SortableList::~SortableList(){delete[]l;}voidSortableList::Input(){cout<<"請(qǐng)輸入帶排序的數(shù)組\n";for(inti=0;i<maxSize;i++){cin>>l[i];if(l[i]==-1)break;n++;}}voidSortableList::Output(){for(inti=0;i<n;i++)cout<<l[i]<<"";}voidSortableList::Swap(inti,intj){intc=l[i];l[i]=l[j];l[j]=c;}intSortableList::Partition(intleft,intright){inti=left,j=right+1;do{doi++;while(l[i]<l[left]);doj--;while(l[j]>l[left]);if(i<j)Swap(i,j);}while(i<j);Swap(left,j);returnj;}ResultCodeSortableList::Select(int&x,intk){if(n<=0||k>n||k<=0)returnOutOfBounds;intj=Select(k,0,n-1,5);x=l[j];returnSuccess;}intSortableList::Select(intk,intleft,intright,intr){intn=right-left+1;if(n<=r){//若問題足夠小，使用直接插入排序InsertSort(left,right);returnleft+k-1;//取其中的第k小元素，其下標(biāo)為left+k-1}for(inti=1;i<=n/r;i++){InsertSort(left+(i-1)*r,left+i*r-1);//二次取中規(guī)則求每組的中間值Swap(left+i-1,left+(i-1)*r+(int)ceil((double)r/2)-1);//將每組的中間值交換到子表前部集中存放}//求二次中間值，其下標(biāo)為jintj=Select((int)ceil((double)n/r/2),left,left+(n/r)-1,r);Swap(left,j);//二次中間值為樞紐元，并換至left處j=Partition(left,right);//對(duì)表（子表）進(jìn)行分劃操作if(k==j-left+1)returnj;//返回第k小元素下標(biāo)elseif(k<j-left+1)returnSelect(k,left,j-1,r);//在左子表求第k小元素elsereturnSelect(k-(j-left+1),j+1,right,r);//

在右子表求第

k-(j-left+1)

小元素}voidSortableList::InsertSort(intleft,intright){for(inti=left+1;i<=right;i++){intj=i;inttemp=l[i];while(j>left&&temp<l[j-1]){l[j]=l[j-1];j--;}l[j]=temp;}