大话数据结构 -- 整理归纳（2）

第 8 章：查找

• 查找表（Search Table）：由同一类型的数据元素（或记录）构成的集合。

• 关键字（Key）：是数据元素中的某个数据项的值，又称为 键值，用它可以标识一个数据元素。也可以标识一个记录的某个数据项（字段），我们称为 关键码。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary Key）。而对于那些可以识别多个数据元素（或记录）的关键字，我们称为 次关键字（Secondary Key）。

• 查找（Searching）：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值得数据元素（或记录）。

• 查找表按照操作方式来分有两大种：静态查找表 和 动态查找表：
  ☛ 静态查找表（Static Search Table）：只作查找操作的查找表。它的主要操作有：（1）查询某个 ”特定的“ 数据元素是否在查找表中。（2）检索某个 ”特定的“ 数据元素和各种属性。
  ☛ 动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。显然动态查找表的操作就是两个：（1）查找时插入数据元素。（2）查找时删除数据元素。

• 从逻辑上来说，查找所基于的数据结构是集合，集合中的记录之间没有本质关系。可是要想获得较高的查找性能，我们就不能不改变数据元素之间的关系，在存储时可以将查找集合组织成表，树等结构。比如，对于静态查找表来说，我们不妨应用线性表结构来组织数据，这样可以使用顺序查找算法，如果再对主关键字排序，则可以应用折半查找等技术进行高效的查找。

• 顺序查找（Sequential Search）：也叫 线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字等于给定值，则查找成功；如果直到最后一个（或第一个）记录，仍然找不到关键字与给定值相等的记录，则查找失败。顺序查找的时间复杂度为 。

• 折半查找（Binary Search）：又叫 二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到达有序），线性表必须采用顺序存储。二分查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。二分查找的时间复杂度为 。

• 由于 二分查找 的前提条件是要求集合有序，因此，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了。但对于需要频繁执行插入或删除操作的数据集（动态查找表）来说，维护有序的排序会带来不小的工作量，那就不建议使用。

• 插值查找（Interpolation Search）：根据要查找的关键字 key 与查找表中的最大最小记录的关键字比较后的查找方法，其核心在于插值计算公式：。

• 插值查找 与 二分查找 的时间复杂度都是 ，但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比二分查找要好的多（因为，二分查找是折半查找，而插值查找会根据要查找的 key 计算得出其在整个查找表中的权重，得到的位置会更接近 key 的位置）。反之，数组中如果分布类似 这种极端不均匀的数据，用插值查找未必是很合适的选择。

• 斐波那契查找（Fibonacci Search）：斐波那契查找与二分查找和插值查找都是有序查找算法，不过其是利用了黄金分割原理来实现的。其核心算法为：
  1）当 时，查找成功；
  2）当 时，新范围是第 low 个到第 mid-1 个，此时范围个数为 个；
  3）当 时，新范围是第 m+1 个到第 high 个，此时范围个数为 个。

斐波那契查找

• 二分查找，插值查找 和 斐波那契查找 都是有序查找算法，它们的本质其实是相同的，都是选择序列中间的某个位置与给定值进行比较，依据序列的有序性，每次查找都可以去除两端一部分序列，从而提升查找性能。三者的区别仅在与中间位置的选择策略不同：二分查找直接取序列中点作为 mid，插值查找按给定值在序列的权重（比例）作为 mid，而斐波那契查找是用序列的黄金分割点（即：）作为 mid。

• 尽管斐波那契查找的时间复杂度也为 ，但就平均性能来说，斐波那契查找要优于二分查找。还有一点比较关键的地方，二分查找是进行加减法与除法运算：mid=low+(high-low)/2，插值查找进行复杂的四则运算：mid=low+(high-low)*(key-a[low])/(a[high]-a[low])，而斐波那契查找只是最简单的加减法运算：mid=low+F[k-1]-1。在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。

• 索引：就是把一个关键字与它对应的记录相关联的过程（关键字=记录）。数据结构的最终目的就是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。

