冒泡排序 （ bubble sort ）是一种简单的排序算法，它的思想很好理解：
- 遍历序列每个元素，并与前一个进行比较，顺序有误就交换位置（单轮冒泡过程）；
- 不断重复执行上述冒泡过程，直到整个序列完全有序（重复执行冒泡过程）；
对于一个长度为 $n$ 的序列，每轮冒泡过程平均需要遍历 $\frac{n}{2}$ 个元素，进行 $\frac{n}{2}$ 次比较。此外，算法需要执行至少 $n-1$ 轮冒泡排序过程，才能保整个证序列完全有序。 因此，冒泡排序的 时间复杂度 是 $O(n^2)$ 。
冒泡过程
冒泡过程分为两种，一种是从序列前面往后面冒泡，另一种则反过来。我们以从后往前冒泡为例进行讲解，关键步骤如下：
- 用变量 $i$ 来记录当前元素下标，以便遍历整个序列；
- 将 $i$ 初始化为 $n-1$ ，指向序列最后一个元素；
- 每次将第 $i$ 个元素与它前一个元素 $i-1$ 进行比较，必要时交换位置；
- 将 $i$ 减一指向前一个元素，重复执行步骤 3 ，直到 $i$ 前面没有元素时退出循环；
下面是冒泡过程的动画演示，可以帮助理解：
冒泡过程示例代码如下，可结合注释和动画对照理解：
冒泡排序
一轮冒泡执行完毕后，最小的元素便位于序列最前面。
因此，对于长度为 $n$ 的序列，只要执行 $n-1$ 轮冒泡，即可保证序列完全有序。第一轮冒泡执行完毕后，最小的元素在位置正确了；第二轮执行完毕后，最小的 2 个元素位置正确了；以此类推。
下面这个动画，很好地演示了循环执行冒泡过程，对数组进行排序的整个过程：
冒泡排序示例代码如下，可结合注释和动画对照理解：
完整代码
【小菜学算法】系列文章首发于公众号【小菜学编程】，敬请关注：
小菜学编程
