目次:
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 |
