算法設(shè)計與分析試驗報告

1、算法設(shè)計與分析實驗報告（2016/2017學(xué)年第一學(xué)期）課程名稱算法分析與設(shè)計實驗名稱分治策略實驗時間2016年 10 月 18日指導(dǎo)單位計算機學(xué)院軟件教學(xué)中心指導(dǎo)教師季一木學(xué)生姓名周文超班級學(xué)號B學(xué)院（系）計算機學(xué)院、 軟件學(xué)院專業(yè)軟件工程實驗報告實驗名稱分治策略指導(dǎo)教師季一木實驗類型驗證實驗學(xué)時2實驗時間一、 實驗?zāi)康暮腿蝿?wù)1.理解分治法的算法思想，閱讀實現(xiàn)書上已有的部分程序代碼并完善程序， 加深對分治法的算法原理及實現(xiàn)過程的理解。2.用分治法實現(xiàn)一組無序序列的兩路合并排序和快速排序。要求清楚合并 排序及快速排序的基本原理，編程實現(xiàn)分別用這兩種方法將輸入的一組無序序列 排序為有序序列后輸出

2、。二、實驗環(huán)境（實驗設(shè)備） 算法設(shè)計與分析課本 筆記本電腦VC+三、實驗原理及內(nèi)容(包括操作過程、結(jié)果分析等)實驗原理運用分治法：無序-部分有序-整體有序歸并排序中“分”與“合”的過程是結(jié)合在一起的，即每一趟都在做“分” 與“合”的工作，并不是先“分”完再“合”基本程序(一)兩路合并排序ftincludeOclass SortableListpublic:SortableList (int mSize) /構(gòu)造函數(shù)maxSize 二 mSize;1 二 new intmaxSizeJ:n = 0;SortableList () delete J 1; /析構(gòu)函數(shù)void Input ():vo

3、id Merge(int left, int mid, int right):void MergeSort();void MergeSort(int left, int right):void Output ();private:int *1; 動態(tài)生成一維數(shù)組int maxSize: /線性表的最大表長int n; /線性表的實際長度；void SortableList:Input()for (int i 二 0;i<maxSize;i+)cin>>l i;n+;void SortableList:Merge(int left, int mid, int right) in

4、t *temp 二 new intrightleft+1;int i = left, j = mid +1, k = 0;while(i<=mid)&&(j<=right)tempk+=li+;elsetempk+二1j+;while (i<=mid)tempk+=1i+;while (j<=right)tempk+=lj+;for (i = 0,k=left;k<=right;)1 k+=tempi+;void SortableList:MergeSort()MergeSort (0, nT);void SortableList:MergeSor

5、t(int left,int right)if (left<right) /若序列的長度超過1,則劃分成兩個子序列 int mid = (left+right)/2;/將待排序的序列一分為二 MergeSort (left, mid) ;/對左序列排序MergeSort (mid+1, right) ;/對右序列排序Merge (left, mid, right) ;/將兩個有序子序列合并成一個有序序列 void SortableList:Output()for (int i = 0;i<maxSize;i+) cout«l i <<，z”；void main

6、() SortableList 1 (10);cout«，z請輸入 10 個數(shù)："«endl;0;0;cout«，/排序后是：，«endl;0;(二)快速排序itincludeOclass SortableListpublic:SortableList (int mSize) /構(gòu)造函數(shù)maxSize = mSize;1 = new intmaxSize;n = 0;SortableList() delete 1; /析構(gòu)函數(shù)void Input ();void Swap(int i, int j);int Partition(int left

7、,int right);void Quicksort(int left, int right);void Quicksort ();void Output ();private:int *1; 動態(tài)生成一維數(shù)組int maxSize; 線性表的最大表長int n; /線性表的實際長度；void SortableLis t: Input ()for (int i 二 0;i<maxSize;i+)cin>>l i;n+;void SortableList： :Swap(int i, int j) int c = 1 i;li = lj；lj = c;int SortableLi

8、st：:Partition(int left, int right)/前置條件：left<=rightint i 二 left, j 二 right + 1:do do i+;while(1i<1left);do j-;while(1j>1left);if (i<j)Swap(i, j);while (i<j);Swap(left, j);return j;void SortableList：:Quicksort()Quicksort(0, nl);void SortableList：:Quicksort(int left,int right) if(left&l

9、t;right)當(dāng)序列長度大于1時，需進(jìn)行分割int j = Partition(left, right) ;/對left, right范圍內(nèi)的序列進(jìn)行分劃Quicksort (left, j-1) ;/對左子序列實施快速排序 Quicksort (j+1, right) ;/對右子序列實施快速排序 void SortableList:Output()for (int i = 0; KmaxSize; i+) cout«l i <<，z”；void main () SortableList 1 (10); cout<"請輸入 10 個數(shù):"<<endl; 0;0;cout«，/排序后是:，«endl;0;實驗結(jié)果兩路合并排序快速排序六、實驗小結(jié)（包括問題和解決方法、心得體