• 索引按照结构可以分为：线性索引，树形索引和多级索引。

• 线性索引：就是将索引项集合组织为线性结构，也称为 索引表。

• 我们重点介绍一下三种线性索引：

  ☛ 稠密索引：指在线性索引中，将数据集中的每个记录对应一个索引项。如下图所示：

稠密索引

稠密索引要应对的可能是成千上万的数据，因此，对于稠密索引这个索引表来说，索引项一定是按照关键码 有序 的排列。

 ☛ 分块索引：对数据集进行有序分块，并将每块对应一个索引项。其中，分块有序 指的是把数据集的记录分成若干块，并且这些块需要满足 块内无序 和 块间有序 这两个条件。分块索引如下图所示：

分块索引

在分块索引表中查找，就是分两步进行：
1）在分块索引表中查找要查关键字所在的块。由于分块索引表示块间有序的，因此很容易利用二分，插值等算法得到结果。
2）找到关键字所在的块后，根据块首指针找到对应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找。

  ☛ 倒排索引：指的是索引项具备 次关键码 和 记录号表 两个字段，且记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字），则称这样的索引方法为 倒排索引（inverted index）。之所以成为倒排索引，是因为其是有属性值来确定记录位置，而不是由记录来确定属性值（即通过内容关键字来查找文章，而不是由文章来查找其内容关键字）。

• 假设查找的数据集是普通的顺序存储，那么插入操作（插入到末尾）和删除操作（删除记录后记录向前移相对耗时，但如果只把删除的元素与最后一个元素互换，然后表记录数减一，则很高效）的效率是可以接受的。但是顺序存储表由于无序会造成查找效率很低。
  如果查找的数据集是有序线性表，并且是顺序存储的，那么其查找（二分法，插值法，斐波那契···）效率很高，但是由于有序，在插入和删除操作上，就需要耗费大量的时间。
  而使用 二叉排序树 这种存储结构时，就可以实现对动态查找表的高效插入，删除和查找操作。

• 二叉排序树（Binary Sort Tree）：又称为 二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：
  ☛ 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  ☛ 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  ☛ 它的左、右子树也分别为二叉排序树；

• 构造一棵 二叉排序树 的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。

• 二叉排序树 是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的有点（只需修改链接指针），插入和删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值得结点在二叉排序树的层数。极端情况下，查找次数最少为 1 次，即根结点就是要找的结点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。很可惜的是，二叉排序树的形状是不确定的（想象下极端的右斜树或左斜树）。对于这个问题，解决方案就是让二叉排序树左右子树是比较平衡的，即其深度与完全二叉树相同，均为 ，那么查找的时间复杂度就为 ，近似二分查找，这种结构就称为 平衡二叉树（AVL 树）。

• 平衡二叉树（Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree）：是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于 1。

• 平衡因子 BF（Balance Factor）：将二叉树上结点的左子树深度减去右子树深度的值称为 平衡因子 BF。

• 平衡二叉树 上所有结点的平衡因子只可能是 -1、0 和 1。只要二叉树上有一个结点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的。

• 最小不平衡子树：距离插入结点最近的，且平衡因子的绝对值大于 1 的结点为根的子树，我们称为 最小不平衡子树。

最小不平衡子树

如上图所示，当新插入结点 37 时，距离它最近的平衡因子绝对值超过 1 的结点是 58（58 的左子树高度为 2，右子树高度为 0），所以从 58 开始以下的子树为最小不平衡子树。

• 平衡二叉树实现原理：平衡二叉树构建的基本思想就是在构建二叉树排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

• 对于 树 来说，一个几点只能存储一个元素，那么在元素非常多的时候，就会使得要么树的度非常大（结点拥有子树的个数的最大值），要么树的高度非常大，甚至两者都必须足够大才行。这就使得内存存取外存次数非常多，这显然成了时间效率上的瓶颈，这迫使我们要打破每一个结点只存储一个元素的限制，为此引入了多路查找树的概念。

