【一周一算法】第一周：冒泡算法

🧮 一周一个算法 · 第 1 周

冒泡排序（Bubble Sort）——最温柔的排序算法

“算法世界的 Hello World” —— 从冒泡排序开始，理解算法的核心：有序化的思想 + 复杂度的度量

---

🧭 一、算法引入：从“气泡上浮”说起

想象你有一列数字，它们像一串气泡。 每次比较相邻的两个，如果前一个更“大”，那它就“上浮”到后面。 经过一轮比较，最大的数就会被“冒泡”到最末尾。 重复这个过程，就能让所有气泡依次排好序。

形象化图示（升序排列）：

初始: [5, 1, 4, 2, 8]
第1轮: [1, 4, 2, 5, 8]   (8 冒到最右)
第2轮: [1, 2, 4, 5, 8]
第3轮: [1, 2, 4, 5, 8]   (已排序)

---

🧩 二、算法思想总结

核心思想：相邻元素两两比较，不符合顺序则交换，重复这一过程直到全部有序。

流程逻辑：

1. 外层循环控制“趟数”；
2. 内层循环进行相邻元素比较；
3. 每次外层结束，最大元素确定；
4. 可通过标志位检测是否提前有序（优化版）。

---

⚙️ 三、算法伪代码

procedure BubbleSort(A[0..n-1]):
    for i from 0 to n-2:
        swapped ← false
        for j from 0 to n-2-i:
            if A[j] > A[j+1]:
                swap(A[j], A[j+1])
                swapped ← true
        if not swapped:
            break  // 提前结束，数组已排序

---

💻 四、C++ 实现代码（含优化）

#include <iostream>
#include <vector>
#include <utility> // for std::swap

void bubbleSort(std::vector<int>& arr) {
    size_t n = arr.size();
    bool swapped;

    for (size_t i = 0; i < n - 1; ++i) {
        swapped = false;
        for (size_t j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // 若一趟中未发生交换，说明已排序完成
        if (!swapped)
            break;
    }
}

int main() {
    std::vector<int> arr = {5, 1, 4, 2, 8};

    bubbleSort(arr);

    std::cout << "排序结果：";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;

    return 0;
}

输出：

排序结果：1 2 4 5 8

---

📈 五、复杂度分析（数学视角）

1️⃣ 时间复杂度

• 最坏情况（完全逆序）：

  • 第 1 轮比较 $n-1$ 次

  • 第 2 轮比较 $n-2$ 次

  • …

  • 第 $(n-1)$ 轮比较 1 次 ⇒ 总比较次数：

    $$(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$$

    因此：

    $$T(n) = O(n^2)$$

• 最好情况（数组已排序 + 启用优化）：

  • 只需一趟比较，未发生交换

    $$T(n) = O(n)$$

• 平均情况： 元素随机分布，约为 $O(n^2)$。

---

2️⃣ 空间复杂度

• 仅使用一个辅助变量 swapped：

  $$S(n) = O(1)$$

---

3️⃣ 稳定性分析

冒泡排序是稳定排序算法。 即相同元素的相对顺序保持不变。 👉 当 A[j] == A[j+1] 时不交换。

---

🔢 六、数学扩展：为什么比较次数是 $\frac{n(n-1)}{2}$？

推导：

$$\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}$$

该数列为等差数列，首项为 1，末项为 $n-1$，项数为 $n-1$。 因此其求和公式是：

$$S = \frac{(1 + n - 1)(n - 1)}{2}$$

数学意义： 这其实表示“所有可能的无序对数量”。 每一对 $(i, j)$ 都需要至少比较一次，冒泡排序会检查所有这些对。

---

🚀 七、可视化理解（交换轨迹）

举例：[5, 3, 4, 1, 2]

轮次	操作	数组状态
1	交换 (5,3)	[3,5,4,1,2]
1	交换 (5,4)	[3,4,5,1,2]
1	交换 (5,1)	[3,4,1,5,2]
1	交换 (5,2)	[3,4,1,2,5]
2	交换 (4,1)	[3,1,4,2,5]
2	交换 (4,2)	[3,1,2,4,5]
3	交换 (3,1)	[1,3,2,4,5]
3	交换 (3,2)	[1,2,3,4,5]

---

🔍 八、算法改进方向

改进方法	思想	效果
提前退出标志	检测一趟是否发生交换	减少不必要比较
记录最后交换位置	限制下一趟的比较区间	更高效的优化版
鸡尾酒排序	双向冒泡（正向+反向）	改善局部有序性能

---

🧠 九、思考与练习

1. 如果要对 10000 个元素排序，冒泡排序大约需要比较多少次？ （提示：$\frac{n(n-1)}{2}$）

2. 若数组初始状态接近有序，冒泡排序是否仍然适合？为什么？

3. 尝试改写 bubbleSort()，实现降序排列。

---

🌱 十、延伸阅读

• 《算法导论》第 2 章：基础排序算法

• 《Programming Pearls》：关于冒泡排序的性能陷阱

• LeetCode 题目推荐：

  • #912 Sort an Array
  • #147 Insertion Sort List

---

✨ 总结

特性	说明
时间复杂度	平均 / 最坏：$O(n^2)$，最好：$O(n)$
空间复杂度	$O(1)$
稳定性	✅ 稳定
是否原地排序	✅ 是
适用场景	小规模、部分有序数据、教学演示

🧩 “冒泡排序不是最快的算法，但它是理解算法思想的最好入口。” —— 下一周，我们将进入 选择排序与插入排序，从“局部最优”出发，迈向更优的排序逻辑。