请选择 进入手机版 | 继续访问电脑版

分治与排序(下)

[复制链接]
孤单 发表于 2020-12-31 18:55:35 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
目次:
1|分治思想:快速排序,归并排序
2|小和,逆序对等问题求解
3|空间布局法之:堆排序,桶排序
4|排序算法小结
5|题解
1.分治法简介:问题分别为若干个子问题而与原来问题一致的子问题,递归办理这些问题,然后再归并这些效果,就得到了原问题的解
关键点:
1.原问题可以一直分解为形式相同子问题,当子问题较小时,可以自然求解,如一个元素本身有序.
2.子问题的解通过归并可以得到原问题的解
3.子问题的分解以及解的归并一定是简朴的,否则分解和归并的时间复杂度甚至高出暴力解法,得不偿失.
归并是分别很简朴,归并比力复杂
快排的思想重点在分别,归并不复杂
快排,重点是分别!:
1.分解:数组A[]被分别Wie两个子数组A[p,…q-1]和A[q+1,…r]使得A[q]为巨细居中的数,左侧A[p,…q-1]的每个元素斗小于即是中间元素,而右侧元素A[q+1,…r]中的每个元素都大于即是中间元素,计算下标也算是分别的一部分.
2.办理:通过递归调用快速排序,分别对于分别的左侧和分别的右侧再次使用快排
3.和序:因为分别好后,每一个元素左边的元素都小于这个元素,右边的元素都大于这个元素,所以说,和序这部分根本就不消做,前两步都做好了.
Partition方法:
方法不唯一,但是我个人以为看一两种最简朴效率最高的方法就够了,剩下的相识一下就可以了,这一选择双向移动指针法.
法一:双向扫描法:头指针从左往右扫,找到大于主元的元素,再将右指针从右往左扫,找到小于主元的元素,两者互换,直到左侧无大于主元的元素,右侧无小于主元的元素.这里直接给出代码
[code]#include#include#include#include#include#includeusing namespace std;int Partition(vector& A, int begin, int end) {                //问题的分别        int record = A[begin];        int i, j;        i = begin, j = end;        while (i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )