算法分治策略

實驗報告2016/2017學年第二學期）課程名稱算法解析與設計實驗名稱分治策略實驗時間2017年3月30日指導單位計算機學院軟件工程系指導教師張怡婷學生姓名霍淇濱班級學號學院(系)計算機學院專業(yè)軟件工程實驗報告實驗名稱分治策略指導教師張怡婷實驗種類考據(jù)型（第4個實驗密實驗學時2實驗時間2017-3-30碼算法是“設計型”）一、實驗目的和任務理解分治法的算法思想，閱讀實現(xiàn)書上已有的部分程序代碼并完善程序，加深對分治法的算法原理及實現(xiàn)過程的理解二、實驗環(huán)境(實驗設備)VisualStudio2015三、實驗原理及內(nèi)容（包括操作過程、結(jié)果解析等）一、用分治法實現(xiàn)一組無序序列的兩路合并排序和快速排序。要求清楚合并排序及快速排序的基根源理，編程實現(xiàn)分別用這兩種方法將輸入的一組無序序列排序為有序序列后輸出。標頭.h#include<iostream>usingnamespacestd;classSortableList{public:SortableList(intmSize);~SortableList();voidInput();//輸入數(shù)組voidOutput();//輸出數(shù)組voidMergeSort();//兩路合并排序voidQuickSort();//快速排序private:int*l;//數(shù)組指針intmaxSize;//數(shù)組最大長度intn;//數(shù)組已有元素個數(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<<"

請輸入待排序的數(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"標頭.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）的線性時間選擇算法，找出N個元素會集S中的第k個最小的元素，使其在線性時間內(nèi)解決。標頭.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<<"請輸入帶排序的數(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小元素，其下標為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);//將每組的中間值交換到子表前部集中存放}//求二次中間值，其下標為jintj=Select((int)ceil((double)n/r/2),left,left+(n/r)-1,r);Swap(left,j);//二次中間值為樞紐元，并換至left處j=Partition(left,right);//對表（子表）進行分劃操作if(k==j-left+1)returnj;//返回第k小元素下標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;}