实 验 报 告
（2013/2014学年 第一学期）
课程名称 实验名称 实验时间 指导单位 指导教师
学生姓名 学院(系) 计算机软件 班级学号 专 业 软件工程 2015 算法分析与设计 分治策略 年 3 月 31 日 计算机学院软件工程系 张怡婷
实 验 报 告
实验名称 实验类型 分治策略 实验学时 2 指导教师 实验时间 张怡婷 2009-10-11 一、 实验目的和任务 实验目的：理解分治法的算法思想，阅读实现书上已有的部分代码并完善程序，加深对分治法的算法原理及实现过程的理解。 实验任务： 用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理， 编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。 二、 实验环境(实验设备) VC++ 6.0 1
三、实验原理及内容（包括操作过程、结果分析等） 实验原理： 分治法求解的三要素：1.问题能够按照某种方式分解成若干个规模较小的.相互独立且与原问题类型相同的子问题；2.子问题足够小时可以直接求解；3.能够将子问题的解组合成原问题的解。 两路合并排序算法的基本思想是：将待排序元素平分成大小大致相同的两个子序列，然后对每个子序列分别使用递归的方法进行两路合并排序，直到子序列长度变为 1，最后利用合并算法将得到的已排序好的两个子序列合并成一个有序的序列。两路合并排序算法的核心部分是将子问题的解组合成原问题解得合并操作。常用的操作是新建一个序列，序列的大小等于要合并的两个子序列的长度之和。比较两个子序列中的最小值，输出其中较小者到新建的序列中，重复此过程直到其中一个子序列为空。如果另一个子序列中还有元素未输出，则将剩余元素依次输出到新建序列中即可。最终得到一个有序序列。 快速排序算法的基本思想是： （ 1） 在待排序序列 K[left:right]上选择一个基准元素（通常是最左边的元素 Kleft），通过一趟分划操作将序列分成左右两个子序列，左子序列中所有元素都小于等于该基准元素，有子序列中所有元素都大于等于该基准元素。则当前基准元素所在的位置位于左、右子序列的中间，即是其排序完成后的最终位置。 （ 2）通过递归调用，对左子序列和右子序列再分别进行快速排序算法的调用。 2
（ 3）由于每一趟分划结束后，左子序列中的元素均不大于基准元素， 右子序列中的元素均不小于基准元素。而每次分划后，对分划得到的左、右子序列的快速排序又均是就地进行，所以一旦左、右两个子序列都已分别排好序后，无需再执行任何计算， 整个序列就是所要求的有序序列了。 实验内容： 1、 排序是数据处理中常用的重要手段，是指将一个元素序列调整为按指定关键字值的递增（或递减）次序排列的有序序列。用分治法求解排序问题的思路是，按某种方式将序列分成两个或多个子序列，分别进行排序，再将已排序的子序列合并成一个有序序列。合并排序和快速排序是两种典型的符合分治策略的排序算法。 2、 如果采用顺序存储的可排序表作为算法实现的数据结构，则需要定义一个可排序表类SortableList，两路合并算法和快速排序算法均由定义在该类上的函数实现。 class SortableList { public: SortableList(int mSize){ maxSize=mSize; l=new int[maxSize]; n=0; //数组中已有元素个数 } ~SortableList(){ 3
delete []l;} void SortableList::Input(); void SortableList::Output(); void QuickSort(); private: void Swap(int i,int j); void QuickSort(int left,int right); int Partition(int left,int right);};int *l; int maxSize; int n; }; 部分关键代码： 1.两路合并排序： void SortableList::MergeSort(int left,int right) { if(left }