8.3.1　冒泡排序

1.冒泡排序的基本思想

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

图8－3展示了冒泡排序的一个实例。从图中可见，在冒泡排序的过程中，关键字较小的记录好比水中气泡逐趟向上飘浮，而关键字较大的记录好比石块往下沉，每一趟有一块“最大”的石头沉到水底。

图8－3 冒泡排序示例

2.冒泡排序算法

算法8.3 初级冒泡排序算法

严格意义上说，这段代码不算是标准的冒泡排序算法，因为它不满足“两两比较相邻记录”的冒泡排序思想，它更应该是最简单的交换排序而已。它的思路就是让每一个关键字都和它后面的每一个关键字比较，如果大则交换，这样第一位置的关键字在一次循环后一定变成最小值。如图8－4所示，假设我们待排序的关键字序列是｛9，1，5，8，3，7，4，6，2｝，当i＝1时，9与1交换后，在第一位置的1与后面的关键字比较都小，因此它就是最小值。当i＝2时，第二位置先后由9换成5，换成3，换成2，完成了第二小的数字交换。后面的数字变换类似，不再介绍。

图8－4 冒泡排序图示

它应该算是最容易写出的排序代码了，不过这个简单易懂的代码却是有缺陷的。观察后发现，在排序好1和2的位置后，对其余关键字的排序没有什么帮助（数字3反而还被换到了最后一位）。也就是说，这个算法的效率是非常低的。

我们来看看正宗的冒泡算法，有没有什么改进的地方。

算法8.4 正宗的冒泡算法

依然假设我们待排序的关键字序列是｛9，1，5，8，3，7，4，6，2｝，当i＝1时，变量j由8反向循环到1，逐个比较，将较小值交换到前面，直到最后找到最小值放置在第一的位置。如图8－5所示，当i＝1，j＝8时，我们发现6＞2，因此交换了它们的位置，j＝7时，4＞2，所以交换……直到j＝2时，因为1＜2，所以不交换。j＝1时，9＞1，交换，最终得到最小值1放置第一的位置。事实上，在不断循环的过程中，除了将关键字1放到第一的位置，我们还将关键字2从第九的位置提到了第三的位置，显然这一算法比前面的要有进步，在上十万条数据的排序过程中，这种差异会体现出来。图中较小的数字如同气泡般慢慢浮到上面，因此就将此算法命名为冒泡算法。

图8－5 排序图示（一）

当i＝2时，变量j由8反向循环到2，逐个比较，在将关键字2交换到第二位置的同时，也将关键字4和3有所提升，如图8－6所示。

图8－6 排序图示（二）

后面的数字变换很简单，这里就不再赘述。

3.冒泡排序优化

这样的冒泡程序是否还可以优化呢？答案是肯定的。试想一下，如果我们待排序的序列是｛2，1，3，4，5，6，7，8，9｝，也就是说，除了第一和第二的关键字需要交换外，别的都已经是正常的顺序。当i＝1时，交换了2和1，此时序列已经有序，但是算法仍然将i＝2到9，以及每个循环中的j循环都执行了一遍，尽管并没有交换数据，但是之后的大量比较还是多余了，如图8－7所示。

图8－7 排序图示（三）

当i＝2时，我们已经对9与8，8与7……3与2作了比较，没有任何数据交换，这就说明此序列已经有序，不需要再继续后面的循环判断工作了。为了实现这个想法，我们需要改进一下代码，增加一个标记变量flag，来实现这一算法的改进。

算法8.5 改进冒泡排序算法

代码改动的关键就是在i变量的for循环中，增加了对flag是否为true的判断。经过这样的改进，冒泡排序在性能上就有了一些提升，可以避免因已经有序的情况下的无意义循环判断。

冒泡排序过程中，一旦发现某一趟没有进行交换操作，就表明此时待排序记录序列已经成为有序序列，冒泡排序再进行下去已经没有必要，应立即结束排序过程。

4.冒泡排序算法的时间复杂度

分析冒泡排序的效率，容易看出，冒泡排序的比较次数和记录的初始顺序有关。若初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行n－1次关键字间的比较，且不移动记录；反之，若初始序列为“逆序”序列，则需进行n－1趟排序，需进行次比较，并作等数量级的记录移动。因此，总的时间复杂度为O（n2），存储开销为一个记录空间，供交换用。

冒泡排序的优点是：每趟结束时，不仅能挤出一个最大值或最小值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。

冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低；冒泡排序只需要一个记录的辅助空间，用来作为记录交换的中间暂存单元；冒泡排序是一种稳定的排序方法。