南京邮电大学算法实验报告.docx

《南京邮电大学算法实验报告.docx》由会员分享，可在线阅读，更多相关《南京邮电大学算法实验报告.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告（2013/2014学年第一学期）课程名称算法分析与设计实验名称分治策略实验时间2015年3月31日指导单位计算机学院软件工程系指导教师张怡婷将该下标处的元素Kj和原有的主元Kleft交换，然后照常调用原有的学生姓名班级学号学院（系）计算机软件专 业软件工程Partition函数即可。void SortableList: QuickSort(int left,mt right)if (leftright)(int j=RandomizedPartition(left,right); /RandomizedPartition 函数 QuickSort(leftJ-1);QuickSort

2、(j+l,right);)int SortableList:RandomizedPartition(int left9 int right) srand( (imsigned)time(NULL); 用当前时间作为种子int i=rand()%(rightleft)+left; 产生一个 left-right 范围内的随机数Swap(ijeft);return Partition(left, right); 调用 Partition 函数)四、实验小结（包括问题和解决方法、心得体会等）通过对分治法的具体应用，在具体的算法和时间复杂度的比照下，更深层的理解分 治法的策略，划小组合取有序，将复杂的

3、问题分解成假设干个小问题求解，虽然有具体的 算法指导，但是在理解上自己还是应该多去琢磨一下。五、指导教师评语10成绩批阅人日期实验报告实验名称分治策略指导教师张怡婷实验类型实验学时 2实验时间2009-10-11一、实验目的和任务实验目的：理解分治法的算法思想，阅读实现书上已有的局部 代码并完善程序，加深对分治法的算法原理及实现过程的理解。实验任务：用分治法实现一组无序序列的两路合并排序和快速 排序。要求清楚合并排序及快速排序的基本原理，编程实现分别 用这两种方法将输入的一组无序序列排序为有序序列后输出。二、实验环境（实验设备）VC+ 6.0三、实验原理及内容(包括操作过程、结果分析等)实验原

4、理：分治法求解的三要素：1.问题能够按照某种方式分解成假设干个规模较小 的.相互独立且与原问题类型相同的子问题；2.子问题足够小时可以直接求 解；3.能够将子问题的解组合成原问题的解。两路合并排序算法的基本思想是:将待排序元素平分成大小大致相同的两个子序列，然后对每个子序列分别使用递归的方法进行两路合并排序，直 到子序列长度变为1,最后利用合并算法将得到的已排序好的两个子序列合 并成一个有序的序列。两路合并排序算法的核心局部是将子问题的解组合成 原问题解得合并操作。常用的操作是新建一个序列，序列的大小等于要合并 的两个子序列的长度之和。比拟两个子序列中的最小值，输出其中较小者到 新建的序列中，

5、重复此过程直到其中一个子序列为空。如果另一个子序列中 还有元素未输出，那么将剩余元素依次输出到新建序列中即可。最终得到一个 有序序列。快速排序算法的基本思想是:(1)在待排序序列Kleft:right上选择一个基准元素(通常是最左边的元素Kleft),通过一趟分划操作将序列分成左右两个子序列，左子序 列中所有元素都小于等于该基准元素，有子序列中所有元素都大于等于该基 准元素。那么当前基准元素所在的位置位于左、右子序列的中间，即是其排序 完成后的最终位置。(2)通过递归调用，对左子序列和右子序列再分别进行快速排序算法的调用。(3)由于每一趟分划结束后，左子序列中的元素均不大于基准元素, 右子序列

6、中的元素均不小于基准元素。而每次分划后，对分划得到的左、右 子序列的快速排序又均是就地进行，所以一旦左、右两个子序列都已分别排 好序后，无需再执行任何计算，整个序列就是所要求的有序序列了。实验内容:1、排序是数据处理中常用的重要手段，是指将一个元素序列调整为按指定关键字值的递增(或递减)次序排列的有序序列。用分治法求解排序问 题的思路是，按某种方式将序列分成两个或多个子序列，分别进行排序，再 将已排序的子序列合并成一个有序序列。合并排序和快速排序是两种典型的 符合分治策略的排序算法。2、如果采用顺序存储的可排序表作为算法实现的数据结构，那么需要定义一个可排序表类SortableList,两路合

7、并算法和快速排序算法均由定义在 该类上的函数实现。class SortableList public:SortableList(int mSize)maxSize=mSize;l=new intmaxSize;n=0;数组中已有元素个数)-SortableList()delete 1; void SortableList:Input();void SortableList:Output();void QuickSortQ;private:void Swap(int i,int j);void QuickSort(int left?int right);int Partition(int lef

8、tnt right);int *1;int maxSize;int n;)；局部关键代码:1 .两路合并排序:void SortableList: :MergeSort(int left,int right)if(leftright)假设序列的长度大于1,划分为2个子序列int mid=(left+right)/2;将待排序列一分为二MergeSort(left,mid); 对左子序列排序MergeSort(mid+1,right); 对右子序列排序Merge(left,mid,right); 将两个有序序列合并成一个有序序列void SortableList: :Merge(int left

9、5int mid,int right)将两个有序子序列合并 int *temp=new intright-left+l;int i=leftj=mid+l,k=O;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=05k=left;k=right;)lk+=tempi+;排序结果: (All nlnhal members a mainn F:B1 3041403Debug1*im.exen5个无序数: 62 0际输入3

10、6 9B36any key to cont nue62 Press.快速排序:int SortableList: :Partition(int left?int right)化函数int i=leftj=right+l;以主元为中心分成左右子序列dodo i+; while (lilleft);if (ij) Swap(ij);交换两个元素Jwhile (ij);Swap(leftJ);return j; 返回分划分点void SortableList: QuickSort()QuickSort(09n-1);void SortableList:QuickSort(int left,int r

11、ight)if (leftvright)假设序列的长度大于1,划分为2个子序列int j=Partition(left,right); 对left,right范围内的序列进行分化QuickSort(leftjl);对左子序列实施快速排序QuickSort(j+l,right); 对右子序列实施快速排序排序结果:* qq并 classes y j /思考:1、在上述快速排序算法的执行过程中，跟踪程序的执行会发现，假设初始输入序列递减有序，那么调用Partition函数进行分划操作时，下标i向右寻 找大于等于基准元素的过程中会产生下标越界，为什么？如何修改程序，可 以防止这种情况的发生?这是因为原

12、有的程序在序列最右边未设置一个极大值作为哨兵，那么下标i在向右寻找大于等于基准元素的过程中，一直没有满足条件的元素值出现，就一直不会停止，直至越界。所以只要在序列的最后预留一个哨兵元素, 将它的值设为极大值8就可以解决:const int INF=2147483647; /定义一个极大值8l=new intmaxSize+l; 预留最后一个哨兵的位置void SortableList: :Input() for (int i=O;i K(left+right)/2和Kright三者的中间值为主元。试选择其中的一种，在原程序的基础上修改实现。下面给出第二种主元选择方式的具体 实现: 随机数的产生是由srand函数以time函数值(即当前时间)作为种子,rand函数产生一个0RAND_MAX范围内的随机数。因此文件的开头应包含两个头文件time.h和stdlib.ho为了不改动原有程序的基本结构，在原有程序上增加一个原有程序上增加一个RandomizedPartition 函数。由Quicksort先调用该函数，产生一个left-right范围内的随机下标3