标签：归并排序

题目内容

P1908

前言：归并排序

这里把归并排序写了留给我这个蒟蒻以后看

归并排序：时间复杂度O(n\log n)，空间复杂度O(n)的稳定排序算法。（试了一下，模板题速度比stl的sort还快，快排123ms，归并105ms，加上40行优化后77ms）

思想是递归+二分

将一个无序的序列先挨次递归分成两端两端，使左右两端先有序，然后从底往上依次合并小的分段序列，具体操作如下：

设需操作的序列左端下标为l，右端下标为r，则定义一变量mid=l+r>>1（代表l+r的和除以2，使用二进制优化常数），则左端序列是[l,mid]，右端是[mid+1,r]，再分别对其递归式地分割。

合并时定义三个指针l,r和k，分别指向左端序列的开头，右端序列的开头和新的临时序列b的对应位置，然后比较a[i]和a[j]的值，如果a[i]<a[j]，则将a[i]放入b序列中，并将指针i,k各加一，如果a[i]>a[j]，同理，将a[j]放入b序列中，并将指针j,k各加一。

为什么可以这样处理，因为需要合并的两端的序列都已经是有序的了（经过上一层递归处理过），再这样合并即可。

如果有剩余，则继续将i指针指向的内容和j指针指向的内容放入b序列中排好序的元素重新复制回a序列。

，然后再将b序列中排好序的元素重新复制回a序列。

网图：

代码实现：

#include <cstdio>
using namespace std;

const int maxn=1e5+4;

int a[maxn],b[maxn],N;//开局时先定义两个数组，a存储数据，b为归并时要用的辅助数组

inline int read()//快读
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}

void msort(int l, int r)//排序函数
{
    if(l==r) return;//如果l=r，那么return
    int mid=l+r>>1,i=l,j=mid+1,k=l;//定义mid变量和i,j,k三个指针
    msort(l,mid);msort(mid+1,r);//递归处理左和右序列
    while(i<=mid&&j<=r)//开始归并
    {
        if(a[i]<=a[j]) b[k++]=a[i++];//如果a[i]<=a[j]，将a[i]放入b序列并将指针后移
        else b[k++]=a[j++];//否则将a[j]放入序列
    }
    while(i<=mid) b[k++]=a[i++];//处理剩下的
    while(j<=r) b[k++]=a[j++];//处理剩下的
    for(int ii=l;ii<=r;ii++) a[ii]=b[ii];//复制结果回a数组
}

int main()
{
    N=read();
    for(int i=1;i<=N;i++)
        a[i]=read();
    msort(1,N);
    for(int i=1;i<=N;i++)
        printf("%d ",a[i]);
    return 0;
}

解题思路

首先要搞懂什么是逆序对

逆序对就是序列中a_i>a_j且i<j的有序对

搞清楚了什么是逆序对，让我们看看为什么归并排序能帮助我们解题

题目要求寻找的是逆序对的数目，而我们在做每一次合并的时候都会做a[i]是否大于a[j]的判断，通过这样的判断我们就可以找出逆序对的对数，如果a[i]大于a[j]，那么由于合并过程中两边的序列都是有序的，那么就一定会产生mid-i+1对逆序对：

看下面例子：

要合并的序列：1 2 5 6 （下标为i）
             3 4 5 7 （下标为j）

开始合并：
step 1: i=1, j=5, 1<3, 将1放入b序列中并i++
step 2: i=2, j=5, 2<3, 将2放入b序列中并i++
step 3: i=3, j=5, 5>3, 由于左序列后面所有的数都大于3，因此会产生5->3，6->3两个逆序对，
                       即mid-i+1个，且将3放入b序列中并j++
step 4: i=3, j=6, 5>4, 由于左序列后面所有的数也都大于4，因此会产生5->4，6->4两个逆序
                       对，也是mid-i+1个，且将4放入b序列中并j++
step 5: i=3, j=7, 5=5, 将5放入b序列中并i++
step 6: i=4, j=7, 6>5, 产生1个逆序对6->5，将5放入b序列中并j++
step 7: i=4, j=8, 6<7, 将6放入b序列中，由于i已经到达上限，故结束此过程，将剩余的7放入b序列

因此我们得到一个规律，每当发现a[i]>a[j]时，会产生mid-i+1个逆序对，计入ans即可，要注意ans要开long long，否则会炸。

代码如下：

#include <cstdio>
using namespace std;
typedef unsigned long long ll;

const int maxn = 5e5 + 10;
ll ans = 0;
int a[maxn], b[maxn], n;

void msort(int l, int r)//归并排序，只是加了记录ans而已
{
    if(l==r) return;
    int mid=(l+r)/2,i=l,j=mid+1,k=l;
    msort(l,mid);msort(mid+1,r);
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j]) b[k++]=a[i++];
        else b[k++]=a[j++],ans+=mid-i+1;//记录ans
    }
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(int ii=l;ii<=r;ii++) a[ii]=b[ii];
}

int main()
{
#ifndef ONLINE_JUDGE//本地调试使用
    freopen("1908.in", "r", stdin);
#endif
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    msort(1, n);
    printf("%llu\n", ans);//输出记得llu
    return 0;
}

反思

第一次打归并排序，其实归并排序本质上也就是一个分治的思想，将一个大的序列细分，逐个变为有序再最后合并。

逆序对，emm，仔细读题