一个排列含有逆序的个数称为这个排列的逆序数。例如排列263451含有8个逆序(2,1)，(6,3)，(6,4)，(6,5)，(6,1)，(3,1)，(4,1)，(5,1)，因此该排列的逆序数就是8。

例题: 求排列的逆序数

笨办法: O(n2)

分治O( nlogn) :

1) 将数组分成两半，分别求出左半边的逆序数和右半边的逆序数

2) 再算有多少逆序是由左半边取一个数和右半边取一个数构成(要求O(n)实现)

2) 的关键: 左半边和右半边都是排好序的。比如，都是从大到小排序的。这样，左右半边只需要从头到尾各扫一遍，就可以找出由两边各取一个数构成的逆序个数

 

#include 
     
      using namespace std;void Merge(int a[],int s,int mid,int e,int tmp[]){    int p1=s,p2=mid+1,p3=0;    while(p1<=mid && p2<=e)    {        if(a[p1]>=a[p2])            tmp[p3++]=a[p1++];        else            tmp[p3++]=a[p2++];    }    while(p1<=mid)        tmp[p3++]=a[p1++];    while(p2<=e)        tmp[p3++]=a[p2++];    int cnt=0;    for(int i=s; i<=e; i++)        a[i]=tmp[cnt++];}int MergeSortCount(int a[],int s,int e,int tmp[]){    int result=0;    if(s