分治法实现快速排序与两路合并排序

1实验报告（2015/2016学年第二学期）课程名称实验名称分治法实现快速排序与两路合并排序实验时间年月日指导单位计算机学院计算机科学与技术系指导教师学生姓名班级学号学院(系)专业实验报告2实验名称分治法指导教师实验类型验证实验学时2实验时间一、实验目的和要求实验目的：理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程序，加深对分治法的算法原理及实现过程的理解。实验要求：用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理，编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。二、实验环境(实验设备)硬件：微型计算机软件：Windows操作系统、MicrosoftVisualC++6.03三、实验原理及内容实验原理：分治法：即分而治之。将问题分解为规模较小，相互独立，类型相同的问题进行求解。对于无序数组的有序排序也就是按某种方式将序列分成两个或多个子序列，分别进行排序，再将已排序的子序列合并成一个有序序列。实验内容：两路合并排序算法的基本思想是：将待排序元素序列一分为二，得到两个长度基本相等的子序列，其过程类似于对半搜索；然后将子序列分别排序，如果子序列较长，还可以继续细分，知道子序列长度不超过1为止。以上的实现由下列代码执行：voidSortableList::MergeSort(){MergeSort(0,n-1);}voidSortableList::MergeSort(intleft,intright){if(leftright){intmid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);}}函数MergeSort是类SortableList上的公有成员函数。mid=(left+right)/2;将函数划分为两个长度基本相等的子序列，用递归来执行两个子序列的内部排序。而Merge函数是将有序的子序列合并，通过合并过程将自问题的解组合成元问题的解。通过比较两个序列中的最小者，输出其中的较小者，重复此过程，直到一个序列为空，如果还有元素为输出则输出即可。其中对于Merge函数代码如下：voidSortableList::Merge(intleft,intmid,intright)//将两个长度之和为n的有序子序列合并一个有序序列{int*temp=newint[right-left+1];inti=left,j=mid+1,k=0;4while((i=mid)&&(j=right))if(l[i]=l[j])temp[k++]=l[i++];elsetemp[k++]=l[j++];while(i=mid)temp[k++]=l[i++];while(j=right)temp[k++]=l[j++];for(i=0,k=left;k=right;)l[k++]=temp[i++];}快速排序算法的基本思想是：在待排序序列K[left:right]上选择一个基准元素（通常是最左边的元素），通过一趟分划操作将序列分成左右两个子序列，左子序列中所有元素都小于等于该基准元素，有子序列中所有元素都大于等于该基准元素。划分操作如下：intSortableList::Partition(intleft,intright){inti=left,j=right+1;do{doi++;while(l[i]l[left]);doj--;while(l[j]l[left]);if(ij)Swap(i,j);}while(ij);Swap(left,j);returnj;}则当前基准元素所在的位置位于左、右子序列的中间，即是其排序完成后的最终位置。通过递归调用，对左子序列和右子序列再分别进行快速排序算法的调用。由于每一趟分划结束后，左子序列中的元素均不大于基准元素，右子序列中的元素均不小于基准元素。而每次分划后，对分划得到的左、右子序列的快速排序又均是就地进行，所以一旦左、右两个子序列都已分别排好序后，无需再执行任何计算，整个序列就是所要求的有序序列了。因此类中应定义成员函数QuickSort来完成递归快速排序算法的调用和成员函数。快速排序操作如下：voidSortableList::QuickSort(){QuickSort(0,n-1);}5voidSortableList::QuickSort(intleft,intright){if(leftright){intj=Partition(left,right);QuickSort(left,j-1);QuickSort(j+1,right);}}比较合并排序和快速排序的异同。合并排序——将序列一分为二即可。快速排序——需调用Partition函数将一个序列划分为子序列。子问题解合并得到原问题解的过程：合并排序——需要调用Merge函数来实现。（Merge函数时间复杂度为O(n)）..快速排序——一旦左、右两个子序列都已分别排序，整个序列便自然成为有序序列。程序中的其他函数：输入输出函数：voidSortableList::Input(){for(inti=0;imaxSize;i++){cinl[i];n++;}}voidSortableList::Output(){for(inti=0;imaxSize;i++){coutl[i];}}主函数：voidmain(){intn;inti;cout***************************************endlendl;6cout1两路合并排序2快速排序endlendl;cout***************************************endlendl;while(1){cout************请选择排序方式*************endl;cini;if(i!=1&&i!=2){coutfaultendl;break;}cout***********请输入比较个数************endl;cinn;SortableListl(n);cout************请输入n个数：*************endl;l.Input();if(i=1)l.MergeSort();elsel.QuickSort();cout************排序后序列是：***********endl;l.Output();coutendl;}}实验结果：实验用例（1）722657884280724860（2）0000078完整实验代码：#includeiostream.hclassSortableList{public:SortableList(intmSize)//构造函数{maxSize=mSize;l=newint[maxSize];n=0;}~SortableList()//析构函数{delete[]l;}voidMergeSort();voidQuickSort();voidInput();voidOutput();private:int*l;intmaxSize;intn;voidMergeSort(intleft,intright);voidMerge(intleft,intmid,intright);voidSwap(inti,intj);voidQuickSort(intleft,intright);intPartition(intleft,intright);};voidSortableList::Swap(inti,intj){intc=l[i];l[i]=l[j];l[j]=c;}9intSortableList::Partition(intleft,intright){inti=left,j=right+1;do{doi++;while(l[i]l[left]);doj--;while(l[j]l[left]);if(ij)Swap(i,j);}while(ij);Swap(left,j);returnj;}voidSortableList::QuickSort(){QuickSort(0,n-1);}voidSortableList::QuickSort(intleft,intright){if(leftright){intj=Partition(left,right);QuickSort(left,j-1);QuickSort(j+1,right);}}voidSortableList::MergeSort(){MergeSort(0,n-1);}voidSortableList::MergeSort(intleft,intright){if(leftright){10intmid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);}}voidSortableList::Merge(intleft,intmid,intright)//将两个长度之和为n的有序子序列合并一个有序序列{int*temp=newint[right-left+1];inti=left,j=mid+1,k=0;while((i=mid)&&(j=right))if(l[i]=l[j])temp[k++]=l[i++];elsetemp[k++]=l[j++];while(i=mid)temp[k++]=l[i++];while(j=right)temp[k++]=l[j++];for(i=0,k=left;k=right;)l[k++]=temp[i++];}voidSortableList::Input(){for(inti=0;imaxSize;i++){cinl[i];n++;}}voidSortableList::Output(){for(inti=0;imaxSize;i++){coutl[i];}}11voidmain(){intn;inti;cout***************************************endlendl;cout1两路合并排序2快速排序endlendl;cout***************************************endlendl;while(1){cout************请选择排序方式*************endl;cini;if(i!=1&&i!=2){coutfaultendl;break;}cout***********请输入比较个数************endl;cinn;SortableListl(n);cout************请输入n个数：*************endl;l.Input();if(i=1)l.MergeSort();elsel.QuickSort();cout************排序后序列是：***********endl;l.Output();coutendl;}}12实验报告四、实验小结（包括问题和解决方法、心得体会、意见与建议等）分治法是一种很有用的算法设计技术，他可以应用于求解许多算法问题。分治法的设计算法一般是递归。五、指导教师评语成绩批阅人日期