题目：

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序数对。一个排列中逆序的总数就称为这个排列的逆序数。

如{2，4，3，1}中，2和1，4和3，4和1，3和1是逆序数对，因此整个数组的逆序数对个数为4，现在给定一数组，要求统计出该数组的逆序数对个数。

思路：

这一题是算法导论上面的一个课后题，也是微软的一个面试题。

据说可以用线段树来解决这个问题，但是自己在这方面比较薄弱，数据结构的各种知识还有待于加强啊。

可以用mergesort来解决这题：

整体思路还是分治，并且巧妙的用到了mergesort排序过程中的性质，十分值得学习。

int g_pair = 0;void mergearray(int a[], int b[], unsigned beg, unsigned mid, unsigned end){    if (a == NULL || b == NULL || beg > mid || mid + 1 > end)        return;    int i = beg, j = mid + 1;    int n = mid, m = end;    int k = beg;    while (i <= n && j <= m)    {        if (a[i] <= a[j])            b[k++] = a[i++];        else            b[k++] = a[j++], g_pair += n - i + 1;    }    while (i <= n)        b[k++] = a[i++];    while (j <= m)        b[k++] = a[j++];    while (beg <= end)        a[beg] = b[beg], ++beg;}void mergesort(int a[], int b[], unsigned beg, unsigned end){    if (a == NULL || b == NULL || beg >= end)        return;    unsigned mid = beg + (end - beg) / 2;    mergesort(a, b, beg, mid);    mergesort(a, b, mid + 1, end);    mergearray(a, b, beg, mid, end);}