算法分治策略

1、實(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)類型驗(yàn)證型（第4個(gè)實(shí)驗(yàn)密 碼算法是“設(shè)計(jì)型”）實(shí)驗(yàn)學(xué)時(shí)2實(shí)驗(yàn)時(shí)間2017-3-30實(shí)驗(yàn)?zāi)康暮腿蝿?wù)理解分治法的算法思想，閱讀實(shí)現(xiàn)書上已有的部分程序代碼并完善程序，加深對(duì)分治法的算法原理及實(shí)現(xiàn)過程的理解二、實(shí)驗(yàn)環(huán)境（實(shí)驗(yàn)設(shè)備）Visual Studio 2015三、實(shí)驗(yàn)原理及內(nèi)容（包括操作過程、結(jié)果分析等）一、用分治法實(shí)現(xiàn)一組無序序列的兩路合并排序和

2、快速排序。要求清楚合 并排序及快速排序的基本原理，編程實(shí)現(xiàn)分別用這兩種方法將輸入的一組 無序序列排序?yàn)橛行蛐蛄泻筝敵觥?biāo)頭.h#in clude<iostream>using n amespace std;class SortableListpublic:SortableList(i nt mSize);SortableList();void In put();輸入數(shù)組void Output。;/ 輸岀數(shù)組void MergeSort();/兩路合并排序void Quicksort。;/快速排序private:int *l;/數(shù)組指針int maxSize;/數(shù)組最大長(zhǎng)度int n

3、;/數(shù)組已有元素個(gè)數(shù)void MergeSort(int left, int right);void Merge(int left, int mid, int right);void Swap(i nt i, i nt j);/交換函數(shù)void QuickSort(int left, int right);int Paritio n(i nt left, i nt right);/分割函數(shù);SortableList:SortableList(int mSize)maxSize = mSize;l = new in tmaxSize;n = 0;SortableList:SortableList

4、() deletel;void SortableList:I nput()cout << "請(qǐng)輸入待排序的數(shù)組n"for (i nt i = 0; i < maxSize; i+)cin >> li;if (li = -1)break;n+;void SortableList:Output()for (i nt i = 0; i < n; i+)cout << li << ""void SortableList:MergeSort() MergeSort(0, n - 1); void Sort

5、ableList:QuickSort() QuickSort(O, n - 1); void SortableList:MergeSort(int left, int right) if (left < right)int mid = (left + right) / 2;MergeSort(left, mid);MergeSort(mid + 1, right); Merge(left, mid, right);void SortableList:Merge(int left, int mid, int right)int *temp = new in tright - left +

6、1;int i = left, j = mid + 1, k = 0;while (i <= mid) && (j <= right)if (li <= lj) tempk+ = li+; else tempk+ = lj+;while (i <= mid) tempk+ = li+;while (j <= right) tempk+ = lj+;for (i = 0, k = left; k <= right;)lk+ = tempi+; void SortableList:Swap(i nt i, i nt j)int c = li;li

7、 = lj;lj = c;void SortableList:QuickSort(int left, int right)if (left < right)int j = Pariti on (left, right);QuickSort(left, j - 1); QuickSort(j + 1, right);int SortableList:Parition(int left, int right)int i = left, j = right + 1;dodo i+; while (li < lleft);do j-; while (lj > lleft);if (i

8、 < j) Swap(i, j); while (i < j);Swap(left, j);return j;源.app#in clude<iostream>#include"標(biāo)頭.h"using n amespace std;void mai n()int n = 10;SortableList my1( n);SortableList my2( n);my1.l nput();my2.l nput();my1.MergeSort();my2.QuickSort();my1.Output();my2.Output();二、采用基于“五元中值組取中值

9、分割法”(media n-of-media n-of-fivepartitioning)的線性 時(shí)間選擇算法，找出N個(gè)元素集合S中的第k個(gè)最 小的元素，使其在線性時(shí)間內(nèi)解決。標(biāo)頭.h#in clude<iostream>using n amespace std;enum ResultCode OutOfBou nds,Success;class SortableListpublic:SortableList(i nt mSize);SortableList();void In put();void Output();ResultCode Select(i nt &x, i

10、nt k); private:int *l;int maxSize;int n;void Swap(i nt i, i nt j);void InsertSort(int left, int right); int Partition(int left, int right);int Select(i nt k,i nt left,i nt right, int r);SortableList:SortableList(int mSize)maxSize = mSize;l = new in tmaxSize;n = 0;SortableList:SortableList() deletel;

11、 void SortableList:I nput()cout << "請(qǐng)輸入帶排序的數(shù)組n"for (i nt i = 0; i < maxSize; i+) cin >> li;if (li = -1)break;n+;void SortableList:Output()for (i nt i = 0; i < n; i+) cout << li << ""void SortableList:Swap(i nt i, i nt j)int c = li;li = lj;lj = c;int

12、SortableList:Partition(int left, int right)int i = left, j = right + 1;dodo i+; while (li < lleft);do j-; while (lj > lleft);if (i < j) Swap(i, j); while (i < j);Swap(left, j);return j;ResultCode SortableList:Select(i nt &x, i nt k)if (n <= 0 | k > n | k <= 0)return OutOfBou

13、 nds;int j = Select(k, 0,n - 1,5);x = lj;retur n Success;int SortableList:Select(i nt k, int left, int right, i nt r)int n = right - left + 1;if (n <= r) /若問題足夠小，使用直接插入排序In sertSort(left, right);return left + k - 1; /取其中的第k小元素，其下標(biāo)為left+k-1for (i nt i = 1; i <= n / r; i+)In sertSort(left + (i -

14、 1)*r, left + i*r - 1); /二次取中規(guī)則求每組的中間值Swap(left + i - 1, left + (i - 1)*r + (in t)ceil(double)r / 2) - 1); /將每組的中間值交換到子表前部集中存放/求二次中間值，其下標(biāo)為jint j = Select(int)ceil(double)n / r / 2), left, left + (n / r) - 1, r);Swap(left, j); / 二次中間值為樞紐元，并換至left處j = Partiti on( left, right); /對(duì)表(子表)進(jìn)行分劃操作if (k = j -

15、 left + 1)return j; / 返回第k小元素下標(biāo)else if (k<j - left + 1)return Select(k, left, j - 1, r);/在左子表求第 k小元素else return Select(k - (j - left + 1), j + 1, right, r); /在右子表求第 k-(j-left+1) 小元素void SortableList:InsertSort(int left, int right)for (int i = left+1; i <= right; i+)int j = i;int temp = li;while (j > left && temp < lj - 1)lj = lj - 1; j-;