1.思路

这题其实挺难想到的，我也是看视频才直到这题要用归并排序做(只能说能想到这种方法的人都太变态了，毕竟归并排序的应用场景不多)。好了，不多废话，直接来分析思路。

我们先来回想一下归并排序的步骤：

①确定分界点mid，mid为区间 l到 r 的中间位置上面的点

②递归排序左右两边merge_Sort(a, l, mid) 、merge_Sort(a, mid + 1, r)

③将排序好的左右两边合并（难点）

这里我们可以先假设merge_Sort(a, l, r)能计算出区间所有的逆序对。而计算逆序对的关键步骤在于归并，当我们开始归并的时候可以发现如果左边的区间指向的数大于右边指向的数时，即a[i] > a[j];我们可以发现区间从i到mid都于j都构成了一个逆序对(合并的时候左右两边都是排好序的，并且是递增的)，此时记录逆序对数量res+=mid-i+1因为区间[i, mid]有mid-i+1个数，后面的操作和归并排序都一样，最后返回res逆序对数量就行。

(这题其实很难想到，所以多思考一下，如果仔细思考当领悟了这个算法之后就觉得这个算个真的很巧妙)

2.代码

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()) {
            int n = in.nextInt();
            int[] a = new int[n];
            for(int i = 0; i < n; i++)
                a[i] = in.nextInt();
            System.out.println(merge_Sort(a, 0, n - 1));
        }
        in.close();
    }
    public static long merge_Sort(int[] a, int l, int r) {
        if(l >= r) return 0;      //如果区间只有一个元素，或者没有元素直接返回0
        int mid = l + r >> 1;   //取区间[l,r]中间位置的点
        long res = merge_Sort(a, l, mid) + merge_Sort(a, mid + 1, r);
        int[] n = new int[r - l + 1];   //创建一个临时数组，用于保存归并之后的数组
        int i = l, j = mid + 1;     //要合并的两个数组开始的位置
        int k = 0;                  //记录临时的下标
        while(i <= mid && j <= r) {     //合并数组
            if(a[i] <= a[j])         //左边区间必须大于右区间才能算一次逆序对
                n[k++] = a[i++];
            else {    
                //因为a的左右两边都是排好序的
                    //所以如果a[i]>a[j]就代表左区间[i,mid]所有数都肯定大于a[j]
                       //所以可以记录mid-i+1个逆序对
                res += mid - i + 1;     
                n[k++] = a[j++];
            }
        }
        while(i <= mid)             
            n[k++] = a[i++];
        while(j <= r)
            n[k++] = a[j++];
        for(int t = 0; t < k; t++)      //将排序并合并完的临时数组保存到原数组中
            a[l + t] = n[t];
        return res;     //返回逆序对数量
    }
}

3.复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)