修改归并排序求数组逆序对

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

例如数组<2,3,8,6,1>的逆序对有(2,1) (3,1) (8,1) (6,1) (8,6)。

如可以通过修改归并排序来求逆序对数量。

int merge_sort(int A[], int p, int r) {
    if (p < r) {
        int inversions = 0;
        int q = (p + r) / 2;
        inversions += merge_sort(A, p, q);
        inversions += merge_sort(A, q + 1, r);
        inversions += merge(A, p, q, r);
        return inversions;
    } else {
        return 0;
    }
}

int merge(int A[], int p, int q, int r) {
    int i, j, k, inversions = 0;

    int n1 = q - p + 1;
    int n2 = r - q;

    int L[n1];
    int R[n2];

    for (i = 0; i < n1; i++) L[i] = A[p + i];
    for (j = 0; j < n2; j++) R[j] = A[q + j + 1];

    for(i = 0, j = 0, k = p; k <= r; k++) {
        if (i == n1) {
            A[k] = R[j++];
        } else if (j == n2) {
            A[k] = L[i++];
        } else if (L[i] <= R[j]) {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
            inversions += n1 - i;
        }
    }

    return inversions;
}

inversions += n1 - i;

因为L[]和R[]是已经排好序的子数组，例如L=｛2,4,5｝R=｛1,3,6｝

2>1,所以2后面的值（4,5）也肯定大于1，

有n1-i即3-0对逆序对（2,1）（4,1）（5,1）。

同理可以求得其他逆序对。

来自算法导论

最后

以上就是无语魔镜为你收集整理的修改归并排序求数组逆序对的全部内容，希望文章能够帮你解决修改归并排序求数组逆序对所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。