排序与二分
一、排序
1、快速排序——分治法——时间复杂度nlog2n（平均时间复杂度，最坏情况为n2）
1、思路：
1、确定分界点，q[l]、q[r]、q[(l+r)/2] 2、调整区间，调整完后分界点左边都是小于等于x的数，右边都是大于等于x的数 3、递归处理左右两段
用i指针指向大于x的数，j指针指向小于x的数。
代码模板：
#include<iostream>
using namespace std;
const int N=1e6+10;
int n,q[N];
void quick_sort(int q[],int l,int r)
{
if(l>=r)//只有一个元素
return ;
int x=q[l],i=l-1,j=r+1;//x的位置看情况选，由于ij每次交换完都会向x移动一次，所以先让i=l-1,j=r+1
while(i<j)
{
do i++; while(q[i]<x);//找到大于x的值的位置
do j--; while(q[j]>x);//找到小于x的值的位置
if(i<j) /*如果i在j的左边，即两个指针没有相遇，
此时i指的数应该放在右边，j指的数应该放在左边，交换两个数的值*/
swap(q[i],q[j]);//没有swap可以手写交换函数
}
quick_sort(q,l,j);//写j的话x不能取q[r],要不然也会无限递归
quick_sort(q,j+1,r);
/*也可以写 quick_sort(q,l,i-1);
quick_sort(q,i,r);
但是这也写x不能等于q[l]会有边界问题，无限递归
*/
}
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;
}
2、归并排序——分治法——时间复杂度为nlog2n
思路：
1、先确定分界点，只能是中间值，即(l+r)/2 2、然后左右两边分别排序形成两个序列 3、然后归并合二为一成新序列res。这一步时间复杂度是O(n)的
左右两个序列排完后， 用两个指针分别指向两个序列第一个元素，然后比较，将较小的元素输到新序列res中 较小元素的那个序列指针后移一位，继续比较，将较小的元素输到新序列res中，重复 如果遇到元素相等，将左边序列后移。
代码模板：
#include<iostream>
using namespace std;
const int N=1e6+10;
int n,q[N],tem[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; //k计数，i为左边序列指针，j为右边序列指针
while(i<=mid&&j<=r)
{
if(q[i]<=q[j]) //左边序列值更小或者相等
tem[k++]=q[i++]; //把左边序列的值放入新数列
else //右边序列值更小
tem[k++]=q[j++]; //把右边序列的值放入新数列
}
while(i<=mid) //如果左边序列没有放完，右边放完了，把左边剩下的依次输入到新数列里
tem[k++]=q[i++];
while(j<=r) //同理右边
tem[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++) //用新数列给原数列赋值
q[i]=tem[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;
}
二、二分
总说
原理：如果确定f(x)在区间[a, b]内连续，且f(a) ∙ f(b) < 0，则至少有一个实根。二分法的操作，就是把[a, b]逐次分半，检查每次分半后区间两端点函数值符号的变化，确定有根的区间。
一般来说什么情况下用二分？
两个条件：上下界[a, b]确定、函数在[a, b]内单调。
1、整数二分
思路：
通过选定一个性质，把一个序列分为两部分，一边满足这个性质，另一边不满足这个性质，然后就可以找到这两个边界点。
第一种情况，要找红色部分的右分界点。
1、先取mid=(l+r+1)/2 //如果不加1，当r=l+1时，会出现死循环
2、写check函数
3、判断mid是否在红色区域里，
如果在红色区域，将区间缩小为[mid,r]，通过l=mid来更新
如果不在，将区间缩小为[l,mid-1]，通过r=mid-1更新
第二种情况，要找绿色部分的左分界点
1、先取mid=(l+r)/2
2、写check函数
3、判断mid是否在绿色区域里
如果在绿色区域，将区间缩小为[l,mid]，通过r=mid来更新
如果不在，将区间缩小为[mid+1,r]，通过l=mid+1更新
代码模板：
#include<iostream>
using namespae std;
const int N=1e5+10;
int n,m,q[N];
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&q[i]);
while(m--) //m次询问
{
int x; //x代表询问的值
scanf("%d",&x);
int l=0,r=n-1; //区间范围刚开始为整个区间
while(l<r) //当l与r没有相遇时一直进行二分，先求左分界点，这点的后面都是大于等于x的
{
int mid=(l+r)>>1; //位运算>> 向右移动一位相当于除2
if(q[mid]>=x) //当所取的中间值大于等于x时，
r=mid; //缩小右边
else
l=mid+1; //缩小左边
}
if(q[l]!=x) //当所求出来的点并不等于x时，代表不存在，
cout<<"-1 -1"<<endl;
else //左分界点存在，接下来求右分界点
{
cout<<l<<" ";
int 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<<l<<endl;
}
}
return 0;
}
2、浮点数二分
思路：
与整数二分差不多，但是由于浮点数没有明确的界限，所以当我们的区间长度小于10-6的时候，可以认为是一个数，就代表找到了。
代码模板：
求一个数的平方根
#include<iostream>
using namespace std;
int main()
{
double x;
cin>>x;
int l=0,r=x;
while(r-l>1e-8) //如果输出的答案要保留a位小数，那么精度至少要到1e-(a+2)
//或者直接for(int i=0;i<=100;i++) 循环100次也行
{
double mid=(l+r)/2;
if(mid*mid>=x)
r=mid;
else
l=mid;
}
printf("%lf\n",l);
return 0;
}
