算法设计解析总结实验报告模板

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

2、选文档二、实验环境(实验设备)算法设计与解析课本笔录本电脑VC+6.0.优选文档三、实验原理及内容（包括操作过程、结果解析等）实验原理运用分治法：无序-部分有序-整体有序归并排序中“分”与“合”的过程是结合在一起的，即每一趟都在做“分”与“合”的工作，其实不是先“分”完再“合”基本程序（一）两路归并排序#includeclassSortableListpublic:SortableList(intmSize)/构造函数maxSize=mSize;l=newintmaxSize;n=0;SortableList()deletel;/析构函数voidInput();voidMerge(intlef

3、t,intmid,intright);voidMergeSort();voidMergeSort(intleft,intright);voidOutput();private:int*l;/动向生成一维数组intmaxSize;/线性表的最大表长intn;/线性表的实质长度;voidSortableList:Input()for(inti=0;ili;n+;.优选文档voidSortableList:Merge(intleft,intmid,intright)int*temp=newintright-left+1;inti=left,j=mid+1,k=0;while(i=mid)&(j=ri

4、ght)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+;voidSortableList:MergeSort()MergeSort(0,n-1);voidSortableList:MergeSort(intleft,intright)if(leftright)/若序列的长度高出1，则划分成两个子序列intmid=(left+right)/2;/将待排序的序列一分为二MergeSort(left,mid);/对

5、左序列排序MergeSort(mid+1,right);/对右序列排序Merge(left,mid,right);/将两个有序子序列归并成一个有序序列voidSortableList:Output()for(inti=0;imaxSize;i+)coutli;voidmain()SortableListl(10);cout请输入10个数：endl;l.Input();l.MergeSort();.优选文档cout排序后是：endl;l.Output();（二）快速排序#includeclassSortableListpublic:SortableList(intmSize)/构造函数maxSi

6、ze=mSize;l=newintmaxSize;n=0;SortableList()deletel;/析构函数voidInput();voidSwap(inti,intj);intPartition(intleft,intright);voidQuickSort(intleft,intright);voidQuickSort();voidOutput();private:int*l;/动向生成一维数组intmaxSize;/线性表的最大表长intn;/线性表的实质长度;voidSortableList:Input()for(inti=0;ili;n+;voidSortableList:Swa

7、p(inti,intj)intc=li;.优选文档li=lj;lj=c;intSortableList:Partition(intleft,intright)前置条件：left=rightinti=left,j=right+1;dodoi+;while(lilleft);if(ij)Swap(i,j);while(ij);Swap(left,j);returnj;voidSortableList:QuickSort()QuickSort(0,n-1);voidSortableList:QuickSort(intleft,intright)if(leftright)/当序列长度大于1时，需进行切

8、割intj=Partition(left,right);/对left,right范围内的序列进行分划QuickSort(left,j-1);/对左子序列推行快速排序QuickSort(j+1,right);/对右子序列推行快速排序voidSortableList:Output()for(inti=0;imaxSize;i+)coutli;voidmain()SortableListl(10);cout请输入10个数：endl;l.Input();l.QuickSort();cout排序后是：endl;l.Output();.优选文档实验结果两路归并排序快速排序.优选文档六、实验小结（包括问题和解决方法、心得领悟等）归并排序的基本运算是把两个或