排序：
1.快排
2.归并排序
二分：
1.整数二分【重点】
2.小数二分（浮点数二分）【相对简单】

快排的基本思想：基于分治
1.确定分界点 x【对于左右边界l和r】
一般四种方式都可以：q[l],q[(l+r)/2],q[r],随机
2.调整区间
使得左边的所有数据都<=x;右边的数据都>=x;
3.递归处理左右两段
采用双指针的方式，可以不用开辟额外的空间
上述过程会涉及到令人不爽的边界问题，一般这种情况常常背一个模板比较好！

#include <iostream>
using namespace std;
const int N = 1e6+10;
int n;
int q[N];
//代码模板精华如下：
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >>1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
//至上
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);

    quick_sort(q,0,n-1);

    for(int i = 0; i < n; i++) printf("%d ", q[i]);

    return 0;
}

归并排序：也是分治，但是和快排有区别
快排是可以随机选一个数进行排序，但优先选择中间的数，因为效率相对更高。 然而归并是以整个数组的中间开始，先递归再处理，而快排是先处理再递归。归并排序是稳定的，相同的两个元素，并不改变其位置。
快排的平均复杂度是nlogn，最坏是n方
而归并排序是妥妥的nlogn
1.确定分界点: mid = (l+r)>>1;
2.递归排序left和right
3.归并（合二为一）

#include <iostream>
using namespace std;
const int N = 1e6+10;
int n;
int q[N], tmp[N]; //和快排的区别就是多用了一个辅助数组来进行二路归并
void merge_sort(int q[], int l, int r){
    if(l >= r) return;
    int mid = l + r >>1;
    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(int i = l, j =0; i <=r; i++,j++) q[i] = tmp[j];


}
int main(){
    scanf("%d", &n);
     for(int i = 0; i < n; i++) scanf("%d", &q[i]);
     merge_sort(q,0,n-1);
     for(int i = 0; i < n; i++) printf("%d ", q[i]);
     return 0;
}

二分算法：
整数二分：
有单调性的题目可以二分，但是可以二分的题目不一定都有单调性。所以二分的本质不是单调性，二是 “边界”。
二分其实是把区间分成两部分，一部分满足条件，一部分不满足。二分可以寻找满足性质的边界。
写算法时候的正常思路：
对于一个区间[l,r]
1.先求mid = l+r >>1;(这里先这么写，因为后面要调整，是否加一的问题)
2.然后写一个check函数，然后想一下这个check函数如果是true或者false的话该如何更新。
if（check（mid）） 看mid是否满足题目中的性质：看模板代码的详细内容。
（注意二分算法是一定有解的，而给的题目可能是无解的，如果无解的话，二分结束的位置，就是从左往右看，第一个大于这个数x的最小值。也就是说，定义了一个性质，性质是有边界的，二分算法是一定可以把这个边界找出来的，所以二分就不需要考虑有没有解的情况了，我们是根据二分出来的结果来判断题目是否有解）

#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int q[N];
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    while(m--){
        int x;
        scanf("%d", &x);

        int l = 0, r = n-1;
        while(l < r){
            int mid = l+r >>1;
            if(q[mid] >=x) r = mid;
            else l = mid +1;
        }
        if(q[l] != x) cout <<"-1 -1"<<endl;
        else{
            cout<<l<<" ";

            l = 0, r = n-1;
            while(l < r){
                int mid = l+r+1 >>1;
                if(q[mid] <=x) l = mid;
                else r = mid - 1;
            }
            cout<<r<<endl;
        }
    }
    return 0;
}

整数二分的模板：

//区间[l,r]被分成[l,mid]和[mid+1, r]时使用
int bsearch(int l, int r){
    while(l < r){
        int mid = l+r>>1;
        if(check(mid)) r = mid; //check() 判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
//区间[l,r]被分成[l,mid-1]和[mid, r]时使用
int bsearch(int l, int r){
    while(l < r){
        int mid = l+r+1>>1;
        if(check(mid)) l = mid; //check() 判断mid是否满足性质
        else l = mid - 1;
    }
    return l;  //都是返回l，因为while停止的条件就是l = r,所以是一样的
}

浮点数二分：本质上也是一个边界，因为没有整除的影响，所以区间长度可以严格的二分，不需要考虑边界，要时时刻刻保证答案在区间的内部。
举一个开平方的例子：

#include <iostream>

using namespace std;

int main(){
    double x;
    cin >>x;
    double l = 0, r = x;
    while(r - l > 1e-6){
        double mid = (l+r) /2;
        if(mid *mid >=x) r = mid;
        else l = mid;
    }
    printf("%lf\n", l);
    return 0;
}