资源简介

(共91张PPT)
第6章 查找与排序
查找
排序
查找
排序
6.2
6.1
点击查看本小节知识架构
点击查看本小节知识架构
学习目标
掌握
掌握
掌握
掌握
掌握常用的查找算法
1
掌握排序算法的代码编写方法
4
2
掌握常用的排序算法
3
掌握查找算法的代码编写方法
本章将主要介绍算法中的常用操作——查找与排序。查找与排序作为数据处理的基本操作，是学习编程必须掌握的。查找是在给定的数据集合（表）中搜索指定的数据元素。排序是将数据集合中的各个数据元素按照指定的顺序进行排列。查找与排序的算法很多，根据数据集合的不同特点使用不同的查找与排序算法，可以节省空间与时间，提高程序效率。本章将重点围绕查找与排序算法的原理与代码实现进行介绍。
6.1 查找
6.1.1
顺序查找
返回目录
6.1.2
折半查找
6.1.3
分块查找
6.1.4
哈希查找
6.1 查找
设记录表 L=(R 1 ,R 2, …R n )，其中 R i (1≤i≤n)为记录，对给定的某个值 k，在表 L 中确定 key=k 的记录的过程，称为查找。若表 L 中存在一个记录 R i的 key 等于 k，记为 R i .key=k，则查找成功，返回该记录在表 L 中的序号 i （或R i 的地址），否则（查找失败）返回 0（或 NULL）。
查找算法有顺序查找、折半查找、分块查找、哈希查找等。查找算法会影响计算机的使用效率，应根据应用场合选择相应的查找算法。
6.1.1 顺序查找
顺序查找（Sequential Search）又可以称为线性查找，是最基本的查找技术。顺序查找的基本原理是从数据集合中的第一个（或最后一个）数据元素开始，逐个与给定值进行对比。如果某个数据元素与给定值相同，则查找成功。如果查找到最后一个（或第一个）数据元素，都与给定值不同，则查找失败。
顺序查找算法比较简单，以整型数据为例，代码如例所示。
6.1.1 顺序查找
6.1.1 顺序查找
例采用循环的方式遍历整个数据集合（数组），与指定值进行对比，相等则查找成功。程序运行结果如下。
运行结果中，输出指定值4，可见查找成功。
6.1.2 折半查找
当数据集合中的数据元素无序排列时，只能采用顺序查找，而如果这个数据集合中的数据元素是有序的，则可以采用折半查找来提高查找效率。
折半查找（Binary Search）又称为二分查找。折半查找的基本原理是在有序的表中取中间的数据作为比较对象。如果查找的值与中间的值相等，则查找成功；如果查找的值小于中间的值，则到有序表的左半区继续查找；如果查找的值大于中间的值，则到有序表的右半区继续查找。不断重复上述步骤，直到查找成功，如图所示。
6.1.2 折半查找
在折半查找的过程中，查找范围不断变化。每一次查找后，查找范围都会减小为原来的一半。代码参考教材6.1.2节。
例每一次查找数据前，都需要寻找当前有序表的中间值，并以此作为判断标准，与给定值进行对比。如果给定值小于中间值，则将查找范围减少，下一次查找有序表的左半区；反之则查找右半区。如果给定值与中间值相等，则查找成功，输出该中间值的下标。程序运行结果如下。
运行结果中，输入给定值5，显示查找失败，说明该值不在有序表（数组）中。输入给定值15，返回该值在有序表中的下标5。
由上述分析可知，折半查找的时间复杂度为O(log 2 n)，相较于顺序查找（时间复杂度为O(n)），折半查找更加高效。需要注意的是，折半查找的前提是数据集合必须是有序的。
6.1.3 分块查找
分块查找（Block Search）又称为索引顺序查找，是介于顺序查找与折半查找之间的查找算法，也是顺序查找算法的一种改进算法。
分块查找类似于从书籍中查找资料。假设读者需要从一本书中查找资料，一般的做法是先从目录开始，找到资料所在章节的起始页面，然后从该起始页向后寻找。这种做法明显要比从书的第一页向后查找快很多。因此，书籍在编辑时，都会将所有的内容按照一定的规则分成若干块（章），每一块再分为若干个小块（节），并设置它们的位置（页），形成一个目录，通过这个目录即可实现快速查找。这个目录就是索引表，这种查找方式就是分块查找。
分块查找需要将数据集合分成若干个块，并且这些块满足两个条件。
（1）块内无序，即每一块中的数据不要求有序。
（2）块间有序，即块与块之间是有序的。后一个块中的各个数据元素都比前一个块中的任何数据元素大。例如，第一个块中的数据元素都小于 30，那么第二个块中的数据元素都必须大于等于 30。
6.1.3 分块查找
分块查找算法的核心是设置一张索引表，索引表中的每一项（索引项）对应一个数据块。索引项由以下 3 部分组成。
（1）数据块中最大的数据元素。
（2）数据块中数据元素的个数。
（3）指向数据块中首元素的指针（块首指针），即首元素的地址。
数据块与索引表的关系如图所示。
6.1.3 分块查找
分块查找算法需要两步完成，具体如下。
（1）在索引表中查找数据所在的块，由于数据块之间是有序的，可以利用折半查找很快得到结果。例如，在图 6.2 中查找数据 43 所在的块，由于第 2 个数据块的最大值为 27，第 3 个数据块的最大值为 56，很容易判定数据 43 在第 3 个数据块中。
（2）根据索引表中的块首指针，在对应的数据块中按照顺序查找数据。（数据块中的数据是无序的，只能采用顺序查找。）
分块查找算法的代码参考教材6.1.2节。
6.1.3 分块查找
例使用结构体数组 NodeTable node[18]存储数据集合，IdxTable idx[3]为索引表，同样为结构
体数组，数据元素为 3 个。因此，测试使用的数据集合分为 3 个数据块，块长为 6。子函数 BlkSearch()
实现分块查找算法，其中调用函数 BiSearch()（折半查找算法）先查找数据所在的数据块，然后使用顺序查找的方式在数据块中查找具体的数据。程序运行结果如下。
输入待查找数据 48，由例的第 58 行代码可知，48 在数组中的下标值为 11，程序输出结果同样为 11，测试成功。
6.1.3 分块查找
例中，BiSearch()函数用来确定数据所在的块，具体分析如下。
（1）假设数据集合分为 10 个数据块（每个数据块中的数据元素不确定），如图所示。
（2）假设当前需要查找的数据 key 在数据块 4 中且不是块中的最大值，结合例中的函数BiSearch()可知，第一次执行 while 循环时，low 的值为 0，high 的值为 9，因此 mid 的值为 4。分析可知，key < idx[4].key，即待查找数据小于数据块 4 中的最大值，需要执行代码 high=mid-1，high 的值变为 3，如图所示。
6.1.3 分块查找
（3）第一次循环后，high 的值变为 3，low 的值不变。再次执行循环，mid 的值为 1。分析可知，key > idx[1].key，即待查找数据大于数据块 1 中的最大值，需要执行代码 low=mid+1，low 的值变为2，如图所示。
（4）第二次循环后，high 的值为 3，low 的值变为 2。再次执行循环，mid 的值为 2。分析可知，key > idx[2].key，即待查找数据大于数据块 2 中的最大值，需要执行代码 low=mid+1，low 的值变为3，如图所示。
6.1.3 分块查找
（5）第三次循环后，high 的值为 3，low 的值变为 3。再次执行循环，mid 的值为 3。分析可知，key > idx[3].key，即待查找数据大于数据块 3 中的最大值，需要执行代码 low=mid+1，low 的值变为4，如图所示。
（6）第四次循环后，low 的值为 4，high 的值为 3。由于 low 的值大于 high，循环结束。由图 6.7 可知，需要查找的数据在第 high+1 个数据块中。
6.1.4 哈希查找
1．哈希函数的构造方法
哈希查找（Hash Search）算法是通过计算数据元素的存储地址来进行查找的一种算法。算法的原理是查找时通过给定值 k 以及对应关系 f，便可以找到 k 值所对应的哈希地址 f(k)（不需要比较直接获得查找目标）。这种对应关系 f 就是哈希函数，通过这个思想建立的表称为哈希表。
哈希函数的构造方法有很多，具体如下。
（1）直接定址法。取关键字或关键字的某个线性函数值作为哈希地址，即 H(key)=key 或 H(key)=a×key+b（a,b 为常数）。
举例：某公司统计 25～60 岁的人数，以年龄作为关键字，哈希函数取关键字自身，假设需要知道年龄为 25 岁的人的数量，则直接查表中的第 1 项即可。
6.1.4 哈希查找
（2）数字分析法。取关键字中某些取值较均匀的数字位作为哈希地址。当关键字的位数很多时，可以通过对关键字的各位进行分析，去掉分布不均匀的位。这种方法只适合于所有关键字已知的情况。通过分析分布情况将关键字取值区间转化为一个较小的关键字取值区间。
举例：列出已知关键字中的 8 个关键字，如表所示。
6.1.4 哈希查找
由表中的 8 个关键字可知，关键字从左到右的第 1、2、3、6 位取值比较集中（第 1 位都为6，第 2 位是 1 或 2，第 3 位是 3 或 7，第 6 位是 2、6 或 8），不宜作为哈希地址，剩余的第 4、5、7、8 位取值较均匀，可选取其中的两位作为哈希地址。假设选取最后两位作为哈希地址，则这 8 个关键字的哈希地址分别为 2、75、28、34、15、38、62、20。
（3）平方取中法。取关键字平方后的中间几位作为哈希地址。
举例：求关键字的平方并选取中间位为作为哈希地址，如表所示。
6.1.4 哈希查找
（4）折叠法。将关键字分割成位数相同的几个部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。这种方法适用于关键字位数比较多，且关键字中每一位上数字分布大致均匀的情况。
（5）除留余数法。取关键字被某个不大于哈希表表长 m 的数 p 除后所得的余数作为哈希地址（p为素数）。
（6）随机数法。选择一个随机函数，取关键字的随机函数值作为其哈希地址，即H(key)=random(key)，其中 random()为随机函数。该方法适用于关键字长度不等的情况。
6.1.4 哈希查找
2．哈希冲突
由于通过哈希函数产生的哈希地址是有限的，而在数据比较多的情况下，经过哈希函数处理后，不同的数据可能会产生相同的哈希地址，这就造成了哈希冲突，如图所示。
6.1.4 哈希查找
除了构造哈希函数外，哈希算法的另一个关键问题就是解决哈希冲突，其方法有很多，具体如下。
（1）开放地址法。开放地址法有 3 种探测方式：线性探测、再平方探测、伪随机探测。线性探测指的是按顺序决定哈希地址时，如果某数据的哈希地址已经存在，则在原来哈希地址的基础上向后加一个单位，直至不发生哈希冲突。再平方探测指的是按顺序决定哈希地址时，如果某数据的哈希地址已经存在，则在原来哈希地址的基础上先加 1 的平方个单位，若仍然存在则减 1 的平方个单位，之后是 2 的平方，以此类推，直至不发生哈希冲突。伪随机探测指的是按顺序决定哈希地址时，如果某数据的哈希地址已经存在，则通过随机函数随机生成一个数，在原来哈希地址的基础上加上随机数，直至不发生哈希冲突。
（2）建立公共溢出区。建立公共溢出区存储所有造成哈希冲突的数据。
（3）再哈希法。对冲突的哈希地址再次进行哈希处理，直至没有哈希冲突。
（4）链地址法。对相同的哈希地址使用链表进行连接，使用数组存储每一个链表。
6.1.4 哈希查找
接下来将重点介绍链地址法的具体实现。链地址法又称为拉链法，其基本的思路是将所有具有相同哈希地址的不同关键字连接到同一个单链表中。如果选定的哈希表长度为 m，则可将哈希表定义为一个由 m 个头指针组成的指针数组 T[0…m－1]，所有哈希地址为 i 的数据，均以结点的形式插入以 T[i]为头指针的单链表，如图所示。
6.1.4 哈希查找
链地址法实现哈希查找算法的代码参考教材6.1.4节。
例中，插入的关键字共有 11 个，哈希表的长度为 13，对应 13 个链表。哈希函数为给定值
对哈希表长度取余（代码 28 与 61 行），得到结果为哈希地址（数组下标）。程序查询的给定值为 68，由插入的关键字可知，68 属于其中的一个关键字。程序运行结果如下。
6.1.4 哈希查找
由程序运行结果可知，输出数据为 13 个链表中的所有关键字，给定值 68 查找成功。程序构建
的哈希表如图所示。
图中，关键字共有 11 个，其中 16 与 68 的哈希地址相同，7 与 46 的哈希地址相同。
6.2 排序
6.2.1
排序的概念
返回目录
6.2.2
直接插入排序
6.2.3
希尔排序
6.2.4
直接选择排序
6.2 排序
6.2.5
堆排序
返回目录
6.2.6
冒泡排序
6.2.7
快速排序
6.2.8
归并排序
6.2 排序
排序（Sort）是将无序的记录序列调整为有序的序列。对序列进行排序有非常重要的意义，例如，对有序的序列进行折半查找，会提高查找的执行效率。在数据库和文件库中建立若干索引文件就会涉及排序的问题。在一些计算机的应用系统中按不同的数据段做若干统计同样也会涉及排序处理。排序效率的高低，直接影响计算机的工作效率。
6.2.1 排序的概念
排序指的是将无序的记录按照其中某个（或某些）关键字的大小以递增或递减的顺序排列起来的操作。其确切的定义为：假设有 n 个数据元素的序列(R 1 ,R 2 ,…R n )，其相应关键字的序列是(K 1 ,K 2 ,…K n )，要求通过排序找出下标 1,2,…n 的一种排列 P 1 ,P 2, …P n ，使得相应关键字满足非递减（或非递增）关系 K p1 ≤K p2 ≤…≤K pn ，从而得到一个按关键字有序排列的记录序列(R p1 ,R p2 …R pn )。
按照排序过程中涉及的存储器的不同，可以将排序分为内部排序与外部排序。内部排序指的是待排序的记录数较少，所有的记录都能存放在内存中进行排序。外部排序指的是待排序的记录数太多，不可能把所有的记录存放在内存中，排序过程中必须在内存与外存之间进行数据交换。
6.2.1 排序的概念
按照排序过程中对记录操作方式的不同，可以将排序分为四大类：插入排序、选择排序、交换排序、归并排序。其中，每一类排序都有很多经典的排序算法，如表所示。
6.2.2 直接插入排序
1．直接插入排序概述
直接插入排序（Insertion Sort）是一种简单直观的排序算法，其工作原理是先构建有序序列，然后在已排序序列中从后向前扫描，为未排序的数据找到相应位置并将其插入。
直接插入排序算法的具体操作步骤如下所示。
（1）从序列的第一个元素开始，该元素被认定为已排序。
（2）在已排序的元素序列中从后向前扫描，为下一个元素寻找位置。
（3）如果已排序的元素大于新插入的元素，则将已排序元素移动到下一位。
（4）重复步骤（3），直到已排序元素小于或等于新插入的元素。
（5）插入新元素。
（6）重复步骤（2）～（5）。
6.2.2 直接插入排序
接下来通过具体的序列对插入排序算法进行说明。如图所示，假设有一串未排序的元素。
执行上述算法描述的步骤（1），选择第一个元素作为已排序的元素，如图所示。
6.2.2 直接插入排序
执行上述算法描述的步骤（2），选择下一个元素（元素为 12），在已排序的元素中进行扫描，执行算法描述的步骤（3）、（4）、（5）。由于新插入的元素 12 大于已排序的元素 8，因此无须移动已排序的元素 8。插入元素 12 后的效果如图所示。
重复算法描述的步骤（2），选择下一个元素（元素为 65），在已排序的元素中从后向前扫描，执行步骤（3）、（4）、（5）。元素 65 先与元素 12 比较，再与元素 8 比较，新插入的元素 65 大于元素 8与元素 12，无须移动已排序的元素。插入元素 65 后的效果如图所示。
6.2.2 直接插入排序
重复算法描述的步骤（2），选择下一个元素（元素为 43），在已排序的元素中从后向前扫描，执行步骤（3）、（4）、（5）。元素 43 小于元素 65，将元素 65 向后移动，即两个元素位置交换；元素 43大于元素 12，则元素 12 无须移动。插入元素 43 后的效果如图所示。
重复上述操作，插入元素为 55，执行算法描述的步骤（3）、（4）、（5）。元素 55 小于元素 65，大于元素 43。插入元素 55 后的效果如图所示。
6.2.2 直接插入排序
重复上述操作，插入元素为 32，执行算法描述的步骤（3）、（4）、（5）。元素 32 小于元素 65、55、43，大于元素 12。插入元素 32 后的效果如图所示。
重复上述操作，插入最后一个元素 24，执行算法描述的步骤（3）、（4）、（5）。元素 24 小于元素65、55、43、32，大于元素 12。插入元素 24 后的效果如图所示。
6.2.2 直接插入排序
元素 24 插入完成后，整个排序过程结束。如图所示，新序列为递增序列。由上述分析可知，插入排序最坏的情况是序列是逆序的，最好的情况是序列是顺序的。例如，图中最后形成的序列是递增的，如果原始序列呈递减状态，则排序过程中，元素比较与移动的次数是最多的。
2．直接插入排序代码实现
直接插入排序的代码如例所示。
6.2.2 直接插入排序
6.2.2 直接插入排序
例的运行结果如下所示。
由程序输出可以看出，无序序列经过插入排序后，成为递增的有序序列。
6.2.3 希尔排序
1．希尔排序概述
希尔排序（Shell Sort）是希尔（Donald Shell） 于 1959 年提出的一种排序算法。希尔排序同样是一种插入排序，它是直接插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。希尔排序与直接插入排序的不同之处在于，希尔排序会优先比较距离较远的元素。
希尔排序的核心操作是将序列按照增量（增量等于组的数量）进行分组，然后对每一组中的序列使用直接插入排序算法进行排序。当所有组中的序列都完成排序后，增量变小，按照减小的增量再次分组（分组不影响元素的位置），分组后再进行直接插入排序，以此类推（增量越小，每组的元素就越多）。当增量减小为 1 时，整个序列分为一组，算法结束。
希尔排序在选择增量时，可以使增量 gap=length/2（length 为序列长度），缩小增量可以使用gap=gap/2 的方式，这种增量可以用一个序列来表示，称为增量序列。
6.2.3 希尔排序
接下来通过具体的序列对希尔排序算法进行说明。如图所示，创建一个原始的未排序的序列。
由图可以计算出，初始增量 gap=length/2=6，则整个序列可以分为 6 组，分别是[18,21]、[9,3]、[7,17]、[5,24]、[13,14]、[16,44]，如图 所示。
6.2.3 希尔排序
分别对 6 组序列进行直接插入排序（组与组互不影响），如图所示。
对比图可知，经过插入排序后，第 2 组的元素 3 与元素 9 交换了位置。完成排序后，减小增量 gap=gap/2=3，则整个序列分为 3 组，如图所示。
6.2.3 希尔排序
分别对重新分组的 3 组序列进行直接插入排序，如图所示。
对比图可知，第 1 组序列经过直接插入排序后为 5–18–21–24，第 2 组序列排序后
为 3–9–13–14，第 3 组序列排序后为 7–16–17–44。再次减小增量 gap=gap/2=1，则将整个序列作为一组，对整个序列进行直接插入排序，如图所示。
6.2.3 希尔排序
6.2.3 希尔排序
经过最后一次直接插入排序后，序列变为递增序列。从上述过程中可以看出，每一次改变增量都会进行一次直接插入排序。虽然希尔排序涉及多次插入排序，但就整体而言，希尔排序降低了直接插入排序算法中元素移动与判断的次数。
2．希尔排序代码实现
希尔排序算法的代码参考教材6.2.3节。
例中，每一次确定增量后，选择分组中的元素与同组中该元素的前一个元素进行对比，如果
满足交换条件则交换。程序运行结果如下所示。
程序运行结果中，增量序列为 4–2–1，排序后的序列为递增序列。
6.2.4 直接选择排序
1．直接选择排序概述
直接选择排序（Selection Sort）是比较稳定的排序算法，其时间复杂度在任何情况下都是 O(n 2 )。
直接选择排序是一种简单直观的排序算法，排序过程中，无须占用额外的空间。直接选择排序的工作原理是：首先在未排序的序列中找到最小（大）元素，存放到已排序序列的末尾；然后从剩余未排序元素中寻找最小（大）元素，放到已排序序列的末尾；以此类推，直到所有元素排序完毕。
由上述描述可知，直接选择排序就是反复从未排序的序列中取出最小（大）的元素，加入另一个序列，最后得到已经排好的序列。接下来通过具体的序列对直接选择排序算法进行说明。如图所示，创建一个原始的未排序的序列。
6.2.4 直接选择排序
选取第一个元素 5，分别与其他元素进行比较，当比较到元素 4 时，发现元素 4 小于元素 5，然后用元素 4 与其他元素进行对比，对比到元素 3 时，对比结束，将元素 3 放入已排序的序列，如图所示。
经过第一次排序，元素 3 进入已排序的序列。选取未排序序列中的第一个元素 7 再次进行比较，当比较到元素 4 时，发现元素 4 小于元素 7，然后用元素 4 与其他元素进行比较。元素 4 为最小值，
将其放入已排序的序列，如图所示。
6.2.4 直接选择排序
元素 3、4 进入已排序序列。选取元素 7 与其他元素再次进行比较，比较到元素 6 时，开始用元素 6 与其他元素进行比较。元素 5 为最小值，将其放入已排序的序列，如图所示。
元素 3、4、5 进入已排序序列。选取元素 8 与其他元素再次进行比较，比较到元素 6 时，开始用元素 6 与其他元素进行比较。元素 6 为最小值，将其放入已排序的序列，如图所示。
6.2.4 直接选择排序
元素 3、4、5、6 进入已排序序列。选取元素 8 与最后一个元素 7 进行比较。元素 7 为最小值，将其放入已排序的序列，如图所示。
经过第五次排序后，序列排序结束，为递增序列。
6.2.4 直接选择排序
2．直接选择排序代码实现
直接选择排序的代码参考教材6.2.4节。
例中的直接选择排序函数每次选择未排序的第一个元素与其他所有元素进行比较，找到最小元素后，将其与第一个元素进行交换。交换后的第一个元素作为已排序的元素。程序运行结果如下所示。
由运行结果可知，排序后的序列为递增序列。
6.2.5 堆排序
1．堆排序概述
堆排序（Heap Sort）是利用数据结构堆设计的一种排序算法。堆是一个近似完全二叉树的结构。如果堆中每个结点的值都大于或等于其左右孩子的值，则该堆称为大顶堆；如果堆中每个结点的值都小于或等于其左右孩子的值，则该堆称为小顶堆，如图所示。
6.2.5 堆排序
如果需要排序后的序列为增序序列，则选择大顶堆，反之选择小顶堆。
堆排序算法的具体操作步骤如下所示。
（1）用初始待排序的序列(R 1 ,R 2 ,…R n )构建大顶堆，则此堆为初始的无序区。
（2）将堆顶元素 R 1 与最后一个元素 R n 交换，将得到新的无序区(R 1 ,R 2 …R n-1 )和新的有序区(R n )，同时满足(R 1 ,R 2 ,…R n-1 )≤(R n )。
（3）由于交换后新的堆顶 R 1 可能违背大顶堆的性质，需要将当前无序区(R 1 ,R 2 ,…R n-1 )调整为新堆，然后将 R 1 与无序区最后一个元素交换，得到新的无序区(R 1 ,R 2 ,…R n-2 )和新的有序区(R n-1 ,R n )。
（4）重复上述过程，直到有序区的元素个数为 n－1，则整个排序过程结束。
6.2.5 堆排序
接下来通过具体的序列对堆排序算法进行说明。如图所示，构造一个初始未排序的堆。
将堆中的结点按照层序保存到数组中，如图所示。
6.2.5 堆排序
选取堆的最后一个非叶结点开始调整（lenth/2－1=5/2－1=1），即结点 1，按照从左到右、从下
到上的顺序进行调整。判断结点 1 的左右孩子是否小于该结点，可见结点 4 的值大于结点 1，因此将
结点 4 与结点 1 进行交换，如图所示。
结点 1 的值变为 8，大于结点 0 的值，因此将结点 1 与结点 0 进行交换，如图所示。
6.2.5 堆排序
交换结点后，结点 1 的值小于其左右孩子，结点 1、结点 3、结点 4 中结点 4 的值最大，将结点1 与结点 4 进行交换，如图所示。
经过交换后，无序的堆变为大顶堆。根据该堆与数组的对应关系，得出构造堆的规则。如图所示，a 为保存结点的数组，i 表示结点在数组的下标以及结点的编号。
6.2.5 堆排序
经过上述交换操作，堆成为大顶堆，其根结点的值大于所有子结点。此时将图 6.36 中的根结点与末尾结点进行交换（在数组中保存的末尾结点），如图所示。
经过交换后，结点 4 的值为堆中的最大值，对应数组的末尾，并且该结点将被视为有序序列的第一个元素。
对图 6.38 中的堆进行调整，使其满足大顶堆的规则。结点 0 的值小于其左右孩子，因此选择将结点 2 与结点 0 进行交换（结点 2 的值为当前最大值），如图所示。
6.2.5 堆排序
结点 0 的值为成为堆中的最大值，此时将堆中的根结点（结点 0）与末尾结点（末尾结点为结点3，结点 4 已排序）进行交换，如图所示。
经过交换后，结点 3 的值为堆中的最大值，且保存在数组的倒数第二位，结点 3 与结点 4 成为
有序序列。继续对堆进行调整，将结点 0 与结点 1 进行交换（结点 0 的值小于其左右孩子，且结点 1的值为当前最大值），如图所示。
6.2.5 堆排序
根结点的值成为堆中的最大值后，选择将根结点与末尾结点（结点 2）进行交换，如图所示。
经过交换后，结点 2 的值成为堆积中的最大值，且保存在数组的倒数第三位，成为已排序序列中的元素。
再次对堆进行调整，使其满足大顶堆的规则，即将结点 0 与结点 1 进行交换，交换后结点 0 的值成为堆中的最大值，如图所示。
6.2.5 堆排序
按照上述操作规律，接下来将根结点与末尾结点（结点 1）进行交换，交换后顶点 1 的值成为堆中的最大值，并将其保存至数组中，成为已排序序列中的元素，如图所示。
经过交换，最后一个结点 0 自动加入已排序的序列，至此，堆排序结束，排序后的序列为递增序列。
通过上述对堆排序的描述可知，其核心操作主要分为三个部分：用无序序列构造一个堆，并调整为一个大顶堆或小顶堆；将堆顶元素与末尾元素进行交换，将最大（小）元素放到数组的末尾；重新调整结构，使堆再次变成大（小）顶堆，再次进行元素交换，将最大（小）放到数组的末尾。反复执行上述过程，每次选出最大（小）元素，从数组的末尾开始依次进行存储，直到所有元素都被选出，则排序成功。
6.2.5 堆排序
2.堆排序代码实现
堆排序的代码参考教材6.2.5节。
堆排序算法的实现比其他排序算法复杂。其中，Make_Heap()函数用来实现第一次堆的调整，第一次调整堆是从堆中最后一个非叶结点开始的。第一次堆调整完成后，堆顶元素一定是整个堆的最大元素，将其与末尾元素进行交换，目的是将最大值存储到数组的末尾。元素交换导致堆顶元素不再是最大元素，破坏了大顶堆的规则，此刻除了堆顶元素，其他元素仍然满足大顶堆的规则，因此，后续堆调整都是从堆顶元素开始。Adjust_Heap()函数用来实现某个非叶结点与其子结点的调整，当该非叶结点为根结点时，函数调整的是整个堆。程序运行结果如下所示。
由运行结果可知，通过堆排序算法排序后的序列为递增序列。
6.2.6 冒泡排序
1．冒泡排序概述
冒泡排序（Bubble Sort）是一种简单且经典的排序算法。冒泡排序的核心思想是重复遍历整个序列，从第一个元素开始，两两比较相邻元素的大小，如果反序则交换，直到整个序列变为有序为止。
冒泡排序算法的具体操作步骤如下所示。
（1）比较相邻元素，从第一个元素开始，即第一个元素与第二个元素比较，如果前一个元素大于后一个元素就进行交换。
（2）每次比较完成后，移动到下一个元素继续进行比较，直到比较完最后一个元素与倒数第二个元素。
（3）所有元素比较完成后（一轮比较），序列中最大的元素在序列的末尾。
（4）重复上述 3 个步骤。
6.2.6 冒泡排序
接下来通过具体的序列对冒泡排序算法进行说明。如图所示，创建一个初始未排序的序列。
对该序列进行第一次排序。先比较第一个元素与第二个元素，再比较第二个元素与第三个元素，以此类推。如果前一个元素大于后一个元素，则将二者交换，反之不交换，如图所示。
6.2.6 冒泡排序
第一次排序后，最大元素 12 位于序列末尾。进行下一轮排序，如图所示。
第二次排序后，元素 10 位于序列倒数第二位。继续进行下一轮排序，如图所示。
6.2.6 冒泡排序
第三次排序后，元素 7 位于序列倒数第三位。继续进行下一轮排序，如图所示。
第四次排序后，元素 5 位于序列倒数第四位。继续进行下一轮排序，如图所示。
经过排序后，序列为递增序列。至此，冒泡排序结束。
6.2.6 冒泡排序
2．冒泡排序代码实现
冒泡排序的代码如例所示。
6.2.6 冒泡排序
6.2.6 冒泡排序
例中，Bubble_Sort()函数用来实现冒泡排序，其中使用 for 循环嵌套完成排序过程，第一层循环表示排序的轮次，第二层循环用来实现一轮排序（从第一个元素到最后一个元素的比较），每一轮排序都会从未排序的元素中确定一个最大值，并放到未排序序列的末尾。程序运行结果如下所示。
由运行结果可知，通过冒泡排序算法排序后的序列为递增序列。
6.2.7 快速排序
快速排序（Quick Sort）的核心思想是通过一轮排序将未排序的序列分为独立的两部分，使得一部分序列的值比另一部分序列的值小，然后分别对这两部分序列继续进行排序，以达到整个序列有序。
快速排序使用分治法将一个序列分为两个子序列，其具体的算法描述如下。
（1）从序列中选出一个元素，作为基准值。
（2）重新排序，将所有比基准值小的元素放到基准值前，所有比基准值大的元素放到基准值后（与基准值相同的元素可以到任一边）。
（3）采用递归的思想对小于基准值的子序列和大于基准值的子序列排序。
在上述算法描述的基础上，快速排序可以设计出很多版本。接下来将通过具体的序列展示快速排序的两个版本，分别为单指针遍历法与双指针遍历法（指针指的是方向选择，不是语法意义上的指针）。
6.2.7 快速排序
1．单指针遍历法
如图所示，创建一个无序的数字序列。
从序列的第一个元素开始，将元素 5 作为基准值，从序列末尾选择元素与基准值进行比较，即元素 2 与元素 5 进行比较。由于元素 2 小于元素 5，二者进行交换，如图所示。
6.2.7 快速排序
交换完成后，从序列开头选择元素与基准值进行比较，即元素 7 与元素 5 进行比较。由于元素 7大于元素 5，二者进行交换，如图所示。
从序列末尾选择元素与基准值进行比较，即元素 3 与元素 5 进行比较。由于元素 3 小于元素 5，二者进行交换，如图所示。
6.2.7 快速排序
从序列开头选择元素与基准值进行比较，即元素 1 与元素 5 进行比较。由于元素 1 小于元素 5，二者无须交换。移动至下一个元素，比较元素 6 与元素 5，元素 6 大于元素 5，二者进行交换，如图所示。
从序列末尾选择元素与基准值进行比较，即元素 8 与元素 5 进行比较。由于元素 8 大于元素 5，二者无须交换。移动至下一个元素，比较元素 4 与元素 5，元素 4 小于元素 5，二者进行交换，如图所示。
6.2.7 快速排序
经过一轮排序后，序列被分为两个子序列，元素 5 前的所有元素都小于元素 5 后的所有元素。将元素 5（可包含元素 5）前的序列视为一个子序列，元素 5 后的序列视为另一个子序列，接下来继续采用上述方式，对这两个子序列进行排序。
先处理第一个子序列，即元素 2 到元素 5，将元素 2 作为基准值。将子序列的末尾元素 5 与元素2 进行比较，元素 5 大于元素 2，无须交换。移动至下一个元素 4，同样无须交换。再次移动至下一个元素 1，元素 1 小于元素 2，二者进行交换，如图所示。
6.2.7 快速排序
继续从子序列的开头选择元素与基准值进行比较，即元素 3 与元素 2 进行比较。元素 3 大于元素 2，二者进行交换，如图所示。
经过交换，子序列再次分为两个子序列，即元素 1 到元素 2 为一个子序列，元素 3 到元素 5 为另一个子序列。将这两个序列继续按照上述方法排序，包括元素 8 到元素 7 的子序列。当所有子序列的元素个数变为 1 时，整个序列的排序工作结束。
由上述操作过程可知，一轮排序会产生两个子序列，且子序列会继续产生子序列。排序的轮次越多，子序列越多，子序列中元素的个数越少。无论产生多少子序列，其排序方式不变，因此排序的过程可以采用递归的思想来实现。
6.2.7 快速排序
2．单指针遍历法实现快速排序
采用单指针遍历法实现快速排序，如例所示。
6.2.7 快速排序
6.2.7 快速排序
例中，Quick_Sort()函数用来实现快速排序，通过函数嵌套实现递归操作，递归的目的是对每一轮排序产生的子序列进行排序。Quick_Sort()函数中，采用“挖坑填数”的方式实现了元素之间的交换，如图所示。
6.2.7 快速排序
挖坑填数”通过相互赋值覆盖掉不需要的数据，实现数据的交换。读者也可以定义交换元素的函数，使用直接交换的方式完成排序。程序运行结果如下。
由运行结果可知，经过快速排序后的序列为递增序列。
3．双指针遍历法
在单指针遍历法中，每次都是选择一个元素与基准值进行比较，而双指针遍历法是同时选择两个元素与基准值进行比较。如图所示，创建一个无序序列。
6.2.7 快速排序
图中，标志 i 处于第一个元素 15 的位置，标志 j 处于末尾元素 12 的位置。将元素 15 作为基准值，将标志 i 向右移动，标志 j 不变。对比标志 i 与标志 j 对应的元素，如图所示。
将标志 i 对应的元素与标志 j 对应的元素同时与基准值进行对比，元素 17 大于元素 15，元素 12小于元素 15，因此将标志对应的元素进行交换。元素交换后，小于基准值的元素在前，大于基准值的元素在后，标志 i 与 j 分别向右、向左移动一位，如图所示。
6.2.7 快速排序
由于标志 i 对应的元素 10 小于元素 15，需要将标志 i 继续向右移动一位，标志 j 位置不变。标志 i 对应的元素 16 大于元素 15，标志 j 对应的元素 13 小于元素 15，因此二者进行交换，如图所示。
元素交换后，较小的元素排在较大的元素前面。继续移动标志 i 与标志 j，使标志 i 对应的元素为 14，标志 j 对应的元素为 18，如图所示。
6.2.7 快速排序
标志 i 对应的元素 14 小于元素 15，标志 j 对应的元素 18 大于元素 15，因此二者不需要交换。继续移动标志 i 与标志 j（标志 i 与标志 j 都需要移动时，先移动标志 j，如果标志 i 与标志 j 发生重合，将基准值与标志对应的元素进行交换），如图所示。
元素 14 与基准值交换后，序列分为两个子序列，即元素 14 到元素 15 为一个序列，元素 18 到元素 17 为一个序列。分别对这两个子序列采用同样的方式进行排序，如图所示。
6.2.7 快速排序
继续通过移动标志进行排序，直到序列中的元素减少到 1 个为止。双指针遍历法与单指针遍历法一样，需要采用递归的思想实现。
4．双指针遍历法实现快速排序
采用双指针遍历法实现快速排序，示例代码参考教材6.2.7节。
例中，partition()函数实现每一轮排序都会产生两个子序列。Quick_Sort()函数通过嵌套实现递归操作，对子序列进行排序。程序运行结果如下所示。
由运行结果可知，排序后的序列为递增序列。
6.2.8 归并排序
1．归并排序概述
归并排序（Merging Sort）是利用归并的思想设计的一种排序算法，该算法是采用分治法的一个非常典型的应用。归并排序是一种稳定的排序方法，性能不受输入数据的影响。归并排序的核心思想是将已排序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列之间有序。
归并排序算法的具体描述如下。
（1）将长度为 n 的序列分成两个长度为 n/2 的子序列。
（2）对两个子序列分别进行归并排序。
（3）将两个排序好的子序列合并成一个最终序列。
归并排序主要的操作是分与合，分指的是将序列分为子序列，合指的是合并子序列。
6.2.8 归并排序
由于最开始的序列是无序的，因此对该序列采用递归的方式进行分割，直到每一个子序列都有序为止，如图所示。
一个无序的序列经过多次分割，最后每个子序列的元素个数为 1。当子序列的元素个数为 1 时，可以认为该子序列是有序的。
分割完成后，再对子序列采用递归的思想进行合并，如图所示。
6.2.8 归并排序
图展示的算法过程中，不仅需要将子序列合并，而且需要对合并的序列进行排序。接下来对图中的最后一次合并处理进行具体分析，如图所示。
由于子序列在合并前都是有序的，因此可以从子序列的第一个元素开始进行比较，将较小的元素放入一个新的数组中保存，如图所示。
6.2.8 归并排序
图中，标志 i 与标志 j 分别对应两个子序列的第一个元素。从第一个元素开始比较，标志 j对应的元素 1 小于标志 i 对应的元素 4，因此将元素 1 存入新数组的第一个位置。移动标志 j 到下一个位置，再次比较标志 i 与标志 j 对应的元素，如图所示。
标志 j 对应的元素 2 小于标志 i 对应的元素 4，因此将元素 2 存入新数组。移动标志 j 到下一个位置，再次比较标志 i 与标志 j 对应的元素，如图所示。
6.2.8 归并排序
标志 j 对应的元素 3 小于标志 i 对应的元素 4，因此将元素 3 存入新数组。移动标志 j 到下一个位置，再次比较标志 i 与标志 j 对应的元素，如图所示。
标志 j 对应的元素 6 大于标志 i 对应的元素 4，因此将元素 4 存入新数组。移动标志 i 到下一个位置，再次比较标志 i 与标志 j 对应的元素，如图所示。
6.2.8 归并排序
标志 j 对应的元素 6 大于标志 i 对应的元素 5，因此将元素 5 存入新数组。移动标志 i 到下一个
位置，再次比较标志 i 与标志 j 对应的元素，如图 所示。
标志 j 对应的元素 6 小于标志 i 对应的元素 7，因此将元素 6 存入新数组。元素 6 存入数组后，标志 j 无法移动，表示子序列遍历结束。此时将另一个子序列中剩余的元素按顺序依次存入新数组，如图所示。
6.2.8 归并排序
至此，已通过比较将所有子序列中的元素加入新数组，形成新的序列。归并排序中其他合并子序列的操作与上述操作相同。
2．归并排序代码实现
归并排序算法的代码参考教材6.2.8节。
例中，Merge_Sort()函数通过嵌套实现递归排序，Merge()函数用来实现合并子序列。程序运行结果如下所示。
由运行结果可知，排序后的序列为递增序列。
本章小结
本章主要介绍了算法中的两种常见操作——查找与排序，包括 4 种常见的查找算法与 7 种排序法。本章从操作原理与代码实现两个方面解释了每一种算法的核心思想。不同的算法在处理不同的情况时，效率也不同。因此，读者需要在理解这些算法的基础上，熟练编写操作代码，为在实际开发中优化数据操作奠定基础。

展开更多......

收起↑