【Algorithms 4】算法（第4版）学习笔记 05 - 2.2 归并排序

前言

本章节主要内容是 归并排序，除此之外还有 排序算法的复杂度 以及 稳定性 的相关内容。

本章节中间有穿插说明 比较器（Compartor），不过本文暂且略过这一内容，感兴趣的朋友建议移步视频自行学习总结。

参考目录

• B站 普林斯顿大学《Algorithms》视频课
  （请自行搜索。主要以该视频课顺序来进行笔记整理，课程讲述的教授本人是该书原版作者之一 Robert Sedgewick。）
• 微信读书《算法（第4版）》
  （本文主要内容来自《2.2 归并排序》）
• 官方网站
  （有书本配套的内容以及代码）

学习笔记

注1：下面引用内容如无注明出处，均是书中摘录。
注2：所有 demo 演示均为视频 PPT demo 截图。

1：归并排序的简单演示

1.1：基本思路

归并排序基本思路：

• 数组一分为二
• 每一半 递归 排序
• 合并两半

1.2：归并排序的 demo 演示

对于归并排序，Sedgewick 教授的视频进行了分步演示，下面截图进行简单说明。

排好序的两个子数组：

在原数组的基础上复制一个辅助数组：

需要三个下标来进行操作：
i、j分别是两个比较的子数组的下标，k是原数组的下标。

比较两个子数组的数据，将较小的值放回原数组：

如果两个值相同，则将左侧子数组的值放回原数组：

如果其中一个子数组已经没有元素，则另一个子数组的元素直接放回原数组：

1.3：代码实现

edu.princeton.cs.algs4.Merge#merge

edu.princeton.cs.algs4.Merge#sort

2：自顶向下的归并排序

上面分步实现的归并排序是属于自顶向下的归并排序。官网给出了归并的分步结果图：

（截图自官网）

2.1：比较次数与访问次数的证明

比较次数和访问次数是衡量一个算法优劣与否的重要参考标准，因此这里给出了相关的证明。

（截图自视频 PPT）

每次归并最多需要访问数组6N次：

• 2N次用来复制
• 2N次用来将排好序的元素移动回去
• 另外最多比较2N次

视频中，教授使用长度 N 为 2ⁿ 的数组来证明：
$$D(N)=2D(N/2)+N，N>1，且D(1)=0$$

一共有三种证明方式，但说实话我看了几遍还是没太懂怎么算的（哭），先把证明方式贴出来：

方式一：图形法证明

方式二：数学方式证明

方式三：数学归纳法证明

这里再贴一下书里面的相关证明帮助理解：

命题F。对于长度为N的任意数组，自顶向下的归并排序需要½NlgN至NlgN次比较。

书中关于命题 F 的证明，相对来说容易理解一些，可以自行参考学习。

2.2：代码优化

归并排序虽然速度比较快，但是也有一些缺点，因此也提出了一些优化方案：（这里列出对应的章节）

• 2.2.2.1 对小规模子数组使用插入排序
• 2.2.2.2 测试数组是否已经有序
• 2.2.2.3 不将元素复制到辅助数组

2.3：优化后代码实现

edu.princeton.cs.algs4.MergeX#sort

3：自底向上的归并排序

自顶向下的归并排序使用了递归的方式，为了减少递归的操作，又提出了自底向上的归并排序。

（截图自官网）

3.1：代码实现

edu.princeton.cs.algs4.MergeBU#sort

4：排序算法的复杂度

这里使用了决策树来进行说明，不过我觉得这一部分书本的说明不是很好，有些地方说得云里雾里的……

例如：

一眼看过去不知道是啥。然后看教授的PPT：

还有对于命题 I 的描述，每一个字我都认识，愣是读了好几遍才读通顺：

命题I。没有任何基于比较的算法能够保证使用少于lg（N!）～NlgN次比较将长度为N的数组排序。

再来看看视频里是怎么说的：

Any compare-based sorting algorithm must use at least lg（N!）～NlgN compares in the worst-case.
任何基于比较的排序算法，在最坏的情况下需要使用 lg（N!）～NlgN 次比较。

贴一下完整的 PPT 截图，一目了然：

证明：

• 假设数组由N个不同的值 a1 到 aN 组成。
• 最坏的情况由决策树的 高度 h 决定。
• 高度为 h 的二叉树最多有 2^h 叶子节点。
• N! 不同的排序 => 至少 N! 叶子节点。

根据书里面的说明再完善一下：

从比较树观察得到的第一个重要结论是这棵树应该至少有 N! 个叶子结点，因为 N 个不同的主键会有 N! 种不同的排列。


二叉树的一个基本的组合学性质就是高度为 h 的树最多只可能有 2h 个叶子结点，拥有 2h 个结点的树是完美平衡的，或称为完全树。

5：稳定性

这一部分回顾了目前所讲到的四种算法：插入排序、选择排序、希尔排序以及归并排序。

Q：哪些算法是稳定的？
A：插入排序和归并排序。（选择排序和希尔排序不稳定。）

5.1：插入排序：稳定

插入排序中，相同的值不会越过彼此。

通常而言，看一个排序是否稳定，一般是看它是否有长距离的交换可能使得一条记录越过某一条相同值的记录。

5.2：选择排序：不稳定

5.3：希尔排序：不稳定

5.4：归并排序：稳定

只要归并操作是稳定的，那么归并排序算法就是稳定的；操作是否稳定，取决于代码怎么写。

（完）