[笔记][中国大学mooc][程序设计与算法（二） 算法基础][归并][归并排序] 求逆序数

题目

描述
在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。

对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足 j < k 且 ij > ik， 那么就称(ij,ik)是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。

现给定1,2,…,n的一个排列，求它的逆序数。

输入
第一行是一个整数n，表示该排列有n个数（n <= 100000)。
第二行是n个不同的正整数，之间以空格隔开，表示该排列。

输出
输出该排列的逆序数。

样例输入
6
2 6 3 4 5 1

样例输出
8

提示

1. 利用二分归并排序算法（分治）；
2. 注意结果可能超过int的范围，需要用long long存储。

分析

一个排列的逆序数，可以被分为两个子排列的逆序数和两个子序列相互之间的逆序数之和，这样的分治策略使得计算的算法复杂度降低到$O(NlogN)$O(NlogN)，整个算法的关键在于计算两个子序列之间的逆序数的时候，如果两个子序列已经分别从小到大排好序，那么只需要将整个序列遍历一遍就可以计算出结果，因为如果前面的序列中的一个元素a比后面序列中某个元素b大时，那么a就比b后面所有元素都大。

代码

#include<stdio.h>
#define MAXN 100000
int n, k;
int integral[MAXN];

//归并排序
long long Merge(int ptr_head1, int ptr_head2, int ptr_tail){
	int ptr1 = ptr_head1, ptr2 = ptr_head2, ptr=0;
	long long inverseNumber = 0;
	int tempSquenceForMerge[ptr_tail-ptr_head1+1];
	while(ptr1<ptr_head2&&ptr2<=ptr_tail){
		if(integral[ptr1]>integral[ptr2]){
			tempSquenceForMerge[ptr++] = integral[ptr1++];
			inverseNumber += (ptr_tail - ptr2 + 1);
		}
		else
			tempSquenceForMerge[ptr++] = integral[ptr2++];
	}
	while(ptr1<ptr_head2)
		tempSquenceForMerge[ptr++] = integral[ptr1++];
	while(ptr2<=ptr_tail)
		tempSquenceForMerge[ptr++] = integral[ptr2++];
	ptr=0;
	for(long cnt=ptr_head1; cnt<=ptr_tail; cnt++)
		integral[cnt]=tempSquenceForMerge[ptr++];
	return inverseNumber;
}
long long MergeSort(int ptr_head, int ptr_tail){
	if(ptr_head >= ptr_tail) return 0;
	else return MergeSort(ptr_head, (ptr_head+ptr_tail)/2)+
		   		MergeSort((ptr_head+ptr_tail)/2+1, ptr_tail)+
		   		Merge(ptr_head, (ptr_head+ptr_tail)/2+1, ptr_tail);
}
int main(){
	freopen("in.txt","r",stdin);
	scanf("%d", &n);
	for(int cnt=0; cnt<n; cnt++)
		scanf("%d", integral+cnt);
	printf("%lld\n", MergeSort(0, n-1));
	return 0;
}