• 多路查找树（muitl-way search tree）：其每一个结点的孩子树可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，因此所有元素之间存在某种特定的排序关系（即其是有序的）。

• 下面介绍 4 中常见的多路查找树：

  ☛ 2-3 树：每个结点都具有两个孩子（我们称它为 2 结点）或三个孩子（我们称它为 3 结点）的树。一个 2 结点 包含一个元素和两个孩子（或没有孩子），且左子树数据元素小于该元素，右子树数据元素大于该元素；一个 3 结点 包含一小一大两个元素和三个孩子（或没有孩子），如果有 3 个孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。下图即为一个 2-3 树 图：

2-3 树

  ☛ 2-3-4 树：其为 2-3 树 的扩展，在其基础上增加一个 4 结点 的使用。一个 4 结点 包含小中大三个元素和四个孩子（或没有孩子）。如果某个 4 结点有孩子的话，左子树包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素。

  ☛ B 树（B-tree）：其是一种平衡的多路查找树，2-3 树 和 2-3-4 树 都是 B 树 的特例。结点最大的孩子数目称为 B 树 的阶（order）。因此，2-3 树 为 3 阶 B 树，2-3-4 树 为 4 阶 B 树。

  ☛ B+ 树：其是应文件系统所需而出的一种 B 树 的变形树。在 B 树 中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在 B+ 树 中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出。另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。

• 对于海量数据，数据一般都保存到外存（eg：硬盘）中，每次需要数据时，再读取到内存中。因此，如果内存与外存交换数据次数频繁，就会造成时间效率上的瓶颈，而使用 B 树 可以减少这种内外存交互：我们的外存，比如硬盘，是将所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，对于一个硬盘来说，一页的长度可能是 211 到 214 个字节。在一个典型的 B 树 应用中，要处理的硬盘数据量很大，因此无法一次全部装入内存。因此我们会对 B 树 进行调整，使得 B 树 的阶数（或结点的元素）与硬盘存储的页面大小相匹配。比如说一棵 B 树 的阶为 1001（即 1 个结点包含 1000 个关键字），高度为 2，它可以储存超过 10 亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。通过这种方式，在有限内存的情况下，每一次磁盘的访问我们都可以获得最大数量的数据。可以说，B 树的数据结构就是为内外存的数据交互准备的。

• 散列技术：是在记录的存储位置和它的关键字之间建立一个确定的对应关系 ，使得每个关键字 key 对应一个存储位置 。查找时，根据这个确定的对应关系找到给定值 key 的映射 ，若查找集合中存在这个记录，则必定在 的位置上。这里我们把这种对应关系 称为 散列函数，又称为 哈希（Hash）函数。

• 采用散列技术将记录存储在一块连续的存储空间中，则这块连续存储空间称为 散列表 或 哈希表（Hash table）。那么关键字对应的记录存储位置我们称为 散列地址。

• 散列技术 既是一种存储方法，也是一种查找方法。通过 散列函数 计算关键字散列地址，并按此散列地址存储对应记录；查找时，通过同样的 散列函数 计算关键字散列地址，按此地址访问对应记录。

• 散列函数 设计原则：
  ☛ 计算简单：散列函数的计算时间不应该超过其他查找技术与关键字比较的时间。
  ☛ 散列地址分布均匀：防止散列冲突最好的办法就是尽量让散列地址均匀地分布在存储空间中，这样可以保证存储空间的有效利用，并减少为处理冲突而耗费的时间。

