《分治法实现一组无序序列的两路合并排序和快速排序.pdf》由会员分享，可在线阅读，更多相关《分治法实现一组无序序列的两路合并排序和快速排序.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实实 验验 报报 告告（2011/20122011/2012 学年学年 第一学期）第一学期）课程名称实验名称实验时间指导单位指导教师学生姓名学院(系)班级学号专业算法分析与设计A分治策略年月日计算机学院软件工程系实实 验验 报报 告告实验名称实验名称实验类型实验类型验证分治策略实验学时实验学时2指导教师指导教师实验时间实验时间一、一、 实验目的和任务实验目的和任务理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程序，加深对分治法的算法原理及实现过程的理解。用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理， 编程实现分别用这两种方法将输入的一组无序
2、序列排序为有序序列后输出。二、二、 实验环境实验环境( (实验设备实验设备) )VC+6.01三、实验原理及内容三、实验原理及内容（包括操作过程、结果分析等）实验原理实验原理1、排序是数据处理中常用的重要手段，是指将一个元素序列调整为按指定关键字值的递增（或递减）次序排列的有序序列。用分治法求解排序问题的思路是，按某种方式将序列分成两个或多个子序列，分别进行排序，再将已排序的子序列合并成一个有序序列。合并排序和快速排序是两种典型的符合分治策略的排序算法。2、如果采用顺序存储的可排序表作为算法实现的数据结构，则需要定义一个可排序表类 SortableList，两路合并算法和快速排序算法均由定义在
3、该类上的函数实现。其中Input 函数和 Output 函数分别用于向可排序表中输入待排序序列，以及输出已经排序好的序列。3、两路合并排序算法的基本思想是：将待排序元素平分成大小大致相同的两个子序列，然后对每个子序列分别使用递归的方法进行两路合并排序，直到子序列长度变为1，最后利用合并算法将得到的已排序好的两个子序列合并成一个有序的序列。两路合并排序算法的核心部分是将子问题的解组合成原问题解得合并操作。常用的操作是新建一个序列，序列的大小等于要合并的两个子序列的长度之和。比较两个子序列中的最小值，输出其中较小者到新建的序列中，重复此过程直到其中一个子序列为空。如果另一个子序列中还有元素未输出，
4、则将剩余元素依次输出到新建序列中即可。最终得到一个有序序列。4、 结合书上已有的程序代码， 使用分治法的快速排序算法， 实现对初始序列的排序。快速排序算法的基本思想是：（1）在待排序序列 Kleft:right上选择一个基准元素（通常是最左边的元素 Kleft） ，通过一趟分划操作将序列分成左右两个子序列，左子序列中所有元素都小于等于该基准元素，有子序列中所有元素都大于等于该基准元素。则当前基准元素所在的位置位于左、右子序列的中间，即是其排序完成后的最终位置。（2）通过递归调用，对左子序列和右子序列再分别进行快速排序算法的调用。（3）由于每一趟分划结束后，左子序列中的元素均不大于基准元素，右子
5、序列中的元素均不小于基准元素。而每次分划后，对分划得到的左、右子序列的快速排序又均是就地进行，所以一旦左、右两个子序列都已分别排好序后，无需再执行任何计算，整个序列就是所要求的有序序列了。因此类中应定义成员函数 QuickSort 来完成递归快速排序算法的调用和成员函数5、比较合并排序和两种算法的异同。问题分解过程： 合并排序将序列一分为二即可。 （十分简单） 快速排序需调用 Partition 函数将一个序列划分为子序列。 （分解方法相对较困难）子问题解合并得到原问题解的过程：合并排序需要调用 Merge 函数来实现。 （Merge 函数时间复杂度为 O(n)）.快速排序一旦左、右两个子序列
6、都已分别排序，整个序列便自然成为有序序列。（异常简单， 几乎无须额外的工作， 省去了从子问题解合并得到原问题解的过程）基本程序基本程序（一）两路合并排序#includeclass SortableList2public:SortableList(int mSize)maxSize=mSize;l=new intmaxSize;n=0;SortableList()delete l;void MergeSort();void Input();void Output();private:int *l;int maxSize;int n;void MergeSort(int left,int righ
7、t);void Merge(int left,int mid,int right);void SortableList:MergeSort()MergeSort(0,n-1);void SortableList:MergeSort(int left,int right)if (leftright)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=ne
8、w intright-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:Input()for(int i=0;ili;3n+;void SortableList:Output()for(int i=0;imaxSize;i+)coutli ;coutend
9、l;void main()SortableList l(10);cout请输入 10 个数：endl;l.Input();l.MergeSort();l.Output();（二）快速排序#includeclass SortableListpublic:SortableList(int mSize)maxSize=mSize;l=new intmaxSize;n=0;SortableList()delete l;void QuickSort();void Input();void Output();private:int *l;int maxSize;int n;void Swap(int i,
10、int j);void QuickSort(int left,int right);4int Partition(int left,int right);void SortableList:Swap(int i,int j)int c=li;li=lj;lj=c;int SortableList:Partition(int left,int right)int i=left,j=right+1;dodo i+; while (lilleft);if (ij) Swap(i,j);while (ij);Swap(left,j);return j;void SortableList:QuickSo
11、rt()QuickSort(0,n-1);void SortableList:QuickSort(int left,int right)if (leftright)int j=Partition(left,right);QuickSort(left,j-1);QuickSort(j+1,right);void SortableList:Input()for(int i=0;ili;n+;5void SortableList:Output()for(int i=0;imaxSize;i+)coutli ;coutendl;void main()SortableList x(10);cout请输入 10 个数：endl;x.Input();x.QuickSort();x.Output();实验结果实验结果两路合并排序6快速排序7四、实验小结四、实验小结（包括问题和解决方法、心得体会等）五、指导教师评语五、指导教师评语成成绩绩批阅人批阅人日日期期8