4.2　冒泡排序算法

冒泡排序法是模仿水中气泡上浮过程而创造的排序方法。以递增排序为例，其基本思想是：从第一个数开始，依次比较相邻的两个数，将小数放在前面，大数放在后面，经过一轮比较后，最大的数将位于最后一个位置。然后继续从第一个数开始，依次比较相邻数，直到将倒数第二大的数置于倒数第二位置。如此重复，直到所有数都完成排序。这个过程就好像一个个气泡逐渐从水底浮到了水面上。

例如，有这样一组数据：56, 20, 84, 66, 13，如图4.9所示。按照递增顺序进行排序，步骤如下。

（1）第一次排序。首先用第一个位置的56与第二个位置的20进行比较，因为56大于20，所以进行交换；然后再用第二个位置的56与第三个位置的84进行比较，因为56小于84，所以不用交换；再用第三个位置的84与第四个位置的66进行比较，因为84大于66，所以进行交换；最后用第四个位置84与第五个位置13进行比较，因为84大于13，所以进行交换。这样就完成了第一次排序，排序过程如图4.10所示。

经过第一次排序，最大值84被放在了最后的位置。因此在第二次排序时，只需要从第一个数开始，比较到倒数第二个数，也就是13即可。

为了便于表述，将前面未完成排序的数列称为新数列。后续的相邻数比较将在此数列中进行。

（2）第二次排序。依然从第一个位置开始比较，即20与56比较，20小于56，不用交换位置；然后56与66比较，56小于66，不用交换位置；最后66与13比较，66大于13，交换位置。这样就完成了第二次排序，排序过程如图4.11所示。

经过第二次排序，已经将新数列（20, 56, 66, 13）中的最大值66，也就是原数列的第二大值，放在了倒数第二的位置。因此，在进行第三次排序时，只需要从第一个数开始，比较到倒数第三个数，也就是13即可。

（3）第三次排序。依然从第一个位置开始比较，即20与56比较，20小于56，不用交换位置；再用56与13比较，56大于13，交换位置。这样就完成了第三次排序，排序过程如图4.12所示。

经过第三次排序，已经将新数列（20, 56, 13）中的最大值56，也就是原数列的第三大值，放在了倒数第三的位置。因此，在进行第四次排序时，只需要从第一个数开始，比较到13即可。

（4）第四次排序。依然从第一个位置开始比较，即20与13比较，20大于13，交换位置。因为只有两个数，第四次排序完成。

（5）第五次排序。此时新数列中只剩下13，13小于20，表明已经是最小的数了。至此，整个冒泡排序完成。第四、五次排序过程如图4.13所示。

接下来用Python代码实现上述冒泡排序算法。

【实例4.3】　使用冒泡排序法将列表中的数字递增排序。（实例位置：资源包\Code\04\03）

用Python代码实现上方示例中的冒泡排序算法，具体代码如下：

运行结果如图4.14所示，排序的步骤和上述介绍的冒泡排序法步骤完全吻合。

【实例4.4】　黄金档各综艺节目收视率排名。（实例位置：资源包\Code\04\04）

如今各电视台在周五的黄金档都会有独播的综艺节目。例如，某周的电视台黄金档综艺节目收视率数据如下：14、27、28、10、21，用冒泡排序法把此收视率按照从高到低的顺序递减排序。用Python实现具体代码如下：

运行结果如图4.15所示。