• 下面是几种常用的散列函数的构造方法（这些方法原理都是将原来数字按某种规律变成另一个数字）：
  ☛ 直接定址法：取关键字的某个线性函数值作为散列地址：；
  直接定址法获取得到的散列函数有点就是简单，均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。
  ☛ 数字分析法：如果关键字是位数较多的数字（比如手机号），且这些数字部分存在相同规律，则可以采用抽取剩余不同规律部分作为散列地址（比如手机号前三位是接入号，中间四位是 HLR 识别号，只有后四位才是真正的用户号。也就是说，如果手机号作为关键字，那么极有可能前 7 位是相同的，此时我们选择后四位作为散列地址就是不错的选择）。同时，对于抽取出来的数字，还可以再进行反转，右环位移，左环位移等操作，目的就是为了提供一个能够尽量合理地将关键字分配到散列表的各个位置的散列函数。
  数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。
  ☛ 平方取中法：即取关键字平方的中间位数作为散列地址（比如假设关键字是 4321，那么它的平方就是 18671041，抽取中间的 3 位就可以是 671，也可以是 710，用做散列地址）。
  平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。
  ☛ 折叠法：折叠法是将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址（比如假设关键字是 9876543210，散列表表长为三位，则我们可以将它分为四组 987|654|321|0，然后将它们叠加求和 987+654+321+0=1962，再取后 3 位得到散列地址即为 962。有时可能这还不能够保证分布均匀，那么也可以尝试从一端到另一端来回折叠后对齐相加。比如讲 987 和 321 反转，再与 654 和 0 相加，变成 789+654+123+0=1566，此时散列地址为 566）。
  折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。
  ☛ 除留余数法：此方法为最常用的构造散列函数方法。对于散列表长为 的散列函数公式为：。很显然，本方法的关键就在于选择合适的 ，根据前辈们的经验，若散列表表长为 ，通常 为小于或等于表长（最好接近 ）的最小质数或不包含小于 20 质因子的合数。
  ☛ 随机数法：选择一个随机数，取关键字的随机函数值为它的散列地址：。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

• 散列冲突 处理方法：
  ☛ 开放定址法：所谓的 开放定址法 就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入：，使用该公式用于解决冲突的开放定址法称为 线性探测法。
  对于 线性探测法，在出现冲突时，它只能晚后一步一步检测看是否有空位置，假设此时该冲突位置后续没有可用位置，但前面有一个空位置，尽管可以不断地求余数后得到结果，但效率很差。因此可以改进该算法，增加双向寻找可能的空位置，这种新算法称为 二次探测法：。
  此外还有一种方法是，在冲突时，对于位移量 采用随机函数计算得到，我们称为 随机探测法：（注：这里的随机其实是伪随机数，即设置相同的随机种子，则不断调用随机函数的过程中就可以生成不会重复的数列；同时，在查找时，用同样的随机种子，它每次得到的数列也是相同的，因此相同的 就可以得到相同的散列地址）。
  ☛ 再散列函数法：即提供多个散列函数：，这里的 就是不同的散列函数，然后每当发生散列地址冲突时，就换一个散列函数计算，相信总会有一个可以把冲突解决掉。这种方法能够使得关键字不产生聚集，当然，相应地也增加了计算的时间。
  ☛ 链地址法：将所有关键字为同义词（即哈希地址相同）的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。
  链地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了查找时需要遍历单链表的性能损耗。
  ☛ 公共溢出区法：即为所有冲突的关键字建立一个公共的溢出区来存放。在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表去进行顺序查找。如果对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

• 散列表 性能分析：
  ☛ 散列函数是否均匀：散列函数的好坏直接影响着出现冲突的频繁程度。不过，由于不同的散列函数对同一组随机的关键字，产生冲突的可能性是相同的，因此可以不考虑它对平均查找长度的影响。
  ☛ 处理冲突的方法：相同的关键字，相同的散列函数，但处理冲突的方法不同，会使得平均查找长度不同。比如线性探测处理冲突可能会产生堆积，显然就没有二次探测法好，而链地址法处理冲突不会产生任何堆积，因而具有更佳的平均查找性能。
  ☛ 散列表的装填因子：所谓的装填因子 。 标志着散列表的装满的程度。当填入表中的记录越多， 就越大，产生冲突的可能性就越大（比如假设散列表长度是 12，而填入表中的记录个数为 11，那么此时的装填因子 ，因此再填入最后一个关键字产生冲突的可能性就非常之大），也就是说，散列表的平均查找长度取决于装填因子，而不是取决于查找集合中的记录个数。不管记录个数 有多大，我们总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围之内，此时我们散列查找的时间复杂度就真的是 了。 为了做到这一点，通常我们都是将散列表的空间设置得比查找集合大，此时虽然是浪费了一定的空间，但换来的是查找效率的大大提升，总的来说，还是非常值得的。

