排序算法应该算是一个比较热门的话题，在各个技术博客平台上也都有一些博文进行了一定程度的讲解。但还是希望能从自我完善的角度出发，可以更详细、全面、形象地表达这些算法的精髓。本文就先从最简单的冒泡排序开始说起，别说你已经彻底了解了冒泡排序算法（虽然一开始我也是这样以为的）。

著作权归作者所有。 商业转载请联系作者获得授权，非商业转载请注明出处。 本文作者：Q-WHai 发表日期： 2016年01月29日 本文链接：https://qwhai.blog.csdn.net/article/details/50591859 来源：CSDN 更多内容：分类 >> 算法与数学

冒泡排序（Bubble Sort）是一种交换排序1，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　— 《大话数据结构》

一般来说，我们学习排序算法的入门都是从教科书中获得。而教科书上讲解的内容都是一些相对比较简单的，其目的是为了让人能够很好地去理解它，也可以让人能够很容易地编写出可行的代码。 　　教科书版冒泡排序的原理是对数组进行两层循环遍历。让数组中较小的关键字能够较快地移动到数组的顶部，从而当两层循环结束，排序即可完成。

如果你说这两个算法代码差不多，那就先把代码比对清楚，你会发现不同的地方还是很多的。通过上面的代码实现，我们可以很容易地画出如下过程图。（这次就感觉像是一个小气泡，在一点一点向上冒了。_）

通过对上面两种冒泡排序算法的学习，我们可以看到不管是哪一种算法，都不能很好地避免对一个已经有序的数组减少比较操作（只是不用做交换处理）。 　　现在，我们想到一种方法，使用一个标志位，来标识当前数组是否已经有序。如果无序，则继续冒泡排序；如果已经有序，则退出排序算法。这样就可以很好地规避掉一些不必要的比较操作。

从冒泡的原理上，我们可以知道，从前向后进行循环遍历交换和从后向前进行循环遍历交换的代价和逻辑是一致的，那么我们也就可以从后向前进行冒泡排序，代码就里就不再给出了。 　　在单向冒泡排序算法中，存在着一个著名的“乌龟问题”2。 　　而在排序过程中，又主要是这个过程耗费了大量时间。关于具体的实例在下面的“双向冒泡排序”算法中体现。

在基于冒泡排序的基础上，我们知道，无论是从前向后遍历交换，还是从后向前遍历交换，对程序的逻辑和性能的代价都是不影响的，那么我们就可以让一部分情况下从前向后遍历交换，另一部分情况从后向前遍历交换。

代码如下：

如果单纯从时间复杂度上来讨论，双向冒泡排序与冒泡排序算法复杂度是一致的。不过在双向冒泡排序算法中，我们引入了一些变量，以控制程序流程，在空间复杂度上虽然都O(1)，不过双向冒泡排序还是会大一些（至少有多了两个位置指针）。从代码的复杂度上，双向冒泡排序算法会大一些。 　　不过在上面的冒泡排序算法中，我们了解到冒泡排序算法有一个“乌龟问题”。正是因为这个原因，我们引入了双向冒泡排序算法。这里我们可通过一个实例更加象形地了解它。 　　假设我们现在有一个待排序序列**{6, 5, 4, 3, 2, 1}**。分别使用单向和双向冒泡排序对其进行排序，两种排序算法的过程如下(左图为单向冒泡，右图为双向冒泡)：

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。 ↩︎

乌龟问题说的是：假设我们需要将序列A按照升序序列排序。序列中的较小的数字又大量存在于序列的尾部，这样会让小数字在向前移动得很缓慢。 ↩︎