算法分治策略

1、实验报告（2016/2017学年第二学期）课程名称算法分析与设计实验名称分治策略实验时间2017年3月30日指导单位计算机学院软件工程系指导教师张怡婷学生姓名霍淇滨班级学号B15041236学院（系）计算机学院专业软件工程实验报告实验名称分治策略指导教师张怡婷实验类型验证型（第4个实验密 码算法是“设计型”）实验学时2实验时间2017-3-30实验目的和任务理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程序，加深对分 治法的算法原理及实现过程的理解二、实验环境（实验设备）Visual Studio 2015、实验原理及内容(包括操作过程、结果分析等)一、用分治法实现一组无序序列的两

2、路合并排序和快速排序。要求清楚合并排序及快速 排序的基本原理，编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后 输出。标头.h#in clude<iostream>using n amespace std;class SortableListpublic:SortableList(i nt mSize);SortableList();void In put();输入数组void Output(); 输出数组void MergeSort();两路合并排序void Quicksort。;/快速排序private:int *l;/数组指针int maxSize;/数组最大长度

3、int n;/ 数组已有元素个数void MergeSort(i nt left, int right);void Merge(int left, int mid, int right);void Swap( int i, i nt j);交换函数void QuickSort(int left, int right);分割函数int Pariti on (i nt left, int right);/;SortableList:SortableList(i nt mSize)maxSize = mSize;l = new in tmaxSize;n = 0;deletel;n"Sor

4、tableList:SortableList() void SortableList:I nput()cout << "请输入待排序的数组for (int 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); vo

5、id SortableList:QuickSort() Quicksort© 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(i nt left, int mid, int right)int *temp = new in tright

6、- left + 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

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

8、ft);if (i < j) Swap(i, j); while (i < j);Swap (left, j); return j;源.即p#in clude<iostream>#include"标头.h"using n amespace std;void mai n()int n = 10;SortableList my1( n);SortableList my2( n);my1 .In put();my2.l nput();my1.MergeSort();my2.QuickSort();my1.0utput();my2.0utput();二、采用

9、基于“五元中值组取中值分割法” (median-of-median-of-fivepartitioning )的线性 时间选择算法，找出N个元素集合S中的第k个最小的元素，使其在线性时 间内解决。标头.h#in clude<iostream>using n amespace std;enum ResultCode OutOfBo un ds,Success;class SortableListpublic:SortableList(i nt mSize);SortableList();void In put();void Output();ResultCode Select(i n

10、t &x, i nt k); private:int *l;int maxSize;int n;void Swap(i nt i, i nt j);void In sertSort(i nt left, int right);int Partiti on (i nt left, int right);int Select(i nt k,i nt left,i nt right, int r); ;SortableList:SortableList(i nt mSize)maxSize = mSize;l = new in tmaxSize;n = 0;deletel;n"So

11、rtableList:SortableList()void SortableList:I nput()cout << "请输入带排序的数组for (int 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 =

12、 lj;lj = c; int SortableList:Partiti on (i nt 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 &l

13、t;= 0)return OutOfBou 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小元素，其下标为left+k-1for (i nt i = 1; i <= n / r; i+)I

14、n sertSort(left + (i - 1)*r, left + i*r - 1); /二次取中规则求每组的中间值Swap(left + i - 1, left + (i - 1)*r + (in t)ceil(double)r / 2) - 1); /将每组的中间值交换到子表前部集中存放/求二次中间值，其下标为jint j = Select(int)ceil(double)n / r / 2), left, left + (n / r) - 1, r);Swap (left, j); /二次中间值为枢纽元，并换至left处j = Partiti on( left, right); /对

15、表(子表)进行分划操作if (k = j - left + 1)return j; / 返回第k小元素下标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:l nsertSort(i nt left, i nt right)for (i nt i = left+1; i <= right; i+)int j = i;int temp = li;while (j > left && temp < lj - 1)lj = lj