归并排序

说明

通过递归的方式进行排序

时间复杂度: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数组
    }
}

results matching ""

    No results matching ""