第一章
基础算法（一）：
一、快速排序：
1.确定区间中的某一点，如a[l],a[r],a[(l+r)/2]等等，
2.将数组分为左右两边，左边全为比分界点小的数，右边全为比分界点大的数，
代码实现：
void quick_sort(int q[],int l,int r)
{
if(l>=r) return 0;//meiyoushu
int i=l-1,j=r+1;
int x=q[l];
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);
}y总代码：
上图29行:改为；，31行l，r改为0和n-1，33行将取地址符&去掉。
?3.然后分别对左右两边进行递归排序。
tips：
*若选取的为q[l],则底下两个递归为l，j和j+1，r；
为q[r]则为l，i-1和i，r；是互相对称的。
*选q[l]，不能用i，只能用j，反之也是一样，，因为这会导致死循环。
较为建议选取q[(l+r)/2];
*(l+r)/2也可以写为(l+r)>>1,即除二取整。
*当输入数据较多时，选择较快的读取方式，在c++中我们选择scanf来进行快速读取。
二、归并排序
1.找分界点
2.递归排序左右两边，将数组分成左右两个有序的数组
3.归并，将两个数组合并成一个有序的数组，通过比较大小插入到一个新的数组中去。
代码实现：
void merge_sort(int q[],int l,int r)
{
if(l>=r) return;
int mid=(l+r)>>1,i=l,j=mid+1;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
int k=0;
while(i<=mid && j<=r)
{
if (q[i]<=q[j]) temp[k++]=q[i++];
else temp[k++]=q[j++];
}
while(i<=mid) temp[k++]=q[i++];
while(j<=r) temp[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++) q[i]=temp[j];
}y总代码：
?tips：
快排，归并，与sort速度差不多；
三、二分法查找边界
二分的实质是寻找边界，使用二分法一定能找到边界，至于边界是否与题意有关是否满足不在考虑之内。
整数二分概念图：
?因为整数除以是向下取整的，并且边界问题考虑在内，所以我们在使用时需要注意加一减一问题。做题时通过画图思考mid值是否满足要求来确定加一减一。
代码实现：
int bsearch1(int l,int r)//找右半边情况
{
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
return l;//r 也行
}
int bsearch2(int l,int r)//找左半边情况
{
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
return l;
}y总代码：
?tips：
*若减一则应该在mid计算时加一，否则可能会出现死循环。
*做题时建议直接写mid=l+r>>1；再根据后面判断是否加1；
浮点数二分：不用考虑边界问题，浮点数除以没有取整问题。直接取mid就好，终止条件可为区间长度小于1e-6等；
经验：若结果取四位小数，则为1e-6，若五位小数，则为1e-7；大二即可较精确。
?eg：求平方根问题：（判断条件也可不写区间长度，直接暴力重复100次也可）
?