算法

1. 快排
   时间复杂度平均为n*log(n) 最坏为n^2
   i)确立分界点x
   ii)调整区间 ※主要书写步骤 ,重开数组或者使用双指针
   iii)递归处理左右两端区间
2. 归并排序
   时间复杂度平均为nlog(n) 最坏为nlog(n)
   i)确立分界点mid=(l+r)/2
   ii)递归处理左右两端区间
   iii)归并左右区间 ※主要书写步骤 ,使用双指针
   需要多开一个数组,最后把数组赋值给原数组 切记!
3. 整数二分
   时间复杂度平均为log(n) 最坏为log(n)
   i)确立性质check
   模板一
   ii)确立分界点mid=(l+r+1)/2
   iii)通过check(mid) 更新l或r
   iiii)l<r停止 返回l
   模板二
   ii)确立分界点mid=(l+r)/2
   iii)通过check(mid) 更新l或r
   iiii)l<r停止 返回l
4. 浮点数二分
   i)确立性质check
   ii)确立分界点mid=(l+r)/2
   iii)通过check(mid) 更新l或r
   iiii)r-l小于一定范围停止 返回l

小技巧与知识

• 1e6表示10的6次幂
• scanf比cin快
• 边界问题背一种模板就好不用太纠结
• 归并排序是稳定的，快排不是稳定的

今日模板算法默写框架

快速排序算法模板
void quick_sort(int q[], int l, int r)
{

}
归并排序算法模板
void merge_sort(int q[], int l, int r)
{

}

整数二分算法模板
bool check(int x)
int bsearch_1(int l, int r)
{

}
int bsearch_2(int l, int r)
{

}

浮点数二分算法模板
bool check(double x)
double bsearch_3(double l, double r)
{

}