题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

方法

参考：https://blog.csdn.net/lzq20115395/article/details/79554591
参考：https://wiki.jikexueyuan.com/project/for-offer/question-thirty-six.html

思路

直接法：50%
归并排序：75%
改进归并排序：100%

在归并排序实现的代码的中，其实只需要在归并排序中添加1行代码即可实现效果。
分析原因：
归并排序的思路是将数组分割成左右两部分，先分别将左右两个子序列排序，再合并。计算逆序对个数，就在合并的过程实现。
归并排序将数组分割成左右两部分，那么左边的任意一个元素，相对于右边数组的任意元素，在原始数组上都是在前面的。比如7、5、6、4，分割成7、5和6、4，那么7、5的两个数字全都在6、4前，这个规律在之后会用到
假设两部分数组已经有序，是5、7和4、6。那么，在合并的过程中，使用两个指针分别指向5、7和4、6的首个元素。合并的过程不做赘述。直接从例子上分析，将4先加入到合并数组中，接着是5加入，5加入的同时，由于合并数组内有4，而4这个元素，是来自右边数组的，5比4大，所以5->4组成一个逆序对。接着6加入，接着7加入，7加入的同时，由于合并数组内有4、5、6，其中4、6是来自右边数组的，那么可以原先数组中就存在7->4, 7->6的逆序对。
所以其实，左边数组元素加入合并数组时，合并数组中有多少个元素来自右边数组，该元素在原数组中就存在多少逆序对。
通过这样的关系，就可以计算出逆序对的数量

改进归并

完了，写到这里觉得我一开始写的归并和别人改进的归并时间复杂度没什么区别。gg

代码

function InversePairs(data) {
  if (data.length < 2) return 0
  let copy = [].concat(data)
  let count = mergeSort(data, copy, 0, data.length - 1)
  return count % 1000000007
}

function mergeSort(data, copy, s, e) {
  if (s === e) return 0
  let middle = Math.floor((e - s) / 2)
  let left = mergeSort(copy, data, s, s + middle)
  let right = mergeSort(copy, data, s + middle + 1, e)
  let count = 0
  let pl = s
  let pr = s + middle + 1
  let p = s
  while (pl <= s + middle && pr <= e) {
    if (data[pl] < data[pr]) {
      copy[p++] = data[pl++]
      count += pr - (s + middle + 1)
    } else {
      copy[p++] = data[pr++]
    }
  }
  while (pl <= s + middle) {
    copy[p++] = data[pl++]
    count += pr - (s + middle + 1)
  }
  while (pr <= e) {
    copy[p++] = data[pr++]
  }
  return left + right + count
}