分治算法实验(用分治法实现快速排序算法).pdf
版权申诉
178 浏览量
2022-07-10
04:37:59
上传
评论
收藏 226KB PDF 举报
算法分析与设计实验报告
第 四 次附加实验
姓名
时间
学号
地点
班级
工训楼 30912.26 上午
实验名称 分治算法实验(用分治法实现快速排序算法)
实验目的 通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。
给定任意几组数据，利用分治法的思想，将数据进行快速排序并将排好的数据
进行输出。
程序思想：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数
据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进
行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序算法的性能取决于划分的对称性。通过修改函数Partition，可以
设计出采用随机选择策略的快速排序算法。
实验原理
实验步骤
分解：以 a[p]为基准元素将 a[p:r]划分成 3 段 a[p:q-1]，a[q]和 a[q+1:r]，使
a[p:q-1]中任何一个元素小于等于 a[q]，而 a[q+1:r]中任何一个元素大于等于
a[q]。下标 q 在划分过程中确定。
递归求解：通过递归调用快速排序算法分别对a[p:q-1]和 a[q+1:r]进行排序。
合并：由于对 a[p:q-1]和 a[q+1:r]的排序是就地进行的，所以在 a[p:q-1]和
a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]就已排好序。
关键代码
//函数Partition以一个确定的基准元素a[p]对子数组a[p:r]进行
划分
template <class Type>
int Partition(Type a[],int p,int r)
{
int i = p,j = r + 1;
Type x = a[p];
//将<x的元素交换到左边区域
//将>x的元素交换到右边区域
while(true)
{
while(a[++i]<x && i<r);
资源评论
