Python中排序算法之冒泡排序

排序算法是将给定的数列中的数进行升序（从小到大）或者降序（从大到小）排列。冒泡排序是排序算法的一种。

1 冒泡排序的原理

1.1 基本思想

冒泡排序是将数据中较大或者较小的数据依次向右推移的一种排序技术。它的基本思想是比较相邻的两个数，以升序为例，将较小的数放在前面，较大的数放在后面。

图1 第一次“冒泡”的步骤

1.2 第一次“冒泡”

假设数列中有“8、5、9、3”四个数，如图1①所示，要使用升序的方式对这四个数进行排列。首先比较8和5这两个数，因为8比5大，将这两个数的位置进行交换，如图1②、图1③所示；接下来比较8和9，因为9比8大，此时无需交换两个数的位置，如图1③所示；最后比较9和3这两个数，因为9比3大，将这两个数的位置进行交换，如图1④、图1⑤所示。这样，经过第一轮的比较与交换位置，数列中的最大值9就被推移到最右端，就像水中的气泡一样，冒了出来，所以这种排序方式叫做“冒泡排序”。

1.3 第二次“冒泡”

在进行第二次“冒泡”时，因为数字9已经作为数列的最大值“冒”了出来，接下来比较的就是“5、8、2”这三个数，如图2①所示。

图2 第二次“冒泡”的步骤

首先比较5和8，因为8比5大，所以不交换位置，如图2①所示；接下来比较8和3，因为8比3大，所以交换两个数的位置，如图2②和图2③所示。这样，数字8作为数列的第二大数“冒”了出来。

1.4 第三次“冒泡”

最后，比较剩下的5和3，因为5大于3，所以交换两个数的位置，如图3①和图3②所示。

图3 第三次“冒泡”的步骤

相关链接1 对n个数字进行排列，需要“冒”n-1次“泡”，即进行n-1次排序。

2 冒泡排序的代码实现

对列表中的数据进行冒泡排序，实际上就是变换数据的下标（索引号）。可以通过for循环的嵌套实现升序的冒泡排序，代码如图4所示。

图4 冒泡排序的代码

其中，第1行定义了包含四个数据的列表；第2行的for循环表示排序的次数，因为之前跳到n个数据要进行n-1次排序；第3行的for循环表示每次排序所要排的数据个数，从“1 冒泡排序的原理”中举的例子可以看出，第1次循环时要排4个数字，第2次循环时要排3个数字，第3次循环时要排2个数字，因此每次循环时要排的数字个数与循环次数有关；第4和第5行代码表示如果前面的数字大于后面的数字，则交换这两个数字的位置。排序后的列表如图5所示。

图5 排序之后的列表

相关链接2 如需降序排列，则只需将图4中的第4行代码“>”改为“<”即可。