【题目描述】

有一实数序列A[1]、A[2] 、A[3] 、……A[n-1] 、A[n] (n<10000)，若i<j，并且A[i]>A[j]，则称A[i]与A[j]构成了一个逆序对，求数列A中逆序对的个数。

例如，5 2 4 6 2 3 2 6，可以组成的逆序对有

（5 2），（5 4），（5 2），（5 3），（5 2），

（4 2），（4 3），（4 2），

（6 2），（6 3），（6 2），

（3 2）

共：12个

【输入描述】

共两行，第一行有一个正整数n，第二行有n个整数。

【输出描述】

只有一行为逆序对个数。

【样例输入】

8  5 2 4 6 2 3 2 6

【样例输出】

12

所谓逆序对的问题，即对给定的数组序列，求其逆序对的数量。

从逆序对定义上分析，逆序对就是数列中任意两个数满足大的在前，小的在后的组合。如果将这些逆序对都调整成顺序（小的在前，大的在后），那么整个数列就变得有序，即排序。因而，容易想到冒泡排序的机制正好是利用消除逆序来实现排序的，也就是说，交换相邻两个逆序数，最终实现整个序列有序，那么交换的次数即为逆序对的数量。

当然，这个题目，用的是合并操作来分析。

在合并操作中，我们假设左右两个区间元素为：

左边：{3 4 7 9}     右边 {1 5 8 10}

那么，合并的第一步就是比较3和1，然后将1取出来，放到辅助数组中，这个时候我们发现，右边的区间如果是当前比较的较小值，那么其会于左边剩余的数字产生逆序关系，也就是说1和3、4、7、9都产生了逆序关系，我们可以一下子统计出4对逆序对。

接下来3，4取下来放到辅助数组后，5与左边剩下的7、9产生了逆序关系，我们可以统计出2对。

以此类推，8与9产生1对，那么总共有4+2+1对。这样统计的效率就会大大提高，便可较好地解决逆序对问题。                                                  

void msort(int s, int t){  	if(s==t) return ;  //如果只有一个数字则返回，无须排序  	int mid=(s+t)/2;   	msort(s,mid);    //分解左序列  	msort(mid+1,t);  //分解右序列   	int i=s, j=mid+1, k=s;  //接下来合并  	  	while(i<=mid && j<=t){  	  		if(a[i]<=a[j]){  			r[k]=a[i];  			k++;  			i++;  		}else{  			r[k]=a[j];  			k++;  			j++;  			ans+=mid-i+1; //统计产生逆序对的数量   		}  	}  	while(i<=mid){  //复制 左边子序列剩余   		r[k]=a[i];  		k++;  		i++;  	}  	while(i<=mid){  //复制 右边子序列剩余   		r[k]=a[j];  		k++;  		j++;  	}  	for(int i=s;i<=t;i++)  		a[i]=r[i];   }

其中，ans+=mid-i+1; 这句代码统计新增逆序对的数量，ans作为全局变量，用于统计逆序对的数量，此时ans要增加左边区间剩余元素的个数。当归并排序结束后，逆序对问题也得到解决，ans即为逆序对的数量。

(adsbygoogle = window.adsbygoogle || []).push({});