quick_sort:
重点: 调整区间
解法:
1. 确定分界点x(q[l], q[r], q[l + r >> 1];双指针取值时有限制)推荐l + r >> 1, 递归时对应(l, j); (j + 1, r)
2. 调整区间,(从小到大)使分界点左侧全部满足<=x,右侧点满足>=x;双指针里判断条件不能>=x, <=x会超内存
3. 递归调用左右两边(l, j;j + 1, r 此时分界点不能取r; 同理如果第一个递归区间为i,则分界点不能取l: 否则当只有两个数需要排序时更新完节点后条件未变,死递归)
merge_sort:
重点: 归并排序
解法:
1. 确定分界点:一般直接l + r >> 1;
2. 先递归调用左右两边(l, mid), (mid + 1, r);
3. 归并,合二为一:两个区间分别用两个指针一个一个比大小,将结果分别存进tmp临时数组,最后再把tmp合进原数组;
二分:
重点:找出能二分的性质
二分本质是找出一组数据的边界;题意可能无解,但二分一定有解(>,>=)
二分可以处理查找问题
思想: 每次把范围缩小一半
目标: 找出红色(或绿色)边界点,使得一半满足性质,另一半不满足此性质
整数二分做法:
1. 先想check函数,想一下更新策略
2. 更新l或r,根据更新方式选择模板
浮点数二分note:
r - l > (); 条件精度比输出精度多2
如何想check函数:
假设x固定,以q[mid]点为主视角考察;
以q[mid] >= x为例, 要找出边界条件;则q[mid] >= x条件可以理解为之前不满足此条件即q[mid]此时 < x,位于x左边,要怎样移动到哪个边界上能满足条件:即左边开始数第一个等于x的数
如何确定边界调整区间:
以x为主视角,想象x位于哪边,缩短x不在的一边
如何确定mid是否要+1 >> 1:
l = r - 1; 带入检验是否更新完会出现l, r没变的情况