vlambda博客
学习文章列表

冒泡排序（bubble sort），是排序算法中的经典之一，也是Alevel 的考试要点，Alevel要求我们必须掌握的一种排序，它还是一种基础的交换排序。

大家一定都喝过汽水，汽水中常常有许多的小小的气泡哗啦哗啦飘到上面来，这是因为组成小气泡的二氧化碳比水轻，所以小气泡可以一点点地向上浮动。

而冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身的大小，一点点地向着数组的一侧移动。

具体如何移动呢？让我们一起先来看一个例子。有8个数字组成的一个无需数列{5,8,6,3,9,2,1,7}，我们希望按照从小到大的顺序对其进行排序。

按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换他们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。详细过程如下：

这样一来，元素9作为数列中最大的元素，就像是汽水里的小气泡一样，“漂”到最右侧。

这时，冒泡排序的第1轮就结束了。数列最右侧元素9的位置可以认为是一个有序区域，有序区域目前只有1个元素。

下面，让我们来进行第2轮排序。

第2轮排序结束后，数列右侧的有序区域有了2个元素，顺序如下：

后续的交换细节，这里就不详细描述了，第3轮到第7轮的状态如下：

到此为止，所有元素都是有序的了，这就是冒泡排序的整体思路。

冒泡排序是一种稳定的排序，值相等的元素并不会打乱原本的顺序。由于该排序算法的每一轮都要遍历所有元素，总共遍历（元素数量-1）轮。

冒泡排序的整体思路要用到两层循环，外层循环控制比较的轮数，应该是n-1轮

内层循环控制每一轮比较的次数，每一轮下来因为都能冒出一个最大数，所以每一轮的次数都上一轮少一次，直到所有的数字排好序。

python实现代码如下：

代码非常简单，使用双循环进行排序。外部循环控制所有的回合，内部循环实现每一轮冒泡处理，先进行元素比较，再进行元素交换。

下面来看看Alevel CS中伪代码的写法：

是不是发现代码并不难理解呢？但这只是冒泡排序的原始实现，不够高效，还存在很大的优化空间哦，请听下回分解。