我觉得每次博客时，开头的话语是最难写的，这次就不写了，但是要鼓励自己好好学习！
题意
在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个
逆序对。给你一个数组，求出这个数组中逆序对的总数。
概括：如果a[i] > a[j] 且 i < j， a[i] 和 a[j] 构成一个逆序对。
样例
序列 [2, 4, 1, 3, 5] 中，有 3 个逆序对 (2, 1), (4, 1), (4, 3)，则返回 3
这题理解起来不是很难的，但是麻烦的地方就是时间复杂度。如果用常规的做法，肯定会超时，所以只能用非常规的方法了，但是这里贴出常规的代码，就当是给自己一个警示！
1.常规的方法(超时)
常规的方法非常简单，这里就不再解释了
public static long reversePairs(int[] A) {
int sum = 0;
for(int i = 0; i < A.length - 1; i++){
for(int j = i + 1; j < A.length; j++){
if(A[i] > A[j]){
sum++;
}
}
}
return sum;
}
2.非常规的方法--归并排序
归并排序有一个特点就是：它是将一个数组分为两部分，然后将两部分分别进行排序，在合并之前，两个部分之间的数字index大小不会变化，例如：1 4 3 2分成两部分后分别是{1,4}和{3,2},排序之后是{1,4}和{2,3},在排序之前，{1,4}在{2,3}的前面，而在排序之后(合并之前)，{1,4}也在{2,3}的前面，所以经过排序（合并之前），两个部分之间的顺序不会变
归并排序最终分解是，将两个数字分成了两个部分，基于归并排序的上面那个特点，两个数字的位置不会因为大小而改变，因为这时候还没有合并，只是两个部分。求逆序对的话，就看看这两个符不符合。就这样，先两两配对，后面在44配对，由于之间的22配对，已经将44配对每一个部分的内部逆序对计算出来，所以只需要计算44配对之间的逆序对。
假设，我们用num来记录逆序对的个数，当我们在合并的两个部分时，会分别的比较两个部分的值，先将较小的值放在一个新的数组里面去。假设两个部分分别是用i和j来控制(其中i <= mid && j <= height)，数组为nums[]，如果nums[i] <= nums[j]，这个直接放入新的数组里面，因为它不符合逆序对的规则(逆序对的规则是：n < m && nums[n] > nums[m])；但是当nums[i] > nums[j]时，需要注意的是，这时候就符合逆序对的规则了，但是这里不是简单的加1。想一下，当前nums[i] > nums[j]，那么num[i + 1~ mid]之间的数字是不是也大于nums[j],所以当前符合要求的个数是: mid - i + 1个数字(但是这里可能有人疑问，为什么要把nums[i + 1 ~ mid]的情况加进去，想一下，如果这里的nums[j]只与nums[i]配对的话，经过本次循环，j++，后面的nums[i + 1~ mid]不会在nums[j]，因此 j 已经变了，所以这里必须将nums[i + 1 ~ mid]的情况考虑进去).
理解了上面的解释，看下面的代码才会很好的理解：
private static int result = 0;
public static long reversePairs(int[] A) {
mergeSort(A, 0, A.length - 1);
return result;
}
private static void mergeSort(int nums[], int low, int height) {
if (low < height) {
int mid = (low + height) / 2;
mergeSort(nums, low, mid);
mergeSort(nums, mid + 1, height);
merge(nums, low, mid, height);
}
}
private static void merge(int[] nums, int low, int mid, int height) {
int temp[] = new int[height - low + 1];
int i = low;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= height) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums [j++];
result += (mid-i+1);
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= height) {
temp[k++] = nums[j++];
}
for (int n = 0; n < temp.length; n++) {
nums[n + low] = temp[n];
}
}
