逆序对问题

【问题】

设 $A$ 为一个有 $n$ 个数字的有序集，其中所有数字各不相同，如果存在整数 $i,j$，使得 $1\leq i < j \leq n$ 且 $A[i]>A[j]$，则 $\{A[i],A[j]\}$ 这个有序对称为 $A$ 的一个逆序对

例如：集合 $\{3,1,4,5,2\}$ 的逆序对有 $\{3,1\}$、$\{3,2\}$、$\{4,2\}$、$\{5,2\}$ 共 $4$ 个

逆序对问题，即：对给定的数组序列，求其逆序对的数量

【分析】

从定义上分析，逆序对就是数列中任意两个数满足大的在前小的在后的组合，如果将这些逆序对都调整为顺序，那么整个数列就变的有序

因而容易想到冒泡排序的机制正好是利用消除逆序来实现的，也就是说，交换相邻两个逆序数，最终实现整个序列有序，那么交换的次数即为逆序对的数量

由于冒泡排序本身效率不高，时间复杂度为 $O(n^2)$，对于 $n$ 较大的情况下不适用，一般选用归并排序来解决逆序对问题

【实现】

/*只需修改原有归并程序，当右边序列元素为较小值时，就统计其产生的逆序对数量，即可完成逆序对统计*/
void mergeArray (int a[], int left, int mid, int right, int temp[], int ans) {
    int i = left, j = mid + 1;
    int cnt = 0; //临时数组temp的指针

    while (i <= mid && j <= right) { //比较左右两个子序列
        if (a[i] <= a[j]) //取a[i]与a[j]中的小者放入temp[k]
            temp[cnt++] = a[i++];
        else {
            temp[cnt++] = a[j++];
            ans += mid - i + 1; //统计产生逆序对的数量
        }
    }
    while (i <= mid) //第一个子序列未处理完
        temp[k++] = a[i++];
    while (j <= right) //第二个子序列未处理完
        temp[k++] = a[j++];
 
    for(int i = 0; i < k; i++) //将数组temp中的值返回数组a
        a[left+i] = temp[i];
}