用归并排序算法merge_sort( )求解 逆序对的数量 降低时间复杂度为 nlogn

题目简述
给定一个序列有n个数，求n个数中逆序对的个数，逆序对的定义：i < j && a[i] > a[j]。

输入格式

第一行包含一个整数n。

第二行包含 n 个整数（所有整数均在1~1e9范围内），表示整数数列。

输出格式

输出一个整数，表示逆序对的个数。

输入样例：

6
2 3 4 5 6 1
输出样例：

5

归并排序应用
归并排序是将一个序列分成两个有序的序列，归并两个有序序列，归并后则该序列有序，是基于分治的思想。

根据逆序对的定义，我们也可以使用分治的算法来求解逆序对的数量。如图：

我们将序列分成两部分，我们发现逆序对的数量是三种逆序对数量的和：

左边序列的逆序对
右边序列的逆序对
横跨中间的逆序对

利用归并排序，我们可以分别求解左边序列的逆序对的数量和右边序列的逆序对的数量。如何求解横跨中间逆序对的数量呢？
归并排序中归并的过程：

意味着在归并两个序列的过程中，我们就可以计算出横跨中间的逆序对的数量。
时间复杂度O(nlogn)，空间复杂度O(N)

//下面的代码是在归并排序的基础上做了改进，不同在于有返回值，递归终止条件，归并第二个序列。
int merge_sort(int a[], int l ,int r){
    //序列只有一个数
    if (l == r) return 0;
    //递归左边和右边
    int mid = l + r >> 1;
    int res = merge_sort(a, l , mid) + merge_sort(a, mid + 1, r);
    //归并的过程
    int i = l , j = mid + 1, k = 0;
    while (i <= mid && j <= r){
        if (a[i] <= a[j]) t[k++] = a[i++];
        else{
            t[k++] = a[j++];
            res += mid - i + 1;
        }
    }
    while (i <= mid) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];
    
    //还原数组
    for (int i = 0 , j = l ; j <= r ; i ++ , j ++) a[j] = t[i];
    
    return res;
}