算法设计与分析——逆序对计数

算法设计与分析——逆序对计数

逆序对：当i A[j] 的二元组（A[i] ,A[j]）。

算法流程：

①把数组分为两个子数组A[1...n/2]和A[n/2+1...n]。

②求解S1：仅在A[1...n/2]中的逆序对数目。

   求解S2：仅在A[n/2+1...n]中的逆序对数目。

③求解S3：跨越子数组的逆序对数目（用归并求解，只是在归并排序的基础上加了一个         S3=S3+mid-i+1）。

④S=S1+S2+S3。

#include
using namespace std;
int n;

int MergeCount(int a[],int left,int mid,int right)
{
    int i=left,j=mid+1,b[100],k=0,s3=0;
    for(int l=0;l=right)return 0;
    else
    {
        int mid=(left+right)/2;
        s1=CountInver(a,left,mid);
        s2=CountInver(a,mid+1,right);
        s3=MergeCount(a,left,mid,right);
    }
    return s1+s2+s3;
}

int main()
{
    cin>>n;
    int a[100];
    for(int i=0;i>a[i];
    }
    cout< 
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5651462.html