冒泡排序

冒泡排序bubble sort )是一种简单的排序算法,它的思想很好理解:

  1. 遍历序列每个元素,并与前一个进行比较,顺序有误就交换位置(单轮冒泡过程);
  2. 不断重复执行上述冒泡过程,直到整个序列完全有序(重复执行冒泡过程);

对于一个长度为 $n$ 的序列,每轮冒泡过程平均需要遍历 $\frac{n}{2}$ 个元素,进行 $\frac{n}{2}$ 次比较。此外,算法需要执行至少 $n-1$ 轮冒泡排序过程,才能保整个证序列完全有序。 因此,冒泡排序的 时间复杂度 是 $O(n^2)$ 。

冒泡过程

冒泡过程分为两种,一种是从序列前面往后面冒泡,另一种则反过来。我们以从后往前冒泡为例进行讲解,关键步骤如下:

  1. 用变量 $i$ 来记录当前元素下标,以便遍历整个序列;
  2. 将 $i$ 初始化为 $n-1$ ,指向序列最后一个元素;
  3. 每次将第 $i$ 个元素与它前一个元素 $i-1$ 进行比较,必要时交换位置;
  4. 将 $i$ 减一指向前一个元素,重复执行步骤 3 ,直到 $i$ 前面没有元素时退出循环;

下面是冒泡过程的动画演示,可以帮助理解:

冒泡过程示例代码如下,可结合注释和动画对照理解:

冒泡排序

一轮冒泡执行完毕后,最小的元素便位于序列最前面。

因此,对于长度为 $n$ 的序列,只要执行 $n-1$ 轮冒泡,即可保证序列完全有序。第一轮冒泡执行完毕后,最小的元素在位置正确了;第二轮执行完毕后,最小的 2 个元素位置正确了;以此类推。

下面这个动画,很好地演示了循环执行冒泡过程,对数组进行排序的整个过程:

冒泡排序示例代码如下,可结合注释和动画对照理解:

完整代码

小菜学算法】系列文章首发于公众号【小菜学编程】,敬请关注:

【小菜学算法】系列文章首发于公众号【小菜学编程】,敬请关注: