归并排序

说明

通过递归的方式进行排序

时间复杂度：O(nlogn)

参数说明:

A[]为原数组，归并排序对[l, r)区间进行排序，

T[]为辅助数组，需要定义这样一个数组，作为参数传进去

使用方法

1. 定义辅助数组T[]，求逆序数的话需要将cnt置零
2. merge_sort(A, l, r, T); l为区间左端点，r为区间右端点的下一个点
3. 数组A中[l, r)已排好序

Tips

• 注意边界范围是[l, r)
• 如果求解逆序数，需要保证cnt初始化为0

模版

//归并排序
void merge_sort(int *A,int l,int r,int *T){
    if (r-l>1) {
        int m=l+(r-l)/2;                    //划分
        int p=l,q=m,i=l;
        merge_sort(A, l, m, T);             //递归求解
        merge_sort(A, m, r, T);             //递归求解
        while (p<m||q<r)
            if (q>=r||(p<m&&A[p]<=A[q]))
                T[i++]=A[p++];              //从左半数组复制到临时空间
            else
                T[i++]=A[q++];              //从右半数组复制到临时空间
        for (i=l; i<r; i++)
            A[i]=T[i];                      //从辅助空间复制回A数组
    }
}

//归并排序求逆序数
void merge_sort_inversion(int *A,int l,int r,int *T,int *cnt){
    if (r-l>1) {
        int m=l+(r-l)/2;                    //划分
        int p=l,q=m,i=l;
        merge_sort_inversion(A, l, m, T,cnt);             //递归求解
        merge_sort_inversion(A, m, r, T,cnt);             //递归求解
        while (p<m||q<r)
            if (q>=r||(p<m&&A[p]<=A[q]))
                T[i++]=A[p++];              //从左半数组复制到临时空间
            else{
                T[i++]=A[q++];              //从右半数组复制到临时空间
                *cnt += m-p;
            }
        for (i=l; i<r; i++)
            A[i]=T[i];                      //从辅助空间复制回A数组
    }
}

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

NYOJ117 求逆序数(归并排序记录次数)

LL sum;
LL a[N],b[N];
void mix(LL start,LL mid,LL end)
{
    LL i=start,j=mid+1,k=0;
    while(i<=mid&&j<=end)
    {
        if(a[i]<=a[j])
        {
            b[k++]=a[i++];
        }
        else
        {
            sum+=mid+1-i;
            b[k++]=a[j++];
        }
    }
    while(i!=mid+1)
        b[k++]=a[i++];
    while(j!=end+1)
        b[k++]=a[j++];
    for(LL i=0; i<k; i++)
        a[start++]=b[i];
}
void mergesort(LL start,LL end)
{
    LL mid=(start+end)/2;
    if(start<end)
    {
        mergesort(start,mid);
        mergesort(mid+1,end);
        mix(start,mid,end);
    }
}

int main()
{
    LL t;
    scanf("%lld",&t);
    while(t--)
    {
        LL n;
        sum=0;
        scanf("%lld",&n);
        for(LL i=0; i<n; i++)
            scanf("%lld",&a[i]);
        mergesort(0,n-1);
        printf("%lld\n",sum);
    }
    return 0;
}