基础算法核心模板指南：快速排序、归并排序与二分查找等 | 极客日志

C++算法

基础算法核心模板指南：快速排序、归并排序与二分查找等

整理 C++ 基础算法核心模板代码，涵盖快速排序、归并排序、整数与浮点数二分、高精度加减乘除运算、双指针优化、位运算技巧、离散化及区间合并。内容包含算法思想解析、关键注意事项说明及完整可运行代码示例，适合算法初学者复习与竞赛准备。

极客工坊发布于 2026/2/9更新于 2026/4/181 浏览

基础算法核心模板指南：快速排序、归并排序与二分查找等

快速排序

思想

快排利用了分治算法，分治算法通常包含三步：

分成子问题
递归处理子问题
子问题合并

快排的操作是选取一个基准数 x，保证该数在数组中左边都比它小，右边都比它大。利用两个指针 i，j 分别放在首尾，当 i 走到第一个比 x 大的数停下，j 找到第一个比 x 小的数停下，交换位置。直到 i >= j 时，x 左边都是比它小的数，右边都是比它大的数。然后分治，将区间换成两个小区间继续操作。

模板展示

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int a[N];

void quick_sort(int a[], int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1;
    int x = a[(l + 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;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf(, &a[i]);
    (a, , n - );
     ( i = ; i < n; i++) (, a[i]);
     ;
}

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int a[N], tmp[N];

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 (k = 0, i = l; i <= r; i++, k++) a[i] = tmp[k];
}

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

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int n, q, a[N];

int main() {
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    while (q--) {
        int x;
        cin >> x;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (a[mid] < x) l = mid + 1;
            else r = mid;
        }
        if (a[l] != x) cout << "-1 -1" << endl;
        else {
            cout << l << ' ';
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (a[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(1);
    return C;
}

int main() {
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    auto C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

bool cmp(vector<int> &A, vector<int> &B) {
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i--) {
        if (A[i] != B[i]) return A[i] > B[i];
    }
    return true;
}

vector<int> sub(vector<int> &A, vector<int> &B) {
    vector<int> C;
    for (int i = 0, t = 0; i < A.size() || i < B.size(); i++) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.back() == 0 && C.size() > 1) C.pop_back();
    return C;
}

int main() {
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    if (cmp(A, B)) {
        auto C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    } else {
        auto C = sub(B, A);
        printf("-");
        for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

vector<int> mul(vector<int>& A, int b) {
    vector<int> C;
    for (int i = 0, t = 0; i < A.size() || t; i++) {
        if (i < A.size()) t = A[i] * b + t;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.back() == 0 && C.size() > 1) C.pop_back();
    return C;
}

int main() {
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    auto C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> div(vector<int>& A, int b, int &r) {
    r = 0;
    vector<int> C;
    for (int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.back() == 0 && C.size() > 1) C.pop_back();
    return C;
}

int main() {
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    int r;
    auto C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    cout << "\n" << r;
    return 0;
}

for (int i = 0, j = 0; i < n; i++) {
    while (j < i && check(i, j)) j++;
    // 剩下的操作就是看题目要求了
}

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n, a[N], s[N], res;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0, j = 0; i < n; i++) {
        s[a[i]]++;
        while (s[a[i]] > 1) {
            s[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res;
    return 0;
}

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int num = 0;
        while (x) {
            if (x & 1) num++;
            x >>= 1;
        }
        cout << num << ' ';
    }
    return 0;
}

#include <iostream>
using namespace std;

int lowbit(int x) {
    return x & (-x);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int res = 0;
        while (x) {
            x -= lowbit(x);
            res++;
        }
        cout << res << ' ';
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int, int> PII;
const int N = 3e5;
int n, m, a[N], s[N];
vector<int> alls;
vector<PII> add, query;

int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (alls[mid] < x) l = mid + 1;
        else r = mid;
    }
    return l + 1;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        int x, c;
        scanf("%d%d", &x, &c);
        add.push_back({x, c});
        alls.push_back(x);
    }
    for (int i = 0; i < m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    for (auto item : add) {
        int x = find(item.first);
        a[x] += item.second;
    }
    for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
    for (auto item : query) {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
typedef pair<int, int> Pii;
vector<Pii> segs;
int n;

void merge() {
    vector<Pii> res;
    int st = -0x3f3f3f3f, ed = -0x3f3f3f3f;
    for (auto seg : segs) {
        if (ed < seg.first) {
            if (ed != -0x3f3f3f3f) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        } else {
            ed = max(ed, seg.second);
        }
    }
    if (st != -0x3f3f3f3f) res.push_back({st, ed});
    segs = res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    sort(segs.begin(), segs.end());
    merge();
    cout << segs.size();
    return 0;
}