ALGORITHMS

逆序对数量

假设A[1..n]是一个有n个不同数的数组。若i<j且A[i]>A[j]，则对偶(i，j)称为A的一个逆序对(inversion)

求给定长度为n数组中逆序对的数量。要求最坏的情况需要 \(Θ(nlgn)\) 时间

整体思想是通过分治，将问题规模不断缩小。这里，采用对归并排序进行一定的修改，从而解决此问题。

在归并排序中，每次将数组分为两个规模相同的部分。

如上图所示，假设左边的为数组A，右边的为数组B。

要求逆序对的数量，可分为以下三部分：

逆序对中的两个元素全在左边，全在右边，或一左一右。

在同侧时，直接递归即可求解。故重点在异侧。

考虑归并排序时，左右两部分已经是有序的。分别设置指针i、j，指向这两个数组A、B。而后按照归并排序的Merge方式移动这两个指针。

此时，若仅进行数组有序归并，则为一个归并排序。但为求逆序对数量，在其中增加一些步骤。

根据归并排序的性质，任意两个合并的数组一定是相邻的。即不失一般性，可取A[start...mid]、B[mid+1...end]. 且此时A、B均有序。

当A[i] > B[j]时，立即可得在A数组中i及之后的元素均大于B[j]。则逆序对的数量count += mid - i + 1。且获得所有以B[j]作为第二元的逆序对数量。如此循环至遍历完A、B数组。也就的到了所有的异侧逆序对。

考虑边界条件：

  • 当 i 至A的尾部，而 j 未至时，归并排序中的做法是复制B中剩余的值至数组剩余部分。假设此时j==k。B[k…end]中任意元素大于A中所有元素。故不对count进行任何操作
  • 当 j 至B的尾部，而 i 未至时，复制A中剩余的值至数组剩余部分。注意，以B[j]为逆序对第二元的逆序对数量已经在 j 到达B的尾部操作中完成。即B中已经没有元素能作为逆序对第二元。故不对count进行任何操作。

注意到，能够通过此方法增加逆序对数量而不失一般性的原因在于A、B是有序的，故在计算逆序数量的同时，必须保证递归”回退”过程中A、B始终有序。即对数组进行排序。

由于count的计算仅仅发生在A[i] > B[j]时，且为一赋值语句。故不影响整体时间复杂度。即整体时间复杂度与归并排序相同: \(Θ(nlgn)\) 。

以下附上完整代码：

class Inversion{

private:int count = 0;

public:int inversionCount(int* array, int n){
    mergeSort(array, 0, n - 1);
    return count;
    }

private: void mergeSort(int* array, int first, int last){
    if(first == last)
        return;

    int mid = (first + last) / 2;
    mergeSort(array, first, mid);
    mergeSort(array, mid+1, last);
    merge(array, first, mid, last);
    }

private: void merge(int* array, int first, int mid, int last){
    int i = first, j = mid + 1, k = 0;
    int temp[last - first + 1];
    memset(temp, 0, last-first+1);

    while (i <= mid && j <= last){
        if(array[i] < array[j]){
            temp[k] = array[i];
            k++, i++;
        }
        if(array[i] > array[j]){
            temp[k] = array[j];
            k++, j++;
            count += mid - i + 1;
        }
    }

    while (i <= mid) temp[k++] = array[i++];
    while (j <= last) temp[k++] = array[j++];

    for (int l = 0; l < last - first + 1; ++l) {
        array[l + first] = temp[l];
    }
}
};