1、-. z.實驗報告（2016/2017學年 第一學期）課程名稱算法分析與設計實驗名稱分治策略實驗時間2016年10月18日指導單位計算機學院軟件教學中心指導教師季一木學生周文超班級*B14041527學院(系)計算機學院、軟件學院專 業軟件工程-. z.實 驗 報 告實驗名稱分治策略指導教師季一木實驗類型驗證實驗學時2實驗時間實驗目的和任務1.理解分治法的算法思想，閱讀實現書上已有的部分程序代碼并完善程序，加深對分治法的算法原理及實現過程的理解。 2.用分治法實現一組無序序列的兩路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理，編程實現分別用這兩種方法將輸入的一組無序序列排序為有序序

2、列后輸出。 實驗環境(實驗設備)算法設計與分析課本筆記本電腦 VC+6.0三、實驗原理及容（包括操作過程、結果分析等）實驗原理運用分治法 ：無序-部分有序-整體有序歸并排序中分”與合”的過程是結合在一起的，即每一趟都在做分” 與合”的工作，并不是先分”完再合” 基本程序兩路合并排序#includeclass SortableListpublic:SortableList(int mSize) /構造函數ma*Size = mSize;l = new intma*Size;n = 0;SortableList()deletel; /析構函數void Input();void Merge(int

3、left,int mid,int right);void MergeSort();void MergeSort(int left,int right);void Output();private:int *l; /動態生成一維數組int ma*Size; /線性表的最大表長int n; /線性表的實際長度;void SortableList:Input()for(int i = 0;ili;n+;void SortableList:Merge(int left,int mid,int right)int *temp = new intright-left+1;int i = left,j =

4、mid +1,k = 0;while(i=mid)&(j=right)if(li=lj)tempk+=li+;elsetempk+=lj+;while(i=mid)tempk+=li+;while(j=right)tempk+=lj+;for(i = 0,k=left;k=right;)lk+=tempi+;void SortableList:MergeSort()MergeSort(0,n-1);void SortableList:MergeSort(int left,int right)if(leftright)/若序列的長度超過1，則劃分成兩個子序列int mid = (left+rig

5、ht)/2;/將待排序的序列一分為二MergeSort(left,mid);/對左序列排序 MergeSort(mid+1,right);/對右序列排序Merge(left,mid,right);/將兩個有序子序列合并成一個有序序列void SortableList:Output()for(int i = 0;ima*Size;i+)coutli ;void main()SortableList l(10);cout請輸入10個數：endl;l.Input();l.MergeSort();cout排序后是：endl;l.Output();（二）快速排序#includeclass Sortabl

6、eListpublic:SortableList(int mSize) /構造函數ma*Size = mSize;l = new intma*Size;n = 0;SortableList()deletel; /析構函數void Input();void Swap(int i,int j);int Partition(int left,int right);void QuickSort(int left,int right);void QuickSort();void Output();private:int *l; /動態生成一維數組int ma*Size; /線性表的最大表長int n;

7、/線性表的實際長度;void SortableList:Input()for(int i = 0;ili;n+;void SortableList:Swap(int i,int j)int c = li;li = lj;lj = c;int SortableList:Partition(int left,int right)/前置條件：left=rightint i = left,j = right + 1; dodo i+;while(lilleft);if(ij)Swap(i,j);while(ij);Swap(left,j);return j;void SortableList:Quic

8、kSort()QuickSort(0,n-1);void SortableList:QuickSort(int left,int right)if(leftright) /當序列長度大于1時，需進行分割int j = Partition(left,right);/對left,right圍的序列進行分劃QuickSort(left,j-1);/對左子序列實施快速排序QuickSort(j+1,right);/對右子序列實施快速排序void SortableList:Output()for(int i = 0;ima*Size;i+)coutli ;void main()SortableList l(10);cout請輸入10個數：endl;l.Input();l.QuickSort();cout排序后是：endl;l.Output();實驗結果兩路合并排序快速排序六、實驗小結（包括問題和解決方法、心得體會等） 合并排序的基本運算是把兩