第 9 章：排序

• 排序 的依据是关键字之间的大小关系，即对同一个记录集合（数据集合），针对不同的关键字进行排序，可以得到不同的序列（注：此处的关键字可以是记录的主关键字，也可以是此关键字，甚至是若干数据项的组合）。

• 多个关键的排序最终都可以转化为单个关键字的排序。比如，现在要对学生的成绩进行排序，排序规则为按总分降序排序，若总分分数相同，按主科（语数英）总分数进行降序排序。直接的思路肯定是先进行总分排序，然后遇到总分相同的，就进行主科总分排序。但是还可以使用一个技巧来实现一次排序即可完成上述组合排序问题：例如，把总分与主科总分当成字符串首尾拼接到一起（注意如果主科成绩不够三位，则需在前面补零）（比如：甲，乙两人的总分都为 753，其中，甲的理科总分为 229，而乙的理科总分为 236，则甲的拼接为："753229"，乙的拼接为："753236"，比较这两个拼接字符串即可直接（一次性）直到乙排在甲前面（乙 > 甲）。

• 排序的稳定性：假设 ，且在排序前的序列中 领先于 （即 ）。如果排序后 仍领先于 ，则称所用的排序方法是 稳定 的；反之，若可能使得排序后的序列中 领先于 ，则称所用的排序方法是 不稳定 的。如下图所示：

排序稳定性

• 根据在排序过程中待排序的记录是否全部被放置在内存中，排序分为：内排序 和 外排序：
  ☛ 内排序：是在排序整个过程中，待排序的所有记录全部被放置在内存中。
  ☛ 外排序：是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交互数据才能进行。

• 对于 内排序 来说，排序算法的性能主要受 3 个方面影响：
  ☛ 时间性能：在内排序中，主要进行两种操作：比较 和 移动。比较 是指关键字之间的比较，这是做排序最基本的操作。移动 是指记录从一个位置移动到另一个位置，事实上，移动可以通过改变记录的存储方式来予以避免。总之，高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。
  ☛ 辅助空间：辅助内存空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。
  ☛ 算法的复杂性：此处指的是算法本身的复杂度，而不是指算法的时间复杂度。

• 内排序 分为：插入排序，交换排序，选择排序 和 归并排序。

• 冒泡排序（Bubble Sort）：是一种交换排序，它的基本思想是：两两比较相邻记录的关键字（或数据），如果反序则交换，直到没有反序的记录为止。

• 选择排序 的基本思想是：每一趟在 个记录中选择关键字最小的记录作为有序序列的第 个记录。

• 简单选择排序法（Simple Selection Sort）：就是把通过 次关键字间的比较，从 个记录中选出关键字最小的记录，并和第 个记录交换之（其实就是取第 1 个记录依次根后续记录进行比较，如果大于后续某个记录，则记录该索引（该索引的值为当前比较的最小值），然后用该索引对应的值继续进行下去，这样一轮过后，就能找到最小值的索引，然后将该值与第 1 个值交换即可。后续过程如上进行）。可以看到，使用该算法减少了记录间交换的次数。

• 直接插入排序（Straight Insertion Sort）：其基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增 1 的有序表。

• 冒泡排序，简单选择排序，直接插入排序 的时间复杂度同为 ，但性能上：直接插入排序 > 简单选择排序 > 冒泡排序。

• 基本有序：就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间。比如，向 就是基本有序，但像 这样的 9 在第三位，2 在倒数第三位就不是基本有序。

• 确保 基本有序 的方法：跳跃分割策略：即将相距某个 “增量” 的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

