归并排序

约 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分治比较难，这里不作介绍

归并排序复杂度分析

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

假设 $n$ 是 $2$ 的幂，从而总可以把它分成均为偶数的两部分。

对于 $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$$

回忆我们假设 $n$ 是 $2$ 的幂，但对于其他情况，答案几乎是一样的