1.快速排序
快速排序的基本思想是分治：
①确定分界点X：常用的方法是取左端点q[l]、右端点q[r]，中点q[(l+r)/2]或者随机。不过一般取中点。
②调整区间：将所有≤X的数都放在X的左半边，所有≥X的数都放在右半边（调整完后左边的数都≤X，右边的数都≥X）
③递归处理左右两段。
其核心就在于第二步调整区间。
对于第二步可看看以下两种做法：
方法一：暴力做法：
①建立两个空白数组a[]，b[]；
②遍历数组q[l~r]，对其中≤X的元素q[i]，放入数组a[]；对于>X的元素q[i]，放入数组b[]；
③数组a[]依次放入数组q[]，数组b[]依次放入数组q[]；
这样X左边的都是小于等于X的元素，X右边都是大于等于X的元素。
这种方式的时间复杂度为O(n)。
方法二：快排
两个指针i和j，初始i指向第一个元素，j指向最后一个元素。两个指针往中间走，直到i走到第一个≥X的数，j走到第一个≤X的数，然后交换（swap）i和j指向的数，之后i和j继续往中间走直到相遇。
平均时间复杂度为O(nlogn)。
C++代码模板
void quick_sort(int q[],int l,int r){
// 区间内没有数或者只有一个数
if(l>=r) return;
//设置两个指针i和j;设X
int i=l-1,j=r+1,x=q[l+r>>1];
while(ix);
if(i
2.归并排序
归并排序的基本思想是分治。
①确定分界点：mid = (l + r) / 2.
②递归排序left 、right.
③归并——合二为一.
平均时间复杂度为：O(nlogn)。
C++代码模板
void merge_sort(int q[],int l,int r){
if(l>=r) return;
int mid=l+r>>1; //确定X，X取中点
merge_sort(q,l,mid),merge_sort(q,mid+1,r); //左右两段递归处理
int k=0,i=l,j=mid+1;
while( i <= mid && j <= r){
if(q[i]<=q[j]) tmp[k++]=q[i++];
else tmp[k++]=q[j++];
}
while( i <= mid ) tmp[k++]=q[i++]; //右半部分已经没有元素，则将左半部分续在后边
while( j <= r ) tmp[k++]=q[j++]; //左半部分已经没有元素，则将右半部分续在后边
for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j]; //合二为一
}
3.二分
二分的本质并非是单调性，二者的关系为：有单调性一定可以二分，但可二分的题不一定要有单调性——二分的本质是边界。算法的思想是假设目标值在闭区间[ l , r ]中， 每次将区间长度缩小一半，每次选择答案所在区间进行处理，当 l = r 时，我们就找到了目标值。
3.1整数二分——考虑边界问题
如图所示，假设给定一个区间，在区间上定义某种性质，使区间可以被一分为二，性质在某一边的区间满足而在另一边区间不满足。二分就是用于寻找该性质的边界，既可以是找绿色性质区间的边界，也可以是找红色性质区间的边界，这样就有了2个模板。
3.1.1二分出红色区间的边界点
①先找个中间值
②判断mid是否满足该（红色区间内）性质。
只有两种可能，满足（T）或不满足（F）。
a).若T，则mid满足红色区间内的性质（即mid位于红色区间内），则答案（红色边界点） 必然在 mid 和 r 之间找到，因为 mid 满足红色区间内的性质，所以也有可能是要找的边界点，因此答案所在的区间包含 mid，mid 之前的区间被舍弃，把初始的[ l , r ]区间变为[ mid , r ]，即更新为 l = mid，便可开始下一轮的二分。
b).若F，则 mid 不满足红色区间内的性质，说明 mid 落在了绿色区间，则答案肯定在 l 和 mid 之间，因为 mid 不满足性质，因此边界一定不在 mid 上，最多只能是在 mid - 1 ，因此区间为[ l , mid - 1 ] ， 更新为 r = mid - 1 即可。
C++代码模板
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
3.1.2二分出绿色区间的边界点
①先找个中间值
②判断mid是否满足该（绿色区间内）性质。
同样只有两种可能：T或F。
a).若T，则 mid 满足性质，即mid位于绿色区间，则答案（绿色边界点）在 l 和 mid 之间，并且边界点有可能位于 mid （因为mid满足条件），因此答案区间为[ l , mid ]，更新为 r = mid 即可。
b).若F，则 mid 不满足性质，即 mid 位于红色区域，则答案位于[ mid + 1 , r ]（不能取到 mid ，因为 mid 不满足条件，因此至少也是 mid + 1 ），更新为 l = mid + 1。
check()的功能由自己根据实际情况定义，这里只是比较形象地说明二分的思路。
C++代码模板
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
注意
1.关于如何选模板，二分时先写 mid = ( l + r ) / 2，再写一个check()函数，根据check的情况考虑如何去更新区间，看符合哪个模板就用哪个。若更新方式为 l = mid，r = mid - 1，则 mid = ( l + r + 1 ) / 2，否则不用补上+1。
2.为什么要补上+1：因为C++向下取整，打个比方，如果 l = r - 1，即区间长度为1时，则 mid = ( 2r - 1 ) / 2向下取整为 r，若check()又恰好成功，则区间更新为 l = mid = l，陷入死循环。为了避免再次更新依然为其自身，则让mid向上取整，即 mid = l + r + 1 >> 1.此时 l = mid = r，不会出现死循环。
3.2浮点数二分——无需考虑边界问题
思想同整数二分。由于浮点数二分无整除限制，因此每次可严格缩小一半，无需处理边界。每次通过中间点判断答案在哪边，只要时刻保证答案在区间内，当区间长度极小时（例如10^-6），可认为是一个数，即找到了答案。
C++代码模板
bool check(double x) {} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
