归并排序的知识

一.什么是归并排序？

归并排序是一种基于分治思想的高效，稳定的排序算法，是算法竞赛中非常常用的排序方法，也是求逆序对的经典算法

二.归并排序的核心思想

核心思想是分治思想，分而治之；它的流程可以拆分为3步：

1.分：把待排序的数组从中间一分为二，递归地左右两个子数组接着拆分，直到每个子数组只有一个元素（天然有序）

2.治：递归地对左右两个子数组进行排序

3.合：把两个已经排好序的子数组合并成一个完整的有序数组

三.如何实现归并排序？

以merge（l,r）为例：

1.递归终止条件：

if(l>=r) return ;

当区间只有一个元素时，l==r，或者区间非法，l>r时，直接返回，不需要排序

2.分：拆成两半

int mid=(l+r)/2;

merge(l,mid);

merge(mid+1,r);

先递归把左半段【l，mid】排好序，再递归把右半段【mid+1，r】排好序。递归到底层后，左右两端都是有序数组

3.合：合并两个有序数组（核心）

int i=l,j=mid+1,k=l;

while(i<=mid&&j<=r){

if(a[i]<=a[j])

tmp[k++]=a[i++];

else{

tmp[i++]=a[j++];

ans+=mid-i+1;}

}

两个指针i，j分别指向左右两端的开头，k指向临时数组tmp的写入位置；每次把两个指针指向的较小值，写入tmp：若a【i】<=a【j】，说明a【i】＜a【j】，不会产生逆序对，直接写入tmp；若a【i】＞a【j】，说明a【j】比左半段从i到mid的所有元素都小，会产生mid-i+1个逆序对，写入tmp并更新ans

4.收尾：拷贝剩余元素

while(i<=mid) tmp[k++]=a[i++];

while(j<=r) tmp[k++]=a[j++];

for(int p=l;p<=r;p++)

a[p]=tmp[p];

把左右两端中剩下的元素直接写入tmp，把tmp中合并好的有序数组，拷贝回原数组a，供上一层递归使用

四.完整可运行代码

#include <bits/stdc++.h>

using namespace std;

const int N = 500010;

int a[N], tmp[N];

long long ans = 0; // 逆序对数量可能很大，必须用

long long void merge(int l, int r)

{

if(l >= r) return;

int mid = (l + r) /2;

merge(l, mid);

merge(mid + 1, r);

int i = l, j = mid + 1, k = l;

while(i <= mid && j <= r)

{ if(a[i] <= a[j])

{ tmp[k++] = a[i++]; }

else

{ tmp[k++] = a[j++];

ans += mid - i + 1; // 统计逆序对 } }

while(i <= mid)

tmp[k++] = a[i++];

while(j <= r) tmp[k++] = a[j++];

for(int p = l; p <= r; p++) a[p] = tmp[p];

}

int main() {

ios::sync_with_stdio(false);

cin.tie(0);

int n;

cin >> n;

for(int i = 1; i <= n; i++)

{

cin >> a[i];

}

merge(1, n);

cout << ans << endl;

return 0; }