普林斯顿算法讲义（一）（3）https://developer.aliyun.com/article/1484169
并查集 API。
以下 API 封装了我们需要的基本操作。 
为了测试 API 的实用性，UF.java 中的main()解决了动态连通性问题。我们还准备了测试数据：文件 tinyUF.txt 包含我们小例子中使用的 11 个连接，文件 mediumUF.txt 包含 900 个连接，文件 largeUF.txt 是一个包含数百万连接的示例。
实现。
我们现在考虑几种不同的实现方式，都基于使用一个站点索引数组id[]来确定两个站点是否在同一个组件中。
- 快速查找. QuickFindUF.java 维护了这样一个不变量：当且仅当
id[p]等于id[q]时，p和q连接。换句话说，组件中的所有站点在id[]中必须具有相同的值。 -
- 快速联合. QuickUnionUF.java 基于相同的数据结构——站点索引
id[]数组，但它使用了不同的值解释，导致更复杂的结构。具体来说，每个站点的id[]条目将是同一组件中另一个站点的名称（可能是它自己）。为了实现find()，我们从给定站点开始，沿着它的链接到另一个站点，再沿着那个站点的链接到另一个站点，依此类推，一直沿着链接直到到达一个根节点，一个有链接指向自身的站点。只有当这个过程将它们导向相同的根节点时，两个站点才在同一个组件中。为了验证这个过程，我们需要union()来维护这个不变量，这很容易安排：我们沿着链接找到与每个给定站点相关联的根节点，然后通过将其中一个根节点链接到另一个根节点来重命名一个组件。 -
- 加权快速联合. 在快速联合算法中，为了
union()将第二棵树任意连接到第一棵树，我们跟踪每棵树的大小，并始终将较小的树连接到较大的树。程序 WeightedQuickUnionUF.java 实现了这种方法。 -
- 带路径压缩的加权快速联合. 有许多简单的方法可以进一步改进加权快速联合算法。理想情况下，我们希望每个节点直接链接到其树的根节点，但我们不想付出改变大量链接的代价。我们可以通过使我们直接检查的所有节点直接链接到根节点来接近理想状态。
并查集成本模型。
在研究并查集算法时，我们计算数组访问次数（访问数组条目的次数，用于读取或写入）。
定义。
树的大小是其节点数。树中节点的深度是从节点到根的路径上的链接数。树的高度是其节点中的最大深度。
命题。
快速查找算法对每次find()调用使用一个数组访问，并且对于每次将两个组件合并的union()调用，数组访问次数在n + 3 和 2n + 1 之间。
命题。
在快速联合中，find()所使用的数组访问次数为 1 加上节点深度的两倍，该节点对应给定站点。union()和connected()所使用的数组访问次数为两个find()操作的成本（如果给定站点在不同树中，则union()还需加 1）。
命题。
由加权快速联合构建的森林中任何节点的深度最多为 lg n。
推论。
对于具有n个站点的加权快速联合，find()、connected()和union()的最坏情况成本增长顺序为 log n。 
问与答
Q. 是否有一种有效的数据结构，支持边的插入和删除？
A. 是的。然而，用于图连接性的已知最佳完全动态数据结构比我们考虑的增量版本复杂得多。此外，它的效率也不如增量版本。参见 Mikkel Thorup 的Near-optimal fully-dynamic graph connectivity。
练习
- 开发类 QuickUnionUF.java 和 QuickFindUF.java，分别实现快速联合和快速查找。
- 给出一个反例，说明快速查找的
union()的这种直观实现是不正确的：
public void union(int p, int q) { if (connected(p, q)) return; for (int i = 0; i < id.length; i++) if (id[i] == id[p]) id[i] = id[q]; count--; }
- 答案. 在 for 循环中，
id[p]的值会改变为id[q]。因此，任何r>p且id[r]等于id[p]的对象都不会被更新为等于id[q]。 - 在加权快速联合实现中，假设我们将
id[root(p)]设置为q而不是id[root(q)]。得到的算法是否正确？
答案. 是的。然而，这会增加树的高度，因此性能保证将无效。
创意问题
- 带路径压缩的快速联合。 修改 QuickUnionUF.java 以包括路径压缩，通过在
find()中添加一个循环，将从 p 到根的路径上的每个站点连接起来。给出一系列输入对，使得该方法产生长度为 4 的路径。注意：该算法的摊销成本每次操作已知为对数级别。
解决方案. QuickUnionPathCompressionUF.java。 - 带路径压缩的加权快速联合。 修改 WeightedQuickUnionUF.java 以实现路径压缩，如练习 1.5.12 所述。给出一系列输入对，使得该方法产生高度为 4 的树。
注意：该算法的摊销成本每次操作已知受到称为反阿克曼函数的函数的限制，对于实践中出现的任何可想象的n值，该函数均小于 5。
解决方案. WeightedQuickUnionPathCompressionUF.java。 - 按高度加权快速联合。 开发一个实现 WeightedQuickUnionByHeightUF.java 的算法，该算法使用与加权快速联合相同的基本策略，但跟踪树高度并始终将较短的树链接到较高的树。证明对于n个站点，您的算法对树的高度有对数上界。
解决方案. 不同树中元素之间的联合操作要么保持高度不变（如果两棵树的高度不同），要么增加一次高度（如果两棵树的高度相同）。你可以通过归纳证明树的大小至少为 2^高度。因此，高度最多可以增加 lg n次。 - 随机连接。开发一个
UF客户端 ErdosRenyi.java，接受一个整数命令行参数n���在 0 到n之间生成随机整数对，调用connected()确定它们是否连接，如果没有连接则调用union()（与我们的开发客户端相同），循环直到所有站点连接，并打印生成的连接数。将程序打包为一个以n为参数的静态方法count()，返回连接数和一个从命令行获取n的main()，调用count()，并打印返回的值。
网页练习
- 真或假。在快速联合实现中，假设我们将
parent[p]设置为parent[root(q)]而不是将parent[root(p)]设置为parent[root(q)]，得到的算法是否正确？
答案。不。 - 在执行带路径压缩的加权快速联合时，以下哪个数组不可能出现：
- 0 1 2 3 4 5 6 7 8 9
- 7 3 8 3 4 5 6 8 8 1
- 6 3 8 0 4 5 6 9 8 1
- 0 0 0 0 0 0 0 0 0 0
- 9 6 2 6 1 4 5 8 8 9
- 9 8 7 6 5 4 3 2 1 0
- 解决方案。B、C、E 和 F。
- 递归路径压缩。使用递归实现路径压缩。
解决方案：
public int find(int p) { if (p != parent[p]) parent[p] = find(parent[p]); return parent[p];
- 路径减半。编写一个数据类型 QuickUnionPathHalvingUF.java，实现一种更简单的策略，称为路径减半，使得查找路径上的每个其他节点都链接到其祖父节点。备注：该算法每次操作的摊销成本被限制在一个称为反阿克曼函数的函数中。
- 路径分裂。编写一个数据类型 WeightedQuickUnionPathSplittingUF.java，实现一种称为路径分裂的替代策略，使得查找路径上的每个节点都链接到其祖父节点。备注：该算法每次操作的摊销成本被限制在一个称为反阿克曼函数的函数中。
- 随机快速联合。实现以下版本的快速联合：将整数 0 到 n-1 均匀随机分配给 n 个元素。在链接两个根时，始终将具有较小标签的根链接到具有较大标签的根。添加路径压缩。备注：没有路径压缩版本的每次操作的期望成本是对数级的；具有路径压缩版本的每次操作的期望摊销成本被限制在一个称为反阿克曼函数的函数中。
- 3D 位置渗透。对 3D 晶格重复。阈值约为 0.3117。
- 键合渗透。与位置渗透相同，但是随机选择边而不是位置。真实阈值恰好为 0.5。
- 给定一组 N 个元素，创建一个 N 个联合操作的序列，使得带权重的快速联合的高度为 Theta(log N)。对带路径压缩的带权重快速联合重复。
- 六角形。六角形游戏在一个梯形六边形网格上进行…描述如何检测白色或黑色何时赢得游戏。使用并查集数据结构。
- 六角形。证明游戏不可能以平局结束。提示：考虑从棋盘左侧可达的单元格集合。
- 六角形。证明第一个玩家可以通过完美的游戏获胜。提示：如果第二个玩家有一个获胜策略，你可以最初选择一个随机单元格，然后只需复制第二个玩家的获胜策略。这被称为策略窃取。
- 在网格上标记聚类。 物理学家将其称为Hoshen–Kopelman 算法，尽管它只是在栅格图上进行的并查集算法，按照栅格扫描顺序进行。 应用包括模拟渗透和电导。 绘制站点占用概率与聚类数量的关系（比如 100x100，p 在 0 到 1 之间，聚类数量在 0 到 1500 之间）或聚类分布。（似乎 DFS 在这里就足够了）Matlab 在图像处理工具箱中有一个名为
bwlabel的函数，用于执行聚类标记。
2. 排序
原文：
algs4.cs.princeton.edu/20sorting译者：飞龙
概述。
排序是重新排列一系列对象的过程，使它们按照某种逻辑顺序排列。排序在商业数据处理和现代科学计算中起着重要作用。在交易处理、组合优化、天体物理学、分子动力学、语言学、基因组学、天气预测等领域都有广泛的应用。
在本章中，我们考虑了几种经典的排序方法以及一个称为优先队列的基本数据类型的高效实现。我们讨论了比较排序算法的理论基础，并以对排序和优先队列算法的应用进行调查来结束本章。
- 2.1 Elementary Sorts介绍了选择排序、插入排序和希尔排序。
- 2.2 Mergesort描述了归并排序，这是一种能够保证在线性对数时间内运行的排序算法。
- 2.3 Quicksort描述了快速排序，它比其他任何排序算法都被广泛使用。
- 2.4 Priority Queues介绍了优先队列数据类型以及使用二叉堆的高效实现。它还介绍了堆排序。
- 2.5 Applications描述了排序的应用，包括使用替代排序、选择、系统排序和稳定性。
本章的 Java 程序。
以下是本章中的 Java 程序列表。点击程序名称以访问 Java 代码；点击参考号以获取简要描述；阅读教材以获取全面讨论。
| REF | PROGRAM | DESCRIPTION / JAVADOC |
| 2.1 | Insertion.java | 插入排序 |
| - | InsertionX.java | 插入排序（优化版） |
| - | BinaryInsertion.java | 二分插入排序 |
| 2.2 | Selection.java | 选择排序 |
| 2.3 | Shell.java | 希尔排序 |
| 2.4 | Merge.java | 自顶向下的归并排序 |
| - | MergeBU.java | 自底向上的归并排序 |
| - | MergeX.java | 优化的归并排序 |
| - | Inversions.java | 逆序对数量 |
| 2.5 | Quick.java | 快速排序 |
| - | Quick3way.java | 三向切分的快速排序 |
| - | QuickX.java | 优化的双向快速排序 |
| - | QuickBentleyMcIlroy.java | 优化的三向快速排序 |
| - | TopM.java | 优先队列客户端 |
| 2.6 | MaxPQ.java | 最大堆优先队列 |
| - | MinPQ.java | 最小堆优先队列 |
| - | IndexMinPQ.java | 索引最小堆优先队列 |
| - | IndexMaxPQ.java | 索引最大堆优先队列 |
| - | Multiway.java | 多路归并 |
| 2.7 | Heap.java | 堆排序 |
排序演示。
以下是一些有趣的排序演示。
- 排序算法动画，作者 David Martin。
- 排序算法的声音和可视化，作者 Timo Bingmann。
- 快速排序的声音。
- 机器人可视化展示快速排序和归并排序。
- Carlo Zapponi 的排序可视化，使用逆序计数作为进度的衡量标准。
2.1 基本排序
原文：
algs4.cs.princeton.edu/21elementary译者：飞龙
在本节中，我们将学习两种基本的排序方法（选择排序和插入排序）以及其中一种的变体（希尔排序）。
游戏规则。
我们的主要关注点是重新排列包含关键字的项目数组的算法，目标是重新排列项目，使它们的关键字按升序排列。在 Java 中，关键字的抽象概念在内置机制中���现为Comparable接口。除了少数例外，我们的排序代码只通过两个操作引用数据：比较对象的方法less()和交换它们的方法exch()。
private static boolean less(Comparable v, Comparable w) { return (v.compareTo(w) < 0); } private static void exch(Comparable[] a, int i, int j) { Comparable swap = a[i]; a[i] = a[j]; a[j] = swap; }
- 排序成本模型。在研究排序算法时，我们计算比较和交换。对于不使用交换的算法，我们计算数组访问。
- 额外内存。我们考虑的排序算法分为两种基本类型：一种是原地排序（除了可能需要一小段函数调用堆栈或常数数量的实例变量外，不需要额外内存），另一种是需要足够额外内存来保存另一个要排序的数组的副本。
- 数据类型。我们的排序代码适用于实现 Java 的Comparable 接口的任何数据类型。这意味着存在一个
compareTo()方法，其中v.compareTo(w)在 v < w 时返回负整数，在 v = w 时返回零，在 v > w 时返回正整数。该方法必须实现全序：
- *自反性：*对于所有的 v，v = v。
- *反对称性：*对于所有的 v 和 w，如果(v < w)，那么(w > v)；如果(v = w)，那么(w = v)。
- *传递性：*对于所有的 v、w 和 x，如果(v ≤ w)且(w ≤ x)，那么 v ≤ x。
- 此外，如果
v和w是不兼容类型或其中任何一个为null，v.compareTo(w)必须抛出异常。
Date.java 演示了如何为用户定义的类型实现Comparable接口。
选择排序。
最简单的排序算法之一的工作方式如下：首先，在数组中找到最小的项，并将其与第一个条目交换。然后，找到下一个最小的项并将其与第二个条目交换。继续这样做，直到整个数组排序完成。这种方法被称为选择排序，因为它通过重复选择剩余的最小项来工作。Selection.java 是这种方法的实现。 
命题。
选择排序使用~n²/2 次比较和 n 次交换来对长度为 n 的数组进行排序。
插入排序。
人们经常用来排序桥牌的算法是逐个考虑卡片，将每张卡片插入到已考虑的卡片中的适当位置（保持它们排序）。在计算机实现中，我们需要为当前项目腾出空间，通过将较大的项目向右移动一个位置，然后将当前项目插入到空出的位置。Insertion.java 是这种方法的实现，称为插入排序。 
命题。
对于具有不同键的长度为 N 的随机排序数组，插入排序平均使用~N²/4 次比较和~N²/4 次交换。最坏情况下，使用~N²/2 次比较和~N²/2 次交换，最佳情况下是 N-1 次比较和 0 次交换。
插入排序对于某些在实践中经常出现的非随机数组非常有效，即使它们很大。逆序对是数组中顺序不正确的一对关键字。例如，E X A M P L E 有 11 个逆序对：E-A、X-A、X-M、X-P、X-L、X-E、M-L、M-E、P-L、P-E 和 L-E。如果数组中的逆序对数量小于数组大小的常数倍，则称该数组是部分排序的。
命题。
插入排序使用的交换次数等于数组中的逆序数，比较次数至少等于逆序数，最多等于逆序数加上数组大小。
属性。
对于具有不同值的随机排序数组，插入排序和选择排序的运行时间是二次的，并且彼此之间相差一个小的常数因子。
SortCompare.java 使用命令行参数中命名的类中的sort()方法执行给定数量的实验（对给定大小的数组进行排序），并打印算法观察运行时间的比率。
可视化排序算法。
我们使用简单的可视化表示来描述排序算法的属性。我们使用垂直条形图，按其高度排序。SelectionBars.java 和 InsertionBars.java 生成这些可视化效果。 
希尔排序。
希尔排序是插入排序的简单扩展，通过允许远离的条目进行交换，以产生部分排序的数组，最终可以通过插入排序高效地排序。其思想是重新排列数组，使其具有这样的属性：取每个第 h 个条目（从任何位置开始）会产生一个排序序列。这样的数组称为h-排序。 
通过对一些大的 h 值进行 h-排序，我们可以将数组中的条目移动到较远的距离，从而使得对较小的 h 值进行 h-排序更容易。对于以 1 结尾的任何增量序列的值使用这种过程将产生一个排序的数组：这就是希尔排序。Shell.java 是这种方法的实现。 
ShellBars.java 生成希尔排序的可视化效果。
属性。
使用增量为 1、4、13、40、121、364 的希尔排序所使用的比较次数受到 N 的倍数限制，与使用的增量数量成正比。
命题。
使用增量为 1、4、13、40、121、364 的希尔排序所使用的比较次数为 O(N^(3/2))。
问与答
Q. 当我编译 Insertion.java 时，编译器会发出警告。有没有办法避免这种情况？
Insertion.java:73: warning: [unchecked] unchecked call to compareTo(T) as a member of the raw type java.lang.Comparable return (v.compareTo(w) < 0);
A. 是的，如果使用静态泛型，就像 InsertionPedantic.java 一样。这会导致笨拙（但无警告）的代码。
练习
- 以选择排序示例跟踪的方式展示选择排序如何对数组进行排序。
E A S Y Q U E S T I O N
- 解决方案。
- 在选择排序中涉及任何特定项目的最大交换次数是多少？涉及特定项目 x 的平均交换次数是多少？
解决方案。 平均交换次数恰好为 2，因为总共有 n 次交换和 n 个项目（每次交换涉及两个项目）。最大交换次数为 n，如下例所示。
- 以插入排序示例跟踪的方式展示插入排序如何对数组进行排序。
E A S Y Q U E S T I O N
- 解决方案。
- 对于所有键相同的数组，选择排序和插入排序哪个运行速度更快？
解决方案。 当所有键相等时，插入排序运行时间为线性时间。 - 假设我们在一个随机排序的数组上使用插入排序，其中项目只有三个键值之一。运行时间是线性的、二次的还是介于两者之间的？
解决方案。 二次的。 - 以希尔排序示例跟踪的方式展示希尔排序如何对数组进行排序。
E A S Y S H E L L S O R T Q U E S T I O N
- 解决方案。
- 为什么在希尔排序的h排序中不使用选择排序？
解决方案。 插入排序在部分排序的输入上更快。
创意问题
- 昂贵的交换。 一家运输公司的职员负责按照要运出的时间顺序重新排列一些大箱子。因此，相对于交换的成本（移动箱子），比较的成本非常低（只需查看标签）。仓库几乎满了：有足够的额外空间来容纳任何一个箱子，但不能容纳两个。职员应该使用哪种排序方法？
解决方案。 使用选择排序，因为它最小化了交换的次数。 - 可视化跟踪。 修改你对上一个练习的解决方案，使 Insertion.java 和 Selection.java 产生类似本节中所示的可视化跟踪。
解决方案。 TraceInsertion.java、TraceSelection.java 和 TraceShell.java。 - 可比较的交易。 扩展你的 Transaction.java 实现，使其实现
Comparable，使得交易按金额顺序排列。 - 交易排序测试客户端。 编写一个类 SortTransactions.java，其中包含一个静态方法
main()，从标准输入读取一系列交易，对其进行排序，并在标准输出上打印结果。
实验
- 带哨兵的插入排序。 开发一个插入排序的实现 InsertionX.java，通过首先将最小的项目放入位置来消除内部循环中的 j > 0 测试。使用 SortCompare.java 来评估这样做的有效性。注意：通常可以通过这种方式避免索引越界测试——使测试能够被消除的项目称为哨兵。
- 无交换的插入排序。 开发一个插入排序的实现 InsertionX.java，将较大的项目向右移动一个位置，而不是进行完整的交换。使用 SortCompare.java 来评估这样做的有效性。
网络练习
- 排序网络。 编写一个程序 Sort3.java，其中有三个
if语句（没有循环），从命令行读取三个整数a、b和c，并按升序打印它们。
if (a > b) swap a and b if (a > c) swap a and c if (b > c) swap b and c
- 无视排序网络。 说服自己，以下代码片段重新排列存储在变量 A、B、C 和 D 中的整数，使得 A <= B <= C <= D。
if (A > B) { t = A; A = B; B = t; } if (B > C) { t = B; B = C; C = t; } if (A > B) { t = A; A = B; B = t; } if (C > D) { t = C; C = D; D = t; } if (B > C) { t = B; B = C; C = t; } if (A > B) { t = A; A = B; B = t; } if (D > E) { t = D; D = E; E = t; } if (C > D) { t = C; C = D; D = t; } if (B > C) { t = B; B = C; C = t; } if (A > B) { t = A; A = B; B = t; }
- 设计一系列语句，可以对 5 个整数���行排序。你的程序使用了多少个
if语句？ - 最佳的无视排序网络。 创建一个程序，使用仅 5 个
if语句对四个整数进行排序，以及使用仅 9 个上述类型的if语句对五个整数进行排序？无视排序网络对于在硬件中实现排序算法很有用。如何检查你的程序对所有输入都有效？
答案： Sort4.java 使用 5 个比较交换对 4 个项目进行排序。Sort5.java 使用 9 个比较交换对 5 个项目进行排序。
0-1 原则说，你可以通过检查一个（确定性的）排序网络是否正确地对由 0 和 1 组成的输入进行排序来验证其正确性。因此，要检查Sort5.java是否有效，你只需要在 32 个可能的由 0 和 1 组成的输入上测试它。 - 最佳的无视排序（具有挑战性）。 找到一个针对 6、7 和 8 个输入的最佳排序网络，分别使用 12、16 和 19 个上一个问题中形式的
if语句。
答案：Sort6.java 是对 6 个项目进行排序的解决方案。 - 最佳非盲目排序。 编写一个程序，仅使用 7 次比较对 5 个输入进行排序。提示：首先比较前两个数字，然后比较后两个数字，以及两组中较大的数字，并标记它们，使得 a < b < d 和 c < d。其次，将剩余的项目 e 插入到链 a < b < d 中的适当位置，首先与 b 进行比较，然后根据结果与 a 或 d 进行比较。第三，以与插入 e 相同的方式将 c 插入到涉及 a、b、d 和 e 的链中的适当位置（知道 c < d）。这使用了 3（第一步）+ 2（第二步）+ 2（第三步）= 7 次比较。这种方法最初是由 H.B. Demuth 在 1956 年发现的。
- Stupidsort。 分析以下排序算法的运行时间（最坏情况和最佳情况）、正确性和稳定性。从左到右扫描数组，直到找到两个连续的位置不正确的项。交换它们，并从头开始。重复直到扫描到数组的末尾。
for (int i = 1; i < N; i++) { if (less(a[i], a[i-1])) { exch(i, i-1); i = 0; } }
- 考虑以下递归变体并分析最坏情况下的内存使用情况。
public static void sort(Comparable[] a) { for (int i = 1; i < a.length; i++) { if (less(a[i], a[i-1])) { exch(i, i-1); sort(a); } } }
- Stoogesort。 分析以下递归排序算法的运行时间和正确性：如果最左边的项大于最右边的项，则交换它们。如果当前子数组中有 2 个或更多项，(i) 递归地对数组的前两个三分之一进行排序，(ii) 对数组的最后两个三分之一进行排序，(iii) 再次对数组的前两个三分之一进行排序。
- 猜测排序。 随机选择两个索引 i 和 j；如果 a[i] > a[j]，则交换它们。重复直到输入排序。分析此算法的预期运行时间。提示：每次交换后，逆序的数量会严格减少。如果有 m 个坏对，那么找到一个坏对的预期时间为 Theta(n²/m)。从 m = 1 到 n² 求和得到 O(N² log N)的总体时间，类似于收集优惠券。这个界限是紧的：考虑输入 1 0 3 2 5 4 7 6 …
- Bogosort。 Bogosort 是一种随机算法，通过将 N 张卡片抛起来，收集它们，并检查它们是否以递增顺序排列。如果没有，重复直到它们排好序。使用第 1.4 节中的洗牌算法实现 bogosort。估计运行时间作为 N 的函数。
- 慢速排序。 考虑以下排序算法：随机选择两个整数 i 和 j。如果 i < j，但 a[i] > a[j]，则交换它们。重复直到数组按升序排列。论证该算法最终会完成（概率为 1）。作为 N 的函数，它需要多长时间？提示：在最坏情况下，它会进行多少次交换？
- 对数组进行排序的最小移动次数。 给定一个包含 N 个键的列表，移动操作包括从列表中移除任意一个键并将其附加到列表的末尾。不允许其他操作。设计一个算法，使用最少的移动次数对给定列表进行排序。
- 猜测排序。 考虑以下基于交换的排序算法：随机选择两个索引；如果 a[i]和 a[j]是一个逆序，交换它们；重复。证明对大小为 N 的数组进行排序的预期时间最多为 N² log N。参见此论文进行分析，以及称为 Fun-Sort 的相关排序算法。
- 交换一个逆序。 给定一个包含 N 个键的数组，设 a[i]和 a[j]是一个逆序（i < j 但 a[i] > a[j]）。证明或证伪：交换 a[i]和 a[j]会严格减少逆序的数量。
- 二进制插入排序。 开发一个实现 BinaryInsertion.java 的插入排序，该排序使用二分查找来找到插入点 j 以便将条目 a[i]插入，然后将所有条目 a[j]到 a[i-1]向右移动一个位置。在最坏情况下，对长度为 n 的数组进行排序的比较次数应该约为~ n lg n。请注意，在最坏情况下，数组访问次数仍然是二次的。使用 SortCompare.java 来评估这样做的有效性。
