排序
1. 快排
以数组q为例
①确定分界点：
常用边界点：
- 左边界：q[l]
- 中间值：q[(l+r)/2]
- 右边界：q[r]
- 随机取一个
②根据分界点的值x，把整个区间划分为两部分，即调整区间使：
- 第一部分区间内的值都≤x
- 第二部分区间内的值都≥x
③递归：
- 递归处理左右两段
如何实现
- 双指针指向l与r，比较q[l]与x，若为q[l]≤x，l向右移动，直到q[l]≥x停止
- 之后r向左移动，比较q[r]与x，若为q[r]≥x，l向左移动，直到q[l]≤x停止
- 交换q[l]与q[r], swap(q[l],q[r])，两个指针都各自移动一格
重复上面操作，直到两个指针相遇过停止
模板：
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]; //分界点为中间值：q[(l+r)/2]
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); //防止边界问题背住就完事，要写i-1 和i的话前面x也得变成q[r]否则容易死循环
}
如果忘了那就暴力吧：
- 开a[ ],b[ ]数组
- 遍历q[l~r]，q[i]<=x，q[i]插到a[],q[i]>=x，q[i]插到b[]
- a[ ]放到q[ ],b[ ]放到q[ ]
2.归并
①确定分界点：
- mid= (l+r)/2
②递归排序left 部分与 right部分
③归并，即把两个合二为一
- 此时两个部分都是有序递增，双指针比较两部分，每次取更小的放入存结果的res[ ]数组，然后前移，继续比较就行
- 直到两个中的一个全被走完了，直接把另一个剩下的部分全部放进res[ ]就好了
模板:
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); //递归排序left部分和right部分
int k = 0, i = l, j = mid + 1; //i为left部分起始位置，j为right部分起始位置
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ]; //当两个数组都没遍历完的时候挨个进行比较并有序放入tmp[]
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ]; //把剩余的全部直接放进去
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; //改变原来的数组
}
整数二分
原理：
- 在一个有界区间内，有某种方法可以把区间一分为二，使得一部分满足check，另一部分不满足，则可以二分找出划分出区间的边界
实现方法
先写check函数，然后思考一下该如何更新区间
如果是true的情况l=mid，则最开始写的mid应该为mid=(l+r+1)>>1,那么false的情况则是r=mid-1
如果是r=mid，则最开始的mid就是mid=(l+r)>>1,那么false的情况是l=mid+1
-核心记法就是看是l=mid还是r=mid,如果是l＝mid记得+1
模板：
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(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_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
浮点数二分
- 这个不会出现边界问题，但是有精度问题，当区间被分为很小的时候就可以认为是找到了
模板：
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
