重点：归并排序 的变种
import java.util.*;
public class Solution {
public static long ans = 0;
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
public int InversePairs(int[] nums) {
if (nums.length == 0) return 0;
mergeSort(nums, 0, nums.length - 1);
return (int)(ans % 1000000007);
}
public void mergeSort(int[] array, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
merge(array, left, mid, right);
}
public void merge(int[] array, int left, int mid, int right) {
int l_pos = left;
int r_pos = mid + 1;
int pos = left;
int[] tempArray = new int[array.length];
while (l_pos <= mid && r_pos <= right) {
if (array[l_pos] <= array[r_pos]) {
tempArray[pos++] = array[l_pos++];
} else {
tempArray[pos++] = array[r_pos++];
// 计算逆序对
// 奥妙之处 此时发现逆序对 计数增加mid-l_pos+1，因为当前面的数组值array[l_pos]大于后面数组值array[r_pos]时；则前面数组array[l_pos]~array[mid]多个元素都是大于array[r_pos]的
ans += (mid - l_pos + 1);
ans %= 1000000007;
}
}
while (l_pos <= mid) {
tempArray[pos++] = array[l_pos++];
}
while (r_pos <= right) {
tempArray[pos++] = array[r_pos++];
}
// 将排序后的结果复制回原数组
while (left <= right) {
array[left] = tempArray[left];
left++;
}
}
}