有一个数的序列A[1]、A[2] 、A[3] 、…… 、A[n]，若i<j，并且A[i]>A[j]，则称A[i]与A[j]构成了一个逆序对，设计算法求数列A中逆序对的个数。
方法：归并排序，只需要加一个变量存逆序数的对数即可。
重点：两个数组merge的时候，两个数组之间逆序数的对数怎么求。
如果前面数组中的ai>后面数组中的aj，那么逆序数的对数应该加（m+1-i），因为两个数组中的数都是有序的，如果ai>aj，那么ai+1~am都是大于aj的。（m为第一数组最后一个元素的索引值）
具体可以看下图帮助理解
3>2，所以2的逆序数对数为（m+1-i = 5+1-0 = 6）
14>11，所以11的逆序数对数为（m+1-i = 5+1-3 = 3）
……
int merge(int a[], int b[], int l, int m, int r)
{
int num = 0;
int i = l;
int j = m + 1;
int k = l;
int t = m - i + 1; //记录前半段的长度
while (i != m + 1 && j != r + 1)
{
if (a[i] > a[j])
{
b[k++] = a[j++];
num += t;
}
else
{
b[k++] = a[i++];
}
t = m - i + 1;
}
while (i != m + 1)
{
b[k++] = a[i++];
}
while (j != r + 1)
{
b[k++] = a[j++];
}
for (i = l; i <= r; i++)
{
a[i] = b[i];
}
return num;
}
int merging(int a[], int b[], int l, int r)
{
int m;
int num1 = 0, num2 = 0, num3 = 0;
if (l < r)
{
m = l + (r - l) / 2; //防止溢出
num1 = merging(a, b, l, m);
num2 = merging(a, b, m + 1, r);
num3 = merge(a, b, l, m, r);
}
return num1 + num2 + num3;
}
| 
转播
