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

《分治法实现快速排序与两路合并排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告（2015/2016学年第二学期）课程名称实验名称分治法实现快速排序与两路合并排序实验时间年月日指导单位计算机学院计算机科学与技术系指导教师学生姓名班级学号学院(系)专业实验报告11实验名称分治法指导教师实验类型验证实验学时2实验时间一、实验目的和要求实验目的：理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程序，加深对分治法的算法原理及实现过程的理解。实验要求：用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理，编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。二、

2、实验环境(实验设备)硬件：微型计算机软件：Windows操作系统、MicrosoftVisualC++6.011三、实验原理及内容实验原理：分治法：即分而治之。将问题分解为规模较小，相互独立，类型相同的问题进行求解。对于无序数组的有序排序也就是按某种方式将序列分成两个或多个子序列，分别进行排序，再将已排序的子序列合并成一个有序序列。实验内容：两路合并排序算法的基本思想是：将待排序元素序列一分为二，得到两个长度基本相等的子序列，其过程类似于对半搜索；然后将子序列分别排序，如果子序列较长，还可以继续细分，知道子序列长度不超过1为止。以上的实

3、现由下列代码执行：voidSortableList::MergeSort(){MergeSort(0,n-1);}voidSortableList::MergeSort(intleft,intright){if(left

4、本相等的子序列，用递归来执行两个子序列的内部排序。而Merge函数是将有序的子序列合并，通过合并过程将自问题的解组合成元问题的解。通过比较两个序列中的最小者，输出其中的较小者，重复此过程，直到一个序列为空，如果还有元素为输出则输出即可。其中对于Merge函数代码如下：voidSortableList::Merge(intleft,intmid,intright)//将两个长度之和为n的有序子序列合并一个有序序列{int*temp=newint[right-left+1];inti=left,j=mid+1,k=0;11while((i<

5、=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]上选择一个基准元素（通常是最左边的元素），通过一趟分划操作将序列分成左右两个子序列，左子序列中所有元素都小于等于该基准元素，有子

6、序列中所有元素都大于等于该基准元素。划分操作如下：intSortableList::Partition(intleft,intright){inti=left,j=right+1;do{doi++;while(l[i]l[left]);if(i

7、分划结束后，左子序列中的元素均不大于基准元素，右子序列中的元素均不小于基准元素。而每次分划后，对分划得到的左、右子序列的快速排序又均是就地进行，所以一旦左、右两个子序列都已分别排好序后，无需再执行任何计算，整个序列就是所要求的有序序列了。因此类中应定义成员函数QuickSort来完成递归快速排序算法的调用和成员函数。快速排序操作如下：voidSortableList::QuickSort(){QuickSort(0,n-1);}11voidSortableList::QuickSort(intleft,intright){if(left

8、