4.4 排序与查找

学习完列表、字典和元组后，我们趁热打铁，学习一下排序与查找的算法。

排序和查找是在实际工程中很常见的操作，它们有很多经典的方法。排序的目的是让数据能够以更有意义的形式表现出来，而查找的意义是在一个数据集中找到元素的位置。这两个内容可能有点难度，在这里我们不进行深入讲解，只对冒泡排序和二分查找这两个比较简单的算法来细谈。在完成这两个算法的学习后，将顺势引出算法复杂度的概念。

4.4.1 冒泡排序

冒泡排序是一种较为简单的排序算法，它会重复地访问要排序的数列，每次都比较两个元素，若是发现顺序有误就将它们交换过来。由于这个排序算法会很形象地将元素慢慢浮起（不断地两两交换），因此称为冒泡排序。

下面用一个例子来详细说明一下，我们构建一个乱序的化学元素列表（用元素在周期表中的序号作为排序的依据）['Cl', 'B', 'K', 'O', 'P']，为了便于编程，使用元素周期表的序号将这个列表抽象为[17, 5, 19, 8, 15]。准备好列表后，使用冒泡排序将这个列表进行升序排列。在给出具体的程序之前我们先用图4.4展示一下排序过程。

图4.4中只给出了大致过程，其中阴影中选定项的两两互换过程我们并没有给出。在图中的每行阴影选定的项，都会从头开始和同行中的第一个与阴影元素相邻的非阴影元素比较，顺序不对就交换。直到所有阴影元素都比较完，排序才完成。

可能这样说有点抽象，接下来给出具体的程序，让我们结合程序和图4.4再次分析。

程序4.6 冒泡排序：

输出：

分析：

在程序中我们使用了两个for循环嵌套，外层循环用于控制图4.4中右侧箭头的指向。内层循环用于从头开始不断选取箭头左边元素与外层所选的元素比较，若是顺序不对就将元素值调换。这样当外层循环结束，整个序列的排序工作完成。

4.4.2 二分查找

二分查找法作用于一个有序数据集合上。首先要查找的是有序集的中间的元素，如果中间元素比要查找的元素大，接着转向较小的半集中进行查找，反之，若中间元素比要查元素小，就转向较大的那个半集中进行查找。转进范围更小的数据集后重复这个查找过程，直到找到要查的元素或数据集不能再分割。

经过上面对二分查找的描述，我们对这个算法已经有所了解，二分查找法实质上就是不断地将有序数据集进行对半分割，并检查分区中的中间元素。上一小节中介绍了冒泡排序，正好可以使用冒泡排序的输出，也就是那个排好序的化学元素列表[5, 8, 15, 17, 19]。

假设想要知道氧元素在列表中的索引号，我们可以使用二分查找法来查找。下面，先来看看二分查找法是如何作用在这个有序的化学元素列表上的。详细过程如图4.5所示。

图4.5中的low和high是用来控制查找元素的两个边界值，它们圈起来的数据就是用于当前查找的数据集，mid表示的是low和high之间的中间值。接下来看看程序具体是如何操作的，如程序4.7所示。

程序4.7 二分查找：

输出：

分析：

从程序中可以看出，我们将low和high分别设置为列表索引0和len-1，在每次的while循环中将mid设置为low和high的中间值，若mid所指定的元素（element[mid]）比目标值小，将low移动到mid后的元素位置上，以此来更新搜索区间。同理，若mid所指定的元素比目标元素值大，将high更新到mid的前一个元素上。

随着循环不断推进，low从左向右移，high从右向左移，当mid处找到目标时，将trace标记为True并跳出循环。如果目标一直没找到，那low和high的指向将会重合并退出循环。这个过程也正是图4.5所展示的。