计算 nlogn 中的反转

Question

考虑一个数组“a”。如果 a[i] > a[j] 且 i < j.

，两个元素 a[i] 和 a[j] 形成反转

例如，给定

int a[5] = {2, 3, 8, 6, 1}

这有 5 个“逆”：

(8,6) (2,1) (3,1) (8,1) (6,1)

我的作业是编写一个 C++ 程序来计算数组中“逆”对的数量，运行时间缩放为 O(n logn)

我的代码的运行时间为 O(n²):

int nghichdao(int a[], int n)
{
    int d = 0;
    for (int j = 1;j < n;j++)
        for (int i = 0;i < j;i++)
            if (a[i] > a[j]) {
                d++;
                cout << "(" << a[i] << "," << a[j] << ")" << endl;
            }
    return d;
}

如何将其改进为 O(n logn)？

Answer 1

使用归并排序实现 N*logN 的倒置计数。请参阅此http://www.geeksforgeeks.org/counting-inversions/

Answer 2

在混合步骤之前，提前对齐是O(nlogn)，合并的同时只比较值，这样O(nlogn)才有可能！