快速排序——分治

解释

image-20220427161913036

1.确定分界点: q[l], q[r], q[(l+r)/2], 随机

2.调整区间：

image-20220427161927068

ps: 定义i和j两个指针，i从头前一位开始走，j从尾部后一位开始走。当i走到第一个大于等于x的数停止，j走到第一个小于等于x的数停止；i和j的数交换。

3.递归处理左右两段

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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];
    //看这里就知道左边界使用左指针就死循环了
    
    
    //同理右边界不能右指针
    while (i < j) //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);
    //注意:
    //这里容易发生死循环（取 l（左边界）时，这里不能用i（左指针）；用 r 时，这里不能写 j );
    //写quick_sort(q, l, i-1), quick_sort(q, i, r)时，要注意x=q[l+r+1>>1]处理边界问题,或者x=q[r]
}

时间复杂度

平均：O(nlog2n)

归并排序——-分治

解释

image-20220427161943236

1.确定分界点mid ：(l+r)/2

2.递归排序 left right

3.归并—-合二为一 重点

定义两个指针分别指向在两个数组头和中间，比较两个指针所指目标值的大小，将更小值放进新数组，然后该指针++。

image-20220427162013293

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
	
    //有一半走完了，没得比较了，直接输出
    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];
}

时间复杂度

平均：O(nlog2n)

整数二分法

解释

利用mid=l+r >>1 ，不断二分，找到要的数值

image-20220427161901962

ps:不一定要单调性才能使用二分法，核心是每次二分，答案都要在二分得到的一个数组里面（二分法是一定能得到一个答案的）。

  整数二分要考虑边界死循环的问题，更为麻烦。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
}

时间复杂度

浮点数二分法

解释

利用mid=l+r >>1 ，不断二分，找到要的数值

image-20220427161845498

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求；	一般题目要求精度再e-2
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

时间复杂度