【基础算法篇】归并排序笔记

算法思路

归并属于分治算法，有三个步骤

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, tmp[r - l + 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(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
&#125;

AC代码

#include <iostream>

using namespace std;

const int N = 100010;
int n;
int q[N], tmp[N];

void merge_sort(int q[], int l, int r)
&#123;
    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)
    &#123;
        if(q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    &#125;
    //合并剩下
    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];
&#125;

int main()
&#123;
    cin >> n;
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    return 0;
&#125;

习题 逆序对的数量

https://www.acwing.com/problem/content/790/

思路

我们将序列从中间分开，将逆序对分成三类：

1. 两个元素都在左边；
2. 两个元素都在右边；
3. 两个元素一个在左一个在右；

mid-i+1个逆序对
当q[i]<=q[j] , (q[i], q[j]) 则不是逆序对。
else if(q[i]>q[j]) (q[i], q[j])是逆序对，并且q[i]….q[mid] 与q[j] 形成 mid-i+1个逆序对。

AC代码

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int q[N];
int tmp[N];

LL merge_sort(int a[], int l, int r)&#123;
    if(l >= r) return 0;
    int mid = l + r >> 1;
    LL res = 0;
    res += merge_sort(a, l, mid);
    res += merge_sort(a, mid + 1, r);

    // 合并
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    &#123;
        if(q[i] <= q[j]) tmp[k ++] = q[i ++];
        else
        &#123;
            tmp[k ++] = q[j ++];
            res += mid - i + 1;
        &#125;
    &#125;
    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;
&#125;

int main()&#123;
    int n;
    cin >> n;
    for(int i = 0; i < n;i++)&#123;
        cin >> q[i];
    &#125;
    cout << merge_sort(q, 0 ,n - 1);
&#125;