算法4-2.1初级排序20200719
2.1初级排序算法
2.1.1游戏规则
我们关注的主要对象是重新排列数纽元素的算法，其中每个元素都有一个主键。 排序算法的目标就是将所有元素的主键按照某种方式排列（通常是按照大小或是字每顺序）。排序后索引较大的主键大于等于索引较小的主键 。 元素和主键的具体性质在不同的应用中千差万别 。 在 Java 中， 元素通常都是对象，对主键的抽象描述则是通过一种内置的机制。
“排序算法类模版”中的 Example 类展示了我们的习惯约定 ： 我们会将排序代码放在类的sort （） 方法中，该类还将包含辅助函数 less （） 和 exch() （可能还有其他辅助函数）以及一个示例用例 main（） 。Example 类还包含了一些早期调试使用的代码：测试用例 main （） 将标准输入得到的字符串排序，并用私有方法 show （） 打印字符数组的内容 。
一般情况下，我们的排序代码只会通过两个方法操作数据 ：less （） 方法对元素进行比较，exch （） 方法将元素交换位置 。exch （）方法的实现很简单，通过 Comparable 接口实现 less （） 方法也不困难 。 将数据操作限制在这两个方法中使得代码的可读性和可移植性更好，更容易验证代码的正确性、分析性能以及排序算法之间的比较 。
2.1.1.1 运行时间
我们还要评估算法的性能 。 首先，要计算各个排序算法在不同的随机输入下的基本操作的次数（包括 比较和交换，或者是读写数组的次数）。
**排序成本模型：**在研究排序算法时，我们需要计算比较和交换的数量。对于不交换元素的算法，我们会计算访问数组的次数。
2.1.1.2 额外的内存使用
排序算法的额外内存开销和运行时间是同等重要的 。 排序算法可以分为两类：除了函数调用所需的栈和固定数目的实例变量之外无需额外内存的原地排序算法，以及需要额外内存空间来存储另一份数组副本的其他排序算法 。
2.1.2 选择排序
一种最简单的排序算法是这样的：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。 再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置 。 如此往复，直到将整个数组排序 。 这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者 。
选择排序的内循环只是在比较当前元素与目前已知的最小元素（以及将当前索引加1和检查是否代码越界），这已经简单到了极点 。 交换元素的代码写在内循环之外，每次交换都能排定一个元素，因此交换的总次数是 N。 所以算法的时间效率取决于比较的次数。
选择排序是一种很容易理解和实现的简单排序算法， 它有两个很鲜明的特点 。
★ 运行时间和输入无关： 为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息 。这种性质在某些情况下是缺点，因为使用选择排序的人可能会惊讶地发现， 一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长 ！ 我们将会看到，其他算法会更善于利用输入的初始状态 。
★ 数据移动最少： 每次交换都会改变两个数组元素的值，因此选择排序用了 N 次交换——交
换次数和数组的大小是线性关系 。其他任何算法都不具备这个特征（大部分的增长数量级都是线性对数或是平方级别）。
2.1.3 插入排序
通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置 。在计算机的实现中 ，为了给更小的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。这种算法叫做：插入排序。
与选择排序一样，当前索引的左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动 。 但是当索引到达数组的右端时，数组排序就完成了 。
和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序 。 例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会 比对随机顺序的数组或是逆序数组进行排序要快得多 。
插入排序对于实际应用钟常见的某些类型的非随机数组很有效 。 例如，正如l刚才所提到的，想想当你用插入排序对一个有序数组进行排序时会发生什么 。 插入排序能够立即发现每个元素都已经在合适的位置之上 ， 它的运行时间也是线性的（对于这种数组，选择排序的运行时间是平方级别的 ）。
对于所有主键都相同的数组也会出现相同的情况（因此命题 B 的条件之一就是主键不重复）。
我们要考虑的更一般的情况是部分有序的数组。倒置指的是数组中的两个顺序颠倒的元素 。 比如 EXA MPLE中有11对倒置 ：E-A 、X -A 、X-M 、X-P、X -L 、X -E 、M-L 、M-E、P-L 、P-E以及 L -E 。 如果数组中倒置的数量小于数组大小的某个倍数，那么我们说这个数组是部分有序的 。
下面是几种典型的部分有序的数组：
★ 数组中每个元素距离它的最终位置都不远；
★ 一个有序的大数组接一个小数组 ；
★ 数组中只有几个元素的位置不正确 。
插入排序对这样的数组很有效，而选择排序则不然 。 事实上，当倒置的数量很少时，插入排序很可能比其他一些算法都要快 。
总的来说，插入排序对于部分有序的数组十分高效 ，也很适合小规模数组 。 这很重要，因为这些类型的数组在实际应用中经常出现，而且它们也是高级排序算法的中间过程。
2.1.4 排序算法的可视化
2.1.5 希尔排序
希尔排序是一种基于插入排序的快速的排序算法 。对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端 。 例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要 N- 1次移动 。 希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序 。
希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的 。 这样的数组被称为 h 有序数组 。 换句话说，一个 h 有序数组就是 h 个互相独立的有序数组编织在一起组成的一个数组。在进行排序时，如果 h 很大，就能将元素移动到很远的地方，为实现更小的h 有序创造方便 。 用这种方式，对于任意以1结尾的 h 序列，我们都能够将数组排序 。 这就是希尔排序 。 使用了序列1/2 ( 3k -1 ），从N/3 开始递减至1，这个序列称为递增序列 。
实现希尔排序的一种方法是对于每个 h ，用插入排序将 h 个子数组独立地排序 。 但因为子数组是相互独立的，一个更简单的方法是在h-子数组中将每个元素交换到比它大的元素之前去（将比它大的元素向右移动一格） 。 只需要在插入排序的代码中将移动元素的距离由1改为 h 即可 。 这样，希尔排序的实现就转化为了一个类似于插入排序但使用不同增量的过程 。
希尔排序更高效的原因是它权衡了子数组的规模和有序性 。 排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序 。 子数组部分有序的程度取决于递增序列的选择 。
如何选择递增序列呢？算法的性能不仅取决于 h ，还取决于 h 之间的数学性质，比如它们的公因子等。 有很多论文研究了各种不同的递增序列，但都无法证明某个序列是“最好的”。递增序列的计算和使用都很简单，和复杂递增序列的性能接近 。 但可
以证明复杂的序列在最坏情况下的性能要好于我们所使用的递增序列 。 和选择排序以及插入排序形成对比的是，希尔排序也可以用于大型数组 。 它对任意排序（不一定是随机的）的数组表现也很好。 实际上，对于一个给定的递增序列，构造一个使希尔排序运行缓慢的数组并不容易。
希尔排序比插入排序和1选择排序要快得多，并且数组越大，优势越大 。