问题

二分归并排序：对 $n$ 个不同的数构成的数组 $A[1\dots n]$ 进行排序，其中 $n=2^k$

解析

归并

将任意的两个升序序列 $A$ 和 $B$ 合并为一个升序序列 $C$
主要步骤
比较 $A$ 序列中的首元素 $a_i$ 和 $B$ 序列中的首元素 $b_i$
若 $a_i \lt b_i$ 则将 $a_i$ 加到 $C$ 序列末尾，否则将 $b_i$ 加到 $C$ 序列末尾
重复以上操作直到 $A$ 序列或 $B$ 序列为空
将非空序列直接加到 $C$ 序列末尾
正确性证明
对于升序序列 $A$ 和 $B$ ，将两个序列的首元素分别记为 $a_i$ 和 $b_j$
因为 $A$ 和 $B$ 是升序序列，所以有 $(\forall k \gt i ,a_i<a_k )(\forall p>j,b_j<b_p)$
若 $a_i<b_j$ 则 $\forall p>j,a_i \lt b_j \lt b_p$ ,此时 $a_i$ 就是两个序列中最小的，将 $a_i$ 放入 $C$ 序列末尾中即可

此时 $A$ 序列中最小的数变为了 $a_{i+1}$
同理，当 $b_j \lt a_i$ 只需将 $b_j$ 放入 $C$ 末尾即可
因为每次放入 $C$ 序列末尾的元素总小于 $A,B$ 中其他元素，也就是 $\forall i \lt k,c_i\lt c_k$ 也就说 $C$ 也是一个升序序列
复杂度
每个元素会被放入 $C$ 序列一次，若 $A,B$ 序列长度分别为 $n,m$ ，则总操作次数为 $n+m$ ,归并操作的复杂度为 $O(n+m)$

归并排序

我们已经得到了一个在线性时间复杂度内合并两个有序序列的算法，只要事先得到两个有序序列，就可以合并得到一个完整的有序序列了
对于这个序列，我们可以从序列中间分开，先排序好前一半，再排序好后一半，最后归并整个序列
对于前一半序列，同样可以用归并排序的方法，分别排序好前后，在归并，后一半同理
显然只有一个元素的序列本身就是有序的，所以如果序列中只有一个元素，就可以直接结束了

设计

void merge(int A[], int T[], int S[], int len1, int len2)//将长度为len1的序列S和长度为len2的序列T进行归并，结果储存在A中
{
    int p = 0;
    int i = 0, j = 0;
    while (i < len1 && j < len2)
    {
        if(T[i]<S[j])
            A[p++] = T[i++];
        else
            A[p++] = S[j++];
    }
    while (i < len1)
        A[p++] = T[i++];
    while (j < len2)
        A[p++] = S[j++];
}

void mergeSort(int A[], int T[], int len)//递归排序
{
    if (len == 1)
        return;
    int mid = len / 2;
    mergeSort(A, T, mid);//先处理前半
    mergeSort(A + mid, T + mid, len - mid);//处理后半
    merge(T, A, A + mid, mid, len - mid);//对序列进行归并
    for (int i = 0; i < len; ++i)
        A[i] = T[i];
}

分析

显然对于长度为 $n$ 的序列，归并前后两半需要的操作次数为 $n$
对于长度为 $2^k$ 次的序列，所需的操作次数为 $2^k$ ,对于长度为 $1$ 的序列，直接结束递归，所以操作次数为 $1$
可以列出如下等式

$\left.\begin{cases} f(2^k)=2*f(2^{k-1})+2^k & k>0\\ f(2^0)=1 &k=0 \end{cases}\right.$
于是我们可以得出方程组

$\left.\begin{aligned} f(2^k)&=2\times f(2^{k-1})+2^k\\ 2\times f(2^{k-1})&=4\times f(2^{k-2})+2^k\\ 4\times f(2^{k-2})&=8\times f(2^{k-3})+2^k\\ 2^{i}\times f(2^{k-i})&=2^{i+1}\times f(2^{k-i-1})+2^k\\ &\dots\\ 2^k\times f(2^0)&=2^k\times 1\\ \end{aligned}\right.$
累加所有式子

$f(2^k)+2f(2^{k-1})+2^2f(2^{k-2})+\dots + 2^kf(1)=2f(2^{k-1})+2^k+4f(2^{k-2})+2^k+\dots+2^k\times 1$

消去相同项 $f(2^k)=(k+1)\times 2^k$
将 $2^k$ 用 $n$ 替代，则 $k=\log_2^n$ ,总操作次数为 $n\times(\log_2^n+1)$
最终算法复杂度为 $O(n\log_2^n)$

源码

传送门

算法课-归并排序

问题

解析

归并

归并排序

设计

分析

源码