inversion 逆序数
definition:
对数组a[].存在一对（i，j）有i < j 且 a[i] > a[j] 即为一个逆序数对
e.g.
{1,3,5,2,4,6} 逆序数为3
i.e. (3,2) (5,2) (5,4)
Stanford open course 的第一章就是关于分而治之思想（divide and conquer）的归并排序（mergesort）。上学期去隔壁班蹭算法课的时候听了下内排序，其实理解的不够深刻。现在再看一次mergesort，确实将分治思想变现的淋漓尽致。将大问题划分成小问题，递归调用函数去解决。
mergesort的大致思路，就是将一个数组平均分成左右两个子数组，分别调用排序函数本身，返回的是两个已排序的数组，然后再将其merge起来。时间复杂度是O（n·log n)
在mergesort算法的基础上稍为改变一下就可以实现求一组数的逆序数。
单纯用for循环模拟的话，复杂度是O( n^2 ) 即n个数中取2个的组合数。
接上，一个array被分成left array[i] & right array[j]，其逆序数的组成可分为3部分：
1.left inversion （i,j)均在left array中，即 i,j <= n/2
2.right inversion (i,j)均在right array中，即 i,j > n/2
3.split inversion i在left，j在right，即 i <= n/2 ; j > n/2
计算左数组和右数组的逆序数，再加上split inversion即可得到整个数组的inversion number。问题关键成了解决split inversion。假设左右数组均已排好序（sorted B[],C[])，按mergesort的思路将两个数组合并的时候，每次从B[]取数放到合并数组(D[]),
计算B中剩余的元素个数（因为B中元素本应全部小于C中元素，若不是则必然存在逆序）。
课程练习原题是从100000的样本测试数据（txt）中计算逆序数个数，这个mergesort的模板感觉是有点怪（参数列表的问题）。开始用int count，结果溢出了。。。目测一下结果，貌似溢出的不多，改unsigned int，过了~
上代码：
#include<cstdio>
#include<fstream>
using namespace std;
int tmp[100001],a[100001];
void mergesort(int a[],int tmp[],int left,int right,unsigned int& count){ //待排序数组地址a，缓存数组tmp（节省时间，避免每次递归调用都开辟新数组）
int mid = (left + right) / 2;
if(left == right)return; //递归分割的最小子项
mergesort(a,tmp,left,mid,count);
mergesort(a,tmp,mid + 1,right,count); //分别对左右数组递归调用mergesort（invoke mergesort() recursively）
for(int i = left;i <= right;i ++)tmp[i] = a[i];
int i = left;
int j = mid + 1;
for(int k = left;k <= right;k ++){ //merge two sorted array
if(i > mid)a[k] = tmp[j ++]; //judge the index of array out of size
else if(j > right)a[k] = tmp[i ++];
else if(tmp[i] > tmp[j]){
a[k] = tmp[j ++];
count += mid + 1 - i; //add remain number of left array(inversions with tmp[j])
}
else a[k] = tmp[i ++];
}
}
int main()
{
fstream file("d:\\IntegerArray.txt",ios::in);
if(!file)printf("exception!");
int i = 0;
unsigned int count = 0;
char s[10];
while(file >> s)
a[i ++] = atoi(s);
mergesort(a,tmp,0,99999,count);
printf("%u\n",count);
return 0;
}
