algorithm - 计算数组中的反转

Question

我正在设计一种算法来执行以下操作:给定数组 A[1... n] , 对于每个 i < j , 找到所有反转对使得 A[i] > A[j] .我正在使用合并排序并将数组 A 复制到数组 B，然后比较这两个数组，但我很难看到如何使用它来查找倒置次数。任何提示或帮助将不胜感激。

Answer 1

所以，这是 java 中复杂度为 O(n log n) 的解决方案。

long merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0;
    long count = 0;
    while (i < left.length || j < right.length) {
        if (i == left.length) {
            arr[i+j] = right[j];
            j++;
        } else if (j == right.length) {
            arr[i+j] = left[i];
            i++;
        } else if (left[i] <= right[j]) {
            arr[i+j] = left[i];
            i++;                
        } else {
            arr[i+j] = right[j];
            count += left.length-i;
            j++;
        }
    }
    return count;
}

long invCount(int[] arr) {
    if (arr.length < 2)
        return 0;

    int m = (arr.length + 1) / 2;
    int left[] = Arrays.copyOfRange(arr, 0, m);
    int right[] = Arrays.copyOfRange(arr, m, arr.length);

    return invCount(left) + invCount(right) + merge(arr, left, right);
}

这几乎是正常的合并排序，整个魔法都隐藏在合并函数中。 请注意，在排序时，算法会删除倒置。 合并时，算法会计算移除的倒置次数(有人可能会这样说)。

唯一移除反转的时刻是算法从数组右侧获取元素并将其合并到主数组时。 本次操作去除的反转数即为待合并的左数组剩余的元素数。

希望它的解释足够。