1.快速排序

快速排序的基本思想是分治。
①确定分界点X:左端点，右端点，中点，随机取都可以，不过建议取中间点，因为有时候取左右端点会是时间复杂度变大；
②调整区间:使x左边的数都<=x,使x右边的数都>=x；
③递归处理左右两段。

例题：785. 快速排序
给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

输出格式
输出共一行，包含 n 个整数，表示排好序的数列。

数据范围
1≤n≤100000

代码模板:

#include<iostream>
using namespace std;
const int N = 1e6+10;//将数组空间开大一点，防止下标越界
int a[N],n;

void quick_sort(int a[],int l,int r)
{
    if(l>=r)
        return;
    
    int x=a[(l+r+1)/2],i=l-1,j=r+1;
    
    while(i<j)
    {
        while(a[++i]<x);
        while(a[--j]>x);
        if(i<j)
            swap(a[i],a[j]);
    }
    
    quick_sort(a,l,i-1);
    quick_sort(a,i,r);
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    
    quick_sort(a,0,n-1);
    
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    
    return 0;
}

2.归并排序

归并排序的基本思想是也是分治。
①确定分界点X:X是中点，x=(left+right)/2;
②递归排序left,right;
③归并-合二为一:将两个有序序列合并成一个有序序列。

例题：
代码:

#include<iostream>
using namespace std;

const int N = 1000010;

int n ;
int q[N],tmp[N];

//q[]:需排序的数组 l:左边界  r:右边界(均为闭区间)
void merge_sort(int q[],int l,int r)
{
    //如果当前区间内只有一个数/没有数，就不用排序了
    if(l>=r)
        return;
    
    //1.确定分界点
    int mid = (l+r)/2;
    
    //2.递归排序左右两边
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    
    //3.归并-合二为一
    int k=0;//已经合并几个数了，即tmp[]里有几个数了
    int i=l,j=mid+1;//i,j是左右两边的指针
    
    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++];
    }
    
        //把tmp[]里的数赋值回q[]里面去
    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;
    
}

3.二分查找

3.1 整数二分(尤其要注意边界问题)

二分的本质并不是单调性。
如果有单调性，一定可以二分；
但可以二分的题目不一定非得有单调性。

例题:

代码:

#include<iostream>
using namespace std;

const int N = 100010;

int n,m;
int a[N];

int main()
{
    scanf("%d%d",&n,&m);
    
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    
    while(m--)
    {
        int x;
        scanf("%d",&x);
        
        int l=0,r=n-1;
        
        while(l<r)
        {
          int mid = l+r>>1;
          if(a[mid]>=x) r=mid;
          else l=mid+1;
        }
        
        if(a[l]!=x) cout<<"-1 -1"<<endl;
        else
        {
            cout<<l<<' ';
            
            int l=0,r=n-1;
            while(l<r)
            {
                int mid = l+r+1>>1;
                if(a[mid]<=x) l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
    
    return 0;
    
    
    
}

3.2 浮点数二分(不需要考虑边界问题)

例题：将一个数开平方，求他的平方根

代码：

#include<iostream>
using namespace std;

int main()
{
    double x;
    cin>>x;
    
    double l=0,r=x;
    
    //只要区间长度大于10的-8次方，就一直做
    while(r-l>1e-8)//如果题目让我们保留4位小数，这就写1e-6;
    {              //这总比我们要求的有效位数多2
        double mid = (l+r)/2;
        if(mid*mid >= x) r=mid;
        else l = mid;
    }
    
    cout<<l;
    
    return 0;
}