思路：最简单的方法是顺序数组。将每一个数字与后面的比較，统计逆序对的个数，这样的方法的时间复杂度为O(n*n)，这样的方法写出的代码在九度OJ上測试，会超时。

剑指offer给出了归并排序的思路。这个有点难想到啊，也可能是我太弱了，根本没往这方面想！理解了思路。就不难了，将数组划分成两个子数组。再将子数组分别划分成两个子数组。统计每一个子数组内的逆序对个数，并将其归并排序。再统计两个子数组之间的逆序对个数，并进行归并排序。

这就是归并排序的变种，在归并排序代码的基础上稍作改进就可以。

    合理还要注意一点：全局变量count不能声明为int型。必须为long long型。由于题目中说数组最大为10^5，那么最大逆序对为(10^5-1)*10^5/2，这个数大约在50亿左右，超过了int型的表示范围。

    AC代码例如以下：

#include<stdio.h>

#include<stdlib.h>

/*

统计两个子数组之间的逆序对

*/

long long MergePairsBetweenArray(int *arr,int *brr,int start,int mid,int end)

{

	int i = mid;

	int j = end;

	int k = end;  //辅助数组的最后一位

	long long count = 0;

	//设置两个指针i,j分别从右往左依次比較。

	//将较大的依次放入辅助数组的右边

	while(i>=start && j>=mid+1)

	{

		if(arr[i] > arr[j])

		{

			count += j-mid;

			brr[k--] = arr[i--];

		}

		else

			brr[k--] = arr[j--];

	}

	//将当中一个数组中还剩下的元素复制到辅助数组中。

	//两个循环仅仅会运行当中的一个

	while(i>=start)

		brr[k--] = arr[i--];

	while(j>=mid+1)

		brr[k--] = arr[j--];

	//从辅助数组中将元素复制到原数组中。使其有序排列

	for(i=end;i>k;i--)

		arr[i] = brr[i];

	return count;

}

/*

统计数组中的全部的逆序对

*/

long long CountMergePairs(int *arr,int *brr,int start,int end)

{

	long long PairsNum = 0;

	if(start<end)

	{

		int mid = (start+end)>>1;

		PairsNum += CountMergePairs(arr,brr,start,mid);	//统计左边子数组的逆序对

		PairsNum += CountMergePairs(arr,brr,mid+1,end);	//统计右边子数组的逆序对

		PairsNum += MergePairsBetweenArray(arr,brr,start,mid,end); //统计左右子数组间的逆序对

	}

	return PairsNum;

}

/*

将函数封装起来

*/

long long CountTotalPairs(int *arr,int len)

{

	if(arr==NULL || len<2)

		return 0;

	int *brr = (int *)malloc(len*sizeof(int));

	if(brr == NULL)

		exit(EXIT_FAILURE);

	long long sum = CountMergePairs(arr,brr,0,len-1);

	free(brr);

	brr = NULL;

	return sum;

}

int main()

{

	int n;

	while(scanf("%d",&n) != EOF)

	{

		int *arr = (int *)malloc(n*sizeof(int));

		if(arr == NULL)

			exit(EXIT_FAILURE);

		int i;

		for(i=0;i<n;i++)

			scanf("%d",arr+i);

		printf("%lld\n",CountTotalPairs(arr,n));

		free(arr);

		arr = NULL;

	}

	return 0;

}