【Algorithms 4】算法（第4版）学习笔记 04 - 2.1 初级排序算法

前言

完成了第一章的基础学习之后，终于迎来了第二章的排序相关算法的学习。本文主要是对章节 2.1 初级排序算法的整理总结，主要包括 选择排序、插入排序 以及 希尔排序。

值得注意的是，Sedgewick 教授还讲了两节排序的应用：洗牌和凸包算法，但是我掌握得不太好，就不再本文进行说明了，感兴趣的朋友建议移步视频自行学习总结。

参考目录

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

学习笔记

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

1：前置说明

在正式讲解具体的排序算法前，先整理几个相关的概念知识，旁边后续深入。

1.1：全序关系

首先根据 Comparable 接口提出了 全序关系 这一概念，主要有三个特性：

（截图自视频 PPT）

注：在教授的 PPT 里面提出的三个特性分别是：反对称性、传递性和总体性。
但是在官方网站以及书本中我找到的特性分别是：自反性、反对称性和传递性，这里以后者为准。

（截图自官网）

可以看到，官网的描述与书本一致。

1.2：Comparable API 实现 demo

以时间作为一个常见的有序的对象实现了 Comparable 接口。

edu.princeton.cs.algs4.Date

edu.princeton.cs.algs4.Date#compareTo

1.3：排序算法模板

基于前面的 Comparable API，提出了一个排序算法模板，主要包含了 比较对象 的方法 less() 和 交换对象 的方法 exch() ，这两个方法用于操作数据。

方法如下（来自官网）：

private static boolean less(Comparable v, Comparable w) {
   return (v.compareTo(w) < 0);
}
1
2
3

private static void exch(Comparable[] a, int i, int j) {
   Comparable swap = a[i];
   a[i] = a[j];
   a[j] = swap;
} 
1
2
3
4
5

2：选择排序

光看字有点难一下子看明白，来结合教授的 PPT 理解。

2.1：内循环实现过程拆解

（截图自视频 PPT）

实际上最核心的步骤已经展示出来了，即：需要找到后侧未排序的集合中的最小值进行交换。

2.2：代码实现

edu.princeton.cs.algs4.Selection#sort

2.3：特点

总结一下选择排序两个特点：

• 运行时间和输入无关。（平方级别，如果数组一部分已经排好序了，对选择排序时间上没有影响，还是要一遍遍进行扫描。）
• 数据移动是最少的。（线性级别）

3：插入排序

上面的选择排序只和最小的（包括自己）进行交换 —— 对右侧操作，而插入排序则是和已经排序好的部分进行交换 —— 对左侧操作。

3.1：内循环实现过程拆解

（截图自视频 PPT）

3.2：代码实现

edu.princeton.cs.algs4.Insertion#sort

3.3：最好的情况与最坏的情况

对于插入排序，不同情况下的数组排序情况有所不同。

最好的情况是：
需要 N-1 次比较和 0 次交换
有序数组，只需要证明后一个值比前一个值大，不需要进行交换。

最坏的情况是：
需要～N²/2 次比较和～N²/2 次交换
逆序数组，且不存在重复值，每个元素都需要移动到数组开头的位置。

3.4：部分有序数组

4：希尔排序

希尔排序是基于插入排序的一种快速排序算法。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。
……
实现希尔排序的一种方法是对于每个h，用插入排序将h个子数组独立地排序。

4.1： 增量选择

希尔排序的关键在于增量序列的选择。

透彻理解希尔排序的性能至今仍然是一项挑战。实际上，算法2.3是我们唯一无法准确描述其对于乱序的数组的性能特征的排序方法。

教授在 PPT 中列举了几项常见的增量序列：

（截图自视频 PPT）

对于上面的几种增量序列，教授进行了简单的说明：

• Shell - 2^N：在 1-sorted 前不会将偶数位置的元素和奇数位置的元素进行比较，性能很差。
• Hibbard - 2^N-1：不错。
• Knuth - 3x+1（ 1/2(3^k-1) ）：容易实现。
• Sedgewick ：根据奇数和偶数分别使用不同增量。（经过（教授本人）大概一年的研究得出的增量序列，性能不错，但无法得知是否是最好的）

当然，维基百科 上有更加详细的增量序列表：

（截图自维基百科）

4.2：代码实现

edu.princeton.cs.algs4.Shell#sort

4.3：补充：Knuth 增量 3x+1 的证明

实际上，Knuth 增量序列的增量为 1/2(3^k-1)，不过在代码中使用了 while 循环来找出最大增量（大于 N/3，N为总长度），然后再通过 h /= 3 来缩短增量。

来做一下计算，证明：
$$\frac{3^k-1}{2}\ast 3+1=\frac{3^{k+1}-1}{2}$$

从左边开始展开计算：
$$\frac{3^k-1}{2}\ast 3+1$$
拆解合并常数项得：
$$\frac{3}{2}\ast 3^k-\frac{3}{2}+1=\frac{3}{2}\ast 3^k-\frac{1}{2}$$
利用指数的乘法规则：
$$3\ast 3^k=3^{k+1}$$
最终化简得：
$$\frac{3^{k+1}-1}{2}$$

（完）