归并排序

                     

贡献者: 有机物

   上文介绍了快速排序,本文将介绍归并排序

   归并排序也是基于分治实现的。

   归并排序的算法步骤:

  1. 确定分界点为 $\dfrac{l + r}{2}$,把一个序列分成两个大小为 $\dfrac{n}{2}$ 的子序列;
  2. 先递归排序两个子序列;
  3. 合并两个已排好序的子序列。

   归并排序的核心就是归并这一步,首先把一个序列分成两个子序列,然后维护两个指针,第一个指针指向第一个子序列的开头,第二个指针指向第二个子序列的开头。其实归并操作就是把两个子序列的值存到一个序列中然后输出出来,具体的做法是:每次判断一下两个指针所指向的值哪一个更小,把较小的的值插入到答案数组中,如果发现其中一个序列的指针已经直到末尾了,那么就退出循环,直接把另一个子序列的后面的值接到答案数组中(如图 $1$ 所示)。前提得保证两个子序列中的值都已排好序。

图
图 1:终止情况

   时间复杂度:

   归并排序的期望时间复杂度为 $\mathcal{O}(n \log_2 n)$,最坏时间复杂度也为 $\mathcal{O}(n \log_2 n)$,可以发现,归并的这一步操作是维护两个指针,两个指针会遍历完整个序列,所以时间复杂度为 $\mathcal{O}(n)$,然后递归每一层,每层有 $\frac{n}{2}$、$\frac{4}{n}$...,一共有 $\log_2 n$ 层,每层时间复杂度为 $\mathcal{O}(n)$,所以总共时间复杂度为 $\mathcal{O}(n \log_2 n)$。归并排序是稳定的。

图
图 2:算法导论中的递归树

   归并排序的代码:

int n, q[N], tmp[N];    // 需要额外开一个临时数组

void merge_sort(int q[], int l, int r)
{
    if (l == r) return;
    int mid = l + r >> 1;   // 分界点
    merge_sort(q, l, mid);  // 递归左边
    merge_sort(q, mid + 1, r);  // 递归右边
    
    int k = 0, i = l, j = mid + 1;  // i 为第一个子序列的起点,j 为第二个子序列的起点

    // 合并两个子序列
    while (i <= mid && j <= r)  // 当两个子序列都能往后走的时候
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];    // 较小者加入临时数组中
        else tmp[k ++ ] = q[j ++ ];
    
    while (i <= mid) tmp[k ++ ] = q[i ++ ]; // 如果第一个子序列还有元素,就直接加
    while (j <= r) tmp[k ++ ] = q[j ++ ];   // 第二个同理
    
    // j < k 可以写成 i <= r,j 为数组中的元素个数
    // i = l 的原因是:要把临时数组的值赋值给原数组原来的位置,因为 l、r 在一直变化
    for (int i = l, j = 0; j < k; i ++ , j ++ ) q[i] = tmp[j];  // 把临时数组赋值给原数组
}

merge_sort(q, 0, n - 1);    // 调用入口

   证明

   接下来证明一下归并排序的正确性,使用数学归纳法来证明。

   首先当序列长度 $n = 1$ 的时候,序列有序,成立。

   假设归并排序算法可以将任意长度小于 $n$ 的序列排好序。

   接下来证明归并排序算法可以将任意长度等于 $n$ 的序列排好序。

   看上面的代码中第 $7$ 行和第 $8$ 行,序列 l, midmid + 1, r 长度都小于 $n$,根据归纳假设,归并排序都可将这两个序列排好序。然后通过归并,可使得两个序列合并为一个有序序列。故对于长度等于 $n$ 的序列,归并排序都可将其排好序。

   所以对于任意长度的序列,归并排序都可将其排好。

   证毕。

                     

© 小时科技 保留一切权利