题解 P1774 【最接近神的人_NOI导刊2010提高（02）】

在归并排序过程中完成。因为逆序对数等于左边的逆序对数加右边的逆序对数加分立两侧的逆序对数，刚好可以在归并排序中完成，算是模板题了，先理解题目最重要。如图为归并的思想：

#include <iostream>
#define LL long long

using namespace std;

const int M = 500010;
int n;
int num[M],tmp[M];
LL ans;

void gsort(int l,int r)
{
    int m=(l+r)>>1;
    int i=l,cnt=0,j=m+1;
    while(i<=m && j<=r)
    {
        if(num[i]<=num[j])
            tmp[cnt++]=num[i++];
        else
        {
            ans+=m-i+1;///已排好序的区间形成的逆序对个数 
            tmp[cnt++]=num[j++];
        }
    }
    while(i<=m)
        tmp[cnt++]=num[i++];
    while(j<=r)
        tmp[cnt++]=num[j++];
    for(int i=0;i<cnt;i++)
        num[l+i]=tmp[i];
}

void sorts(int l,int r)
{
    if(l<r)
    {
        int m=(l+r)>>1;
        sorts(l,m);
        sorts(m+1,r);
        gsort(l,r);
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>num[i];
    sorts(1,n);
    cout<<ans;
    return 0;
}

　 归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。