冒泡排序

定义

冒泡排序是一种简单直观的排序算法。其名称来源于算法执行过程中较小的元素像气泡般逐步“浮”到数列的前端；也可描述为较大的元素不断“沉”向数列末端。

---

具体说明与示例

以无序数组 $A = [5, 4, 1, 3, 2]$ 为例，演示冒泡排序如何将最大元素逐步“沉”到末端：

• 第一轮（$i = 1$）

  • 比较 A[1] 与 A[2]：$5 > 4$，交换 $\to$ $[4, \textcolor{red}{5}, 1, 3, 2]$
  • 比较 A[2] 与 A[3]：$5 > 1$，交换 $\to$ $[4, 1, \textcolor{red}{5}, 3, 2]$
  • 比较 A[3] 与 A[4]：$5 > 3$，交换 $\to$ $[4, 1, 3, \textcolor{red}{5}, 2]$
  • 比较 A[4] 与 A[5]：$5 > 2$，交换 $\to$ $[4, 1, 3, 2, \textcolor{red}{5}]$
  • 结果：最大元素 5 沉到最后，数组变为 $[4, 1, 3, 2, 5]$。

• 第二轮（$i = 2$）

  • 比较 A[1] 与 A[2]：$4 > 1$，交换 $\to$ $[1, \textcolor{red}{4}, 3, 2, 5]$
  • 比较 A[2] 与 A[3]：$4 > 3$，交换 $\to$ $[1, 3, \textcolor{red}{4}, 2, 5]$
  • 比较 A[3] 与 A[4]：$4 > 2$，交换 $\to$ $[1, 3, 2, \textcolor{red}{4}, 5]$
  • 结果：第二大元素 4 沉到倒数第二位，数组变为 $[1, 3, 2, 4, 5]$。

• 第三轮（$i = 3$）

  • 比较 A[1] 与 A[2]：$1\leq 3$，不交换 $\to$ $[1, \textcolor{red}{3}, 2, 4, 5]$
  • 比较 A[2] 与 A[3]：$3 > 2$，交换 $\to$ $[1, 2, \textcolor{red}{3}, 4, 5]$
  • 结果：第三大元素 3 沉到第三位，数组变为 $[1, 2, 3, 4, 5]$。

• 第四轮（$i = 4$）

  • 比较 A[1] 与 A[2]：$1\leq 2$，不交换 $\to$ $[1, 2, 3, 4, 5]$
  • 结果：无改动，数组已有序，排序结束。

具体实现

设待排序数组为 A[1..n]：

• 外层循环：i 从 1 到 n-1（$n$ 个数字最多 $n-1$ 轮完成排序）。
• 内层循环：j 从 1 到 n-i：
  • 若 A[j] > A[j+1]，则交换 A[j] 与 A[j+1]。
• 每完成一次内层循环，当前最大元素被放到 A[n-i+1]。
• 重复上述步骤直至数组有序。

伪代码

\[\begin{array}{ll} 1 & \textbf{for } i\gets 1\textbf{ to }n-1\\ 2 & \qquad \textbf{for }j\gets 1\textbf{ to }n-i\\ 3 & \qquad\qquad\textbf{if }A[j]>A[j+1]\\ 4 & \qquad\qquad\qquad \text{swap }A[j]\text{ and }A[j+1]\\ \end{array}\]

为什么 $j$ 只遍历到 $n−i$？ 因为每完成一轮，末尾 $i$ 个元素已按大小顺序沉底，不再参与后续比较。

性质

稳定性

冒泡排序是一种稳定的排序算法。

时间复杂度

在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 $O(n)$。

在最坏情况下，冒泡排序要执行 $\frac{(n-1)n}{2}$ 次交换操作，时间复杂度为 $O(n^2)$。

冒泡排序的平均时间复杂度为 $O(n^2)$。