算法分治策略

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)b15041236學(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)過(guò)程的理解二、 實(shí)驗(yàn)環(huán)境(實(shí)驗(yàn)設(shè)備)visual studio 2015三、實(shí)驗(yàn)原理及內(nèi)容（包括操作過(guò)程、結(jié)果分析等）一、用

2、分治法實(shí)現(xiàn)一組無(wú)序序列的兩路合并排序和快速排序。要求清楚合并排序及快速排 序的基本原理，編程實(shí)現(xiàn)分別用這兩種方法將輸入的一組無(wú)序序列排序?yàn)橛行蛐蛄泻筝敵?。?biāo)頭.h#includeusing namespace std;class sortablelistpublic:sortablelist(int msize);sortablelist();void input();/輸入數(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(int i, int j);/交換函數(shù)void quicksort(int left, int right);int parition(int left, int right);/分割函數(shù);sortablelist:sortablelist(int msize)maxsize = msize;l = new intmaxsize;n = 0;sortablelist:sortablelist()dele

4、tel;void sortablelist:input()cout 請(qǐng)輸入待排序的數(shù)組n;for (int i = 0; i li;if (li = -1)break;n+;void sortablelist:output()for (int i = 0; i n; i+)cout li ;void sortablelist:mergesort() mergesort(0, n - 1); void sortablelist:quicksort() quicksort(0, n - 1); void sortablelist:mergesort(int left, int right)if (

5、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 intright - left + 1;int i = left, j = mid + 1, k = 0;while (i = mid) & (j = right)if (li = lj) tempk+ = li+;else tempk+

6、= lj+;while (i = mid) tempk+ = li+;while (j = right) tempk+ = lj+;for (i = 0, k = left; k = right;)lk+ = tempi+;void sortablelist:swap(int i, int j)int c = li;li = lj;lj = c;void sortablelist:quicksort(int left, int right)if (left right)int j = parition(left, right);quicksort(left, j - 1);quicksort(

7、j + 1, right);int sortablelist:parition(int left, int right)int i = left, j = right + 1;dodo i+; while (li lleft);if (i j) swap(i, j); while (i j);swap(left, j);return j;源.app#include#include標(biāo)頭.husing namespace std;void main()int n = 10;sortablelist my1(n);sortablelist my2(n);my1.input();my2.input()

8、;my1.mergesort();my2.quicksort();my1.output();my2.output(); 二、采用基于“五元中值組取中值分割法”（median-of-median-of-five partitioning）的線性 時(shí)間選擇算法，找出 n 個(gè)元素集合 s 中的第 k個(gè)最小的元素，使其在線性時(shí)間內(nèi)解決。標(biāo)頭.h#includeusing namespace std;enum resultcode outofbounds,success;class sortablelistpublic:sortablelist(int msize);sortablelist();voi

9、d input();void output();resultcode select(int &x, int k);private:int *l;int maxsize;int n;void swap(int i, int j);void insertsort(int left, int right);int partition(int left, int right);int select(int k,int left,int right,int r);sortablelist:sortablelist(int msize)maxsize = msize;l = new intmaxsize;

10、n = 0;sortablelist:sortablelist()deletel;void sortablelist:input()cout 請(qǐng)輸入帶排序的數(shù)組n;for (int i = 0; i li;if (li = -1)break;n+;void sortablelist:output()for (int i = 0; i n; i+)cout li ;void sortablelist:swap(int i, int j)int c = li;li = lj;lj = c;int sortablelist:partition(int left, int right)int i =

11、left, j = right + 1;dodo i+; while (li lleft);if (i j) swap(i, j); while (i j);swap(left, j);return j;resultcode sortablelist:select(int &x, int k)if (n n | k = 0)return outofbounds;int j = select(k, 0,n - 1, 5);x = lj;return success;int sortablelist:select(int k, int left, int right, int r)int n =

12、right - left + 1;if (n = r) /若問(wèn)題足夠小，使用直接插入排序 insertsort(left, right);return left + k - 1; /取其中的第k小元素，其下標(biāo)為left+k-1 for (int i = 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); /將每組的中間值交換到子表前部集中存放/求二次中間值，

13、其下標(biāo)為j int j = 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)return j; /返回第k小元素下標(biāo) else if (kj - 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 left & temp lj - 1)lj = lj - 1; j-;lj = temp;源.