信息学竞赛模板（五）— 归并排序

2021-02-14 · 96次阅读 · 原创 · 数据结构与算法

代码实现

int a[MAX];
int back[MAX];

void merge(int l, int r, int mid) {
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) back[k++] = a[i++];
        else back[k++] = a[j++];
    }
    while (i <= mid) back[k++] = a[i++];
    while (j <= r) back[k++] = a[j++];

    for (int k = l; k <= r; ++k) a[k] = back[k];
}

void merge_sort(int l, int r) {
    if (l >= r) return;
    if (l + 1 == r) {
        if (a[l] > a[r]) swap(a[l], a[r]);
        return;
    }

    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    merge(l, r, mid);
}

可参考例题：AcWing-107-超快速排序

应用

求逆序对

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e5 + 5;
int n, a[N], b[N];
LL ans;

void merge_sort(int l, int r){
    if(l >= r) return;
    
    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) b[k++] = a[i++];
        else ans += mid - i + 1, b[k++] = a[j++];
    }
    while(i <= mid) b[k++] = a[i++];
    while(j <= r) b[k++] = a[j++];
    
    for(i = l; i <= r; i++) a[i] = b[i];
}

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

标题：	信息学竞赛模板（五）— 归并排序
链接：	https://www.fightingok.cn/detail/52
更新：	2022-09-18 22:34:41
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可

信息学竞赛模板（五）— 归并排序

代码实现

应用

求逆序对

Cyan