算法设计与分析实验报告模板

1、实验报告（ 2016/2017 学年 第一学期）课程名称算法分析与设计实验名称分治策略实验时间2016年10月18日指导单位计算机学院软件教学中心指导教师季一木学生姓名周文超班级学号B14041527学院 ( 系)计算机学院、专业软件工程软件学院实验报告实验名称分治策略指导教师季一木实验类型验证实验学时2实验时间一、实验目的和任务1. 理解分治法的算法思想， 阅读实现书上已有的部分程序代码并完善程序，加深对分治法的算法原理及实现过程的理解。2. 用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理， 编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后

2、输出。二、实验环境 ( 实验设备 )算法设计与分析课本笔记本电脑VC+6.0三、实验原理及内容 （包括操作过程、结果分析等）实验原理运用分治法：无序 - 部分有序 - 整体有序归并排序中“分”与“合”的过程是结合在一起的， 即每一趟都在做 “分”与“合”的工作，并不是先“分”完再“合”基本程序（一）两路合并排序#includeclass SortableListpublic:SortableList(int mSize) / 构造函数maxSize = mSize;l = new intmaxSize;n = 0;SortableList()deletel; / void Input();析构

3、函数void Merge(int left,int mid,int right);void MergeSort();void MergeSort(int left,int right);void Output();private:int *l; /动态生成一维数组int maxSize; /线性表的最大表长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

4、;int i = left,j = 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，则划分成两个子序列i

5、nt mid = (left+right)/2;/将待排序的序列一分为二MergeSort(left,mid);/对左序列排序MergeSort(mid+1,right);/对右序列排序Merge(left,mid,right);/将两个有序子序列合并成一个有序序列void SortableList:Output()for(int i = 0;imaxSize;i+)coutli ;void main()SortableList l(10);cout 请输入 10 个数： endl;l.Input();l.MergeSort();cout 排序后是： endl;l.Output();（二）快速

6、排序#includeclass SortableListpublic:SortableList(int mSize) / 构造函数maxSize = mSize;l = new intmaxSize;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 m

7、axSize; /线性表的最大表长int n; /线性表的实际长度;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=right int i = left,j = right + 1;dodo i+;while(lilleft);if(ij)Swap(i,j);while(ij);Swap(left,j);retur

8、n j;void SortableList:QuickSort()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;imaxSize;i+)coutli ;void main()SortableList l(10);cout 请输入 10 个数： endl;l.Input();l.QuickSort();cout 排序后是： endl;l.Output();实验结果两路合并排序快速排序六、实验小结 （包括问题和解决方法、心得体会等）合并排序的基