算法基础课题解合集

归并排序的前世今生

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
1945年，约翰·冯·诺依曼（John von Neumann）发明了归并排序，这是典型的分治算法的应用。

算法步骤

1. 分：先递归将数组分成只有一个元素的有序数组

然后

2. 治：合二为一：将两个有序数组合并成一个有序数组（就是二路归并）

图解

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, q[N], tmp[N];

void mergesort(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    //分
    mergesort(l, mid);
    mergesort(mid + 1, r);
    //治（合并）
    //tmp数组临时存放我们合并的有序序列
    //i是第一个序列的头，j是第二个序列的头
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        //找小的存进tmp中
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    }
    //如果还剩下有没放进tmp中的，就按顺序插入tmp的末尾
    //这两个循环最多只会执行一个
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];
    //再把tmp中的数据copy会原数组里
    for (int i = l, j = 0; i <= r; i ++, j ++)
        q[i] = tmp[j];
}

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

时间复杂度：$O(nlogn)$，是稳定的排序