分治算法实验(用分治法实现快速排序算法)教学文稿.pdf资源-CSDN文库

版权申诉

79 浏览量 2022-07-10 04:34:22 上传评论收藏 207KB 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);

while(a[--j]>x);

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余5页未读，立即下载

内容反馈

版权申诉

G11176593

粉丝: 6643
资源: 3万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip