计算数组的逆序对个数

问题：给定一个数组A，A存有n个互不相同的整数。定义：若iA[j],则称(i,j)为A的一个逆序对(inversation)。设计一个O(nlogn)算法求A中逆序对个数。

显然最坏情况下逆序对有n(n-1)/2个,如;5 4 3 2 1完全逆序，逆序对有(5-1)*5/2=10对。若用暴力来求解，则时间复杂度为O(n²),显然比这不是一个好的算法。下面考虑用归并排序的类似方法来解决这个问题。

首先，对于一个长度为n的数组A[0...n-1],我们可以将它分为两个长度为n/2子数组L[0...n1]=A[0...n/2]和R[0...n2]=A[n/2+1...n-1],总的逆序对=L中的逆序对+R中的逆序对+横扫L和R的逆序对；

比如将数组 2 3 8 6 1分为两部分 L: 2 3 8和 R:6 1,于是左边L中逆序对0个，右边R中逆序对(6,1)共1对,那么横扫L与R的有(2,1),(3,1),(8,6),(8,1)一共4对，于是总的对数为0+1+4=5对。现在问题的难点就是如何求中间横扫那部分的逆序对，如果暴力来求，必然O(n²)。我们先来看看这样的一个事实，如果将L排好序，将R也排好序，这时候中间横扫那部分的逆序对个数不会改变，这是因为L与R是分开的。这样以来，我们可以用归并排序的思路设计这个算法，基于这样设计之所以正确在于每一次子序列的排序的归并都是在该该序列逆序对计算完成后进行的。C++代码如下：

#include<iostream>
using namespace std;
#define MAX_VALUE 12343564
int Count_Reversations(int *A, int n);
int Merge_Reversations(int *A, int p, int r);
int main(){
     int a[5] = { 2,3,8,6,1 };
     cout << Count_Reversations(a, 5) << endl;
     return 0;
}
int Count_Reversations(int*A, int n){ //接口函数
     return Merge_Reversations(A, 0, n - 1);
}
int Merge_Reversations(int *A, int p, int r){
     if (p>=r)
          return 0;
     int i, j, k,mid,n1,n2, reversations = 0;
     mid = (p + r) >> 1;
     int next_count= Merge_Reversations(A, p, mid) + Merge_Reversations(A, mid + 1, r);
     n1 = mid - p + 1;
     n2 = r - mid;
     int *R = new int[n2 + 1];
     int *L = new int[n1 + 1];
     for (i = 0; i < n1; i++)
          L[i] = A[i + p];
     for (j = 0; j < n2; j++)
          R[j] = A[j + mid + 1];
     L[n1] = R[n2] = MAX_VALUE; //设置为最大值，当做哨兵
     i = j = 0;
     for (k = p; k <= r; k++){
          if (L[i]>R[j]){
                 reversations +=n1-i;
                 A[k] = R[j++];
     }
     else
         A[k] = L[i++];
}
    delete[]R, L;
    return reversations +next_count;
}

原文链接: https://www.cnblogs.com/td15980891505/p/5143866.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