跳转至

算法模板（入门级）

基础算法

冒泡排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
//冒泡排序
#include <iostream>
using namespace std;
int n, a[100010];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            //相邻元素两两比较，若前者大于后者，则交换位置
            if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

选择排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//选择排序
#include <iostream>
using namespace std;
int main() {
    int n;
    int a[100010];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int min;
    for (int i = 0; i < n; i++) {
        min = i;
        for (int j = i + 1; j < n; j++) {
            //min变量保存从i+1至n-1位置的最小元素的下标
            if (a[j] < a[min]) min = j;
        }
        if (i != min) swap(a[i], a[min]);
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

插入排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//插入排序
#include <iostream>
using namespace std;
int main() {
    int n, a[100010];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        //变量t暂时存储当前操作的元素a[i]的值
        int t = a[i];
        //变量j保存可以插入a[i]元素的位置下标
        int j = i;
        //遍历寻找j的合适位置
        while (a[j - 1] > t && j - 1 >= 0) {
            a[j] = a[j - 1];
            j--;
        }
        //把当前元素插入到合适的位置j
        a[j] = t;
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

快速排序

思路：

  1. 找到分界点 x，x 可以取a[L] 或者 a[R] 或者 a[(L + R) >> 1]
  2. 使左边所有数 <= x，右边所有数 >= x
  3. 递归排序左边，递归排序右边
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//快速排序 
#include <iostream>
using namespace std;
void quick_sort(int a[], int l, int r) {
    //递归函数的结束条件
    if (l >= r) return;
    //随机寻找一个元素值（一般找数组中的中间位置元素）
    int x = a[(l + r) >> 1];
    //以元素x的大小为分界线，把数组分为左右两个部分，
    //所有左半边元素的值不大于x，所有右半边元素的值不小于x
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    //递归处理数组左半边和右半边
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}
int main() {
    int n, a[100010];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    quick_sort(a, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

应用例题 第 \(k\) 个数 给定一个长度为 \(n\) 的整数数列，以及一个整数 \(k\)，请用快速选择算法求出数列从小到大排序后的第 \(k\) 个数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
int quick_sort(int a[], int l, int r, int k) {
    if (l >= r) return a[l];
    int x = a[(l + r) >> 1];
    int i = l - 1, j = r + 1;
    while (i < j) {
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    int s = j - l + 1;
    if (k <= s) return quick_sort(a, l, j, k);
    else return quick_sort(a, j + 1, r, k - s);
}
int main() {
    int n, k, a[100100];
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << quick_sort(a, 0, n - 1, k) << endl;
    return 0;
}

归并排序

思路：

1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//归并排序
#include <iostream>
using namespace std;
int tmp[100010];
void merge_sort(int a[], int l, int r) {
    //递归函数的结束条件
    if (l >= r) return;
    //以数组中间位置为分界线，把数组划分为两个部分
    int mid = l + r >> 1;
    //递归处理左半边和右半边
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    //合并左半边和右半边
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    //把合并完成的元素重新移回原数组
    for (int i = l, j = 0; i <= r; i++, j++) {
        a[i] = tmp[j];
    }
}

int main() {
    int n, a[100010];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    merge_sort(a, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

应用例题 \(逆序对的数量\) 给定一个长度为 \(n\) 的整数数列，请你计算数列中逆序对的数量。逆序对的定义： 对于数列中的第 \(i\) 个元素和第 \(j\) 个元素，如果满足 \(i < j\) 且 \(a[i] > a[j]\)，则其为一个逆序对；否则不是。

时间复杂度为 \(O(n^2)\) 的程序：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int main() {
    int n, a[100010];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] > a[j]) cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

使用归并排序思想的优化算法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r) {
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = 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 {
            res += mid - i + 1;
            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];
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    cout << merge_sort(a, 0, n - 1) << endl;
    return 0;
}

二分算法

整数二分算法思路：假设目标值在闭区间 [l, r] 中， 每次将区间长度缩小一半，当 l = r 时，我们就找到了目标值。

版本1

当我们将区间 [l, r] 划分成 [l, mid] 和 [mid + 1, r] 时，其更新操作是 r = mid 或者 l = mid + 1，计算 mid 时不需要加 1。

版本2

当我们将区间 [l, r] 划分成 [l, mid - 1] 和 [mid, r] 时，其更新操作是 r = mid - 1 或者 l = mid，此时为了防止死循环，计算mid时需要加 1。

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

浮点数二分算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

前缀和与差分

一维前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

二维前缀和

//S[i, j] = 第i行j列格子左上部分所有元素的和
S[i, j] = S[i - 1, j] + S[i, j - 1] - S[i - 1, j - 1] + A[i, j]
//以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

一维差分

//给区间[l, r]中的每个数加上c
B[l] += c, B[r + 1] -= c

例题：差分

输入一个长度为 \(n\) 的整数序列。

接下来输入 \(m\) 个操作，每个操作包含三个整数 \(l, r, c\)，表示将序列中 \([l, r]\) 之间的每个数加上 \(c\)。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 \(n\) 和 \(m\)。 第二行包含 \(n\) 个整数，表示整个序列。 接下来 \(m\) 行，每行包含三个整数 \(l, r, c\)，表示一个操作。

输出格式

共一行，包含 \(n\) 个整数，表示最终序列。

数据范围

\(1{\leq}n, m {\leq} 100000\), \(1 {\leq} l {\leq} r {\leq} n\), \(-1000 {\leq} c {\leq} 1000\), \(-1000{}{\leq}\) 整数序列中元素的值 \({\leq}{}1000\)

输入样例

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例

3 4 5 3 4 2

二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：

S[x1][y1] += c, S[x2 + 1][y1] -= c, 
S[x1][y2 + 1] -= c, S[x2 + 1][y2 + 1] += c

TODO 高维前缀和及差分

最后更新: 2021-09-27
Back to top