• 希尔排序：其思想就是将原本有大量记录数的记录进行分组。分割成若干个子序列，此时每个子序列待排序的记录个数就比较少了，然后再这些子序列内分别进行直接插入排序，当整个序列都 基本有序 时，再对全体记录进行一个直接插入排序。

• 希尔排序 的关键并不是随便分组后各自排序，而是将相隔某个 ”增量“ 的记录组成一个子徐磊，实现跳跃式的移动，使得排序的效率提高。因此这里 “增量” 的选取就非常关键了，但增量的选择度量至今还未找到一种最好的增量序列。不过大量的研究表明，当增量序列为： 时，可以获得不错的效率，其时间复杂度为 ，要好于直接排序的 。（注：**增量序列的最后一个增量值必须等于 1）。）另外由于记录是跳跃式的移动，因此希尔排序并不是一种稳定的排序算法。

• 堆 是具有下列性质的完全二叉树：

  ☛ 每个结点的值都大于或等于其左右孩子结点的值，称为 大顶堆。如下图所示：

大顶堆

  ☛ 每个结点的值都小于或等于其左右孩子结点的值，称为 小顶堆。如下图所示：

小顶堆

• 堆排序（Heap Sort）：就是利用 堆（假设使用 大顶堆）进行排序的方法。它的基本思想是：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾交换，此时末尾元素就是最大值），然后将剩余的 个序列重新构造成一个堆，这样就会得到 个元素中的次小值。如此反复执行，便能得到一个有序序列了。

• 堆排序 就是对 简答选择排序 的一种改进算法，并且这种改进的效果非常明显。

• 堆排序 的时间复杂度为 。其记录的比较与交换是跳跃式进行，因此 堆排序 也是一种不稳定的排序方法。另外，由于初始构建堆所需的比较次数较多，因此，它并不适合待排序序列个数较少的情况。

• 归并排序（Merging Sort）：就是利用归并的思想实现的排序方法。它的原理是：假设初始序列含有 个记录，则可以看成是 个有序的子序列，每个子序列的长度为 1，然后两两归并，得到 个长度为 2 或 1 的有序子序列；再两两归并，······，如此重复，直至得到一个长度为 的有序序列为止，这种排序方法称为 2 路归并排序。

• 归并排序 的时间复杂度为 ，空间复杂度为 。

• 归并排序 是一种比较占内存，但效率高且稳定的算法。

• 快速排序（Quick Sort）：其基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

• 希尔排序 相当于 直接插入排序 的升级，它们同属于插入排序类；堆排序 相当于简单选择排序的升级，它们同属于选择排序类；而 快速排序 其实就是我们前面认为最慢的 冒泡排序 的升级，它们都属于交换排序类，即它也是通过不断比较和移动交换来实现排序的，只不过它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的移动次数和移动交换次数。

• 快速排序 的 平均时间复杂度 为 ，平均空间复杂度 为 。可惜的是，由于关键字的比较和交换是跳跃式进行的，因此，快速排序是一种不稳定的排序方法。

• 从算法的简单性来看，可以将 7 种算法分为两类：
  ☛ 简单算法：冒泡，简单选择，直接插入；
  ☛ 改进算法：希尔，堆，归并，快速。
  它们的各种性能指标如下图所示：

从平均情况来看，显然后面 3 种改进算法要胜过希尔排序，并远远胜过前 3 种简单算法。

从最好情况看，反而冒泡和直接插入排序更好，也就是说，如果你的待排序序列总是 基本有序，反而不应该考虑 4 种复杂的改进算法。

从最坏情况看，堆排序和归并排序又强过快速排序以及其他简单排序。

从空间复杂度看，归并排序强调要马跑得快，就得给马吃饱。快速排序也有相应的空间要求，反而堆排序等却都是少量索取，大量付出，对空间要求是 。如果执行算法的软件非常在乎 内存使用量 时，选择归并排序和快速排序就不是一个较好的决策了。

总的来说，综合各项指标，经过优化的快速排序是性能最好的排序算法，但是不同的场合我们也应该考虑使用不同的算法来应对。