排序

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;
}