跳转至

归并排序

约 544 个字 47 行代码 预计阅读时间 2 分钟

把原问题“把n个元素排成升序”,分解成“把前\frac n2个排成升序”和“把后\frac n2个排成升序”两个子问题,然后合并这两个问题的解

Q1:为什么是分成两半?

A1:分成两半使问题规模缩小一半,这样从 n 的规模缩小到 1 的规模,只花了 \log_2 n 次,这也是复杂度中 \log_2 n 的来源

Q2:处理斐波那契数列时,终止状态是 n\le 2 时,返回1,那么归并排序如何处理终止状态?

A2:当问题规模缩小到 1 时,长度为 1 的数组自然是升序的,所以不用处理,直接返回即可

Q3:如何合并子问题?

A3:此时问题是两个升序序列合并,两个序列从头开始,谁首元素小,谁就放到前面,当一个序列遍历完,另一个序列全部放到末尾

实现

int TmpArray[N];
void Merge(int Lpos,int Rpos,int RightEnd)
{
    int st=Lpos,LeftEnd=Rpos-1,TmpPos=Lpos;
    while(Lpos<=LeftEnd && Rpos<=RightEnd)
    {
        if(a[Lpos]<=a[Rpos])
            TmpArray[TmpPos++]=a[Lpos++];
        else
            TmpArray[TmpPos++]=a[Rpos++];
    }
    while(Lpos<=LeftEnd)
        TmpArray[TmpPos++]=a[Lpos++];
    while(Rpos<=RightEnd)
        TmpArray[TmpPos++]=a[Rpos++];
    for(;st<=RightEnd;--RightEnd)
        a[RightEnd]=TmpArray[RightEnd];
}
void MSort(int left,int right)
{
    if(left>=right)
        return;
    int center=(left+right)/2;
    MSort(left,center);
    MSort(center+1,right);
    Merge(left,center+1,right);
}
void MergeSort()
{
    MSort(0,n-1);
}

归并排序求逆序对的数量

逆序对:若 i<j,a_i>a_j,则称 a_i,a_j 是一个逆序对

合并序列时,对于后半序列第 i 个元素,将要合并时,前半序列比他小的元素个数已知

long long ans=0;
void Merge(int Lpos,int Rpos,int RightEnd)
{
    ...
    while(Lpos<=LeftEnd && Rpos<=RightEnd)
    {
        if(a[Lpos]<=a[Rpos])
            TmpArray[TmpPos++]=a[Lpos++];
        else
        {
            TmpArray[TmpPos++]=a[Rpos++];
            ans+=LeftEnd-Lpos+1;
        }
    }
    ...
}

cdq分治比较难,这里不作介绍

归并排序复杂度分析

归并排序是分析递归例程方法的经典实例,给运行时间写出一个递归关系。

假设 n2 的幂,从而总可以把它分成均为偶数的两部分。

对于 n=1,归并排序所用时间是常数,我将记为 1

否则,对 n 个数归并排序的用时等于完成两个大小为 \frac n2 的递归排序所用的时间再加上合并的时间,它是线性的

下述方程给出表示

T(1)=1
T(n)=2T(\frac n2)+n

对上式求解

\frac{T(n)}n=\frac{T(\frac n2)}{\frac n2}+1
\frac{T(\frac n2)}n=\frac{T(\frac n4)}{\frac n4}+1
...
\frac{T(2)}2=\frac{T(1)}1+1
\frac{T(n)}n=\frac{T(1)}1+\log_2 n
T(n)=n+n\log_2 n

回忆我们假设 n2 的幂,但对于其他情况,答案几乎是一样的