竞赛算法(2) 排序, 二分

快速排序#

基于分治思想, 对于每个区间将其分为较小的一段和较大的一段, 较小段的最大值小于等于较大段的最小值.

快速排序的步骤

选定基准值x, 将某个区间分为小于等于x的部分和大于x的部分, 当x靠近中位数时分治效果较为理想. 通常随机选取区间中的某个数.

使用双指针i, j. 其中i从前往后遍历, j从后往前遍历.

保证i遍历过的部分都是小于等于x的, j遍历过的都是大于x的.

如果i处大于x, j处小于等于x, 并且i在j前面, 交换两处的数字, 并移动i和j

如果i不在j前面, 说明已经遍历完毕, break.

递归处理左右两段.

1
void qks(vector<int>& arr, int l, int r) {
2
    if (l >= r) return;
3
    int x = arr[(l + r) / 2];
4
    int i = l - 1;
5
    int j = r + 1;
6
    while (i < j) {
7
        do i++; while (arr[i] < x);
8
        do j--; while (arr[j] > x);
9
        if (i < j) swap(arr[i], arr[j]);
10
    }
11
    qks(arr, l, j);
12
    qks(arr, j + 1, r);
13
}

归并排序#

同样基于分治思想, 见算法导论.

1
void mgs(vector<int>& arr, int l, int r) {
2
    static vector<int> tmp(arr.size());
3
    if (l >= r) return;
4

5
    int mid = (l + r) / 2;
6
    mgs(arr, l, mid), mgs(arr, mid + 1, r);
7

8
    int i = l, j = mid + 1, k = 0;
9
    while (i <= mid && j <= r) {
10
        if (arr[i] <= arr[j]) {
11
            tmp[k++] = arr[i++];
12
        }
13
        else {
14
            tmp[k++] = arr[j++];
15
        }
16
    }
17
    while (i <= mid) {
18
        tmp[k++] = arr[i++];
19
    }
20
    while (j <= r) {
21
        tmp[k++] = arr[j++];
22
    }
23

24
    for (i = l, k = 0; i <= r; i++, k++) {
25
        arr[i] = tmp[k];
26
    }
27
}

归并排序用于求逆序对#

1
long long ans = 0;
2
void mgs(vector<int>& arr, int l, int r) {
3
    static vector<int> tmp(arr.size());
4
    if (l >= r) return;
5

6
    int mid = (l + r) / 2;
7
    mgs(arr, l, mid), mgs(arr, mid + 1, r);
8

9
    int i = l, j = mid + 1, k = 0;
10
    while (i <= mid && j <= r) {
11
        if (arr[i] <= arr[j]) { // 注意这里必须是小于等于
12
            tmp[k++] = arr[i++];
13
        }
14
        else {
15
            tmp[k++] = arr[j++];
16
            ans += mid - i + 1; // 添加的一行
17
        }
18
    }
19
    while (i <= mid) {
20
        tmp[k++] = arr[i++];
21
    }
22
    while (j <= r) {
23
        tmp[k++] = arr[j++];
24
    }
25

26
    for (i = l, k = 0; i <= r; i++, k++) {
27
        arr[i] = tmp[k];
28
    }
29
}

二分查找#

1
bool check(int a);
2
void bs(const vector<int>& arr) {
3
    int n = arr.size();
4
    int l = -1;
5
    int r = n;
6
    while (r - l > 1) {
7
        int mid = (l + r) / 2;
8
        if (check(arr[mid])) {
9
            l = mid;
10
        }
11
        else {
12
            r = mid;
13
        }
14
    }
15
    return;
16
}

1
// 实数域二分
2
const double PCS = 1e-7;
3
bool check(double a);
4
double bs(double n, double l, double r) {
5
    while (r - l > PCS) {
6
        double mid = (l + r) / 2;
7
        if (check(mid)) {
8
            l = mid;
9
        }
10
        else {
11
            r = mid;
12
        }
13
    }
14
    return l;
15
}

主定理(master公式)#

用于求解分治算法的时间复杂度.

若 $T(n) = aT(\frac{n}{b}) + f(n)$

我们去比较 $f(n)$ 与 $n^{\log_ba}$ , 分为如下几种情况:

若 $f(n) < n^{\log_ba}$ , 则时间复杂度由递归主导, $T(n) = O(n^{\log _b a})$
若 $f(n) = n^{\log_ba}$ , 则时间复杂度由递归部分与非递归部分共同影响, $T(n) = O(n^{\log _b a}\log n)$ . 需要注意 $\log n$ 不算阶数.
若 $f(n) > n^{\log_ba}$ , 同时满足正则条件 $af(\frac{n}{b}) \le cf(n)$ (通常竞赛题目都满足), 则时间复杂度由非递归主导, $T(n) = O(f(n))$