归并排序——计算逆序数

浏览数：32 / 时间：2015年06月08日

归并排序——计算逆序数

归并排序用了分治的思想，时间复杂度o(N*logN)动态内存的运用可减小空间开销；

归并排序还可用于计算逆序数；

逆序数：序列中位置和大小相反的一对数字；

逆序数=冒泡排序中相邻两个数字交换的次数；

int a[maxn],n;
long long ans; //逆序数一般很大，用long long

void compute_ans(int*a,int begin,int mid,int end)
{
    int len_L=mid-begin+1;
    int len_R=end-mid;
    int *left=new int[len_L+1];   //节约空间
    int *right=new int[len_R+1];

    for(int i=0;i<len_L;i++) left[i]=a[begin+i];
    for(int i=0;i<len_R;i++) right[i]=a[mid+1+i];
    left[len_L]=right[len_R]=INF;   //注意防止越界

    int i,j;i=j=0;
    for(int k=begin;k<=end;k++){
        if(left[i]<=right[j]) a[k]=left[i++];
        else{
            a[k]=right[j++];
            ans+=len_L-i;            //计算逆序数，若仅进行排序，此行删掉；逆序数=冒泡排序交换操作次数
        }
    }
    delete left; //记得释放，若不释放会造成MLE
    delete right;
}

void mergesort(int*a,int begin,int end)
{
    if(begin<end){
        int mid=(begin+end)/2;
        mergesort(a,begin,mid);
        mergesort(a,mid+1,end);
        compute_ans(a,begin,mid,end);
    }
}

int main()
{
    while(cin>>n,n){
        ans=0;
        for(int i=0;i<n;i++) cin>>a[i];
        mergesort(a,0,n-1);
        cout<<ans<<endl;
    }
    return 0;
}