归并排序

问题转化：求逆序对就是统计有多少个前大后小的数对，问题和归并两个有序数组求前大后小数对一样。所以现在的问题变为统计子问题中逆序对的个数。

递归模型变形：递归按照标准的归并排序来，注意的是统计个数，当出现nums[i]>nums[j]时，统计所有前半段区间内比nums[j]大的数及为ans+=m-i+1;（为了理解方便 1 ~ m 前半段，m+1 ~ r 后半段）

边界注意：

  • i == r+1当前半段已经统计完，剩下后半段归并，证明j后的数都是比nums[m]大的，无需统计
  • j == l+1当后半段统计完，剩下前半段归并，i后的数都比num[l]大，但在之前已经统计个数，无需统计 alt

摘抄自题解内容，仅供学习使用