GESP 2级 · 冒泡排序

📖概念讲解

冒泡排序是最基础的交换排序算法，核心思想是相邻元素两两比较，把大的往后"冒泡"。每一轮会把当前未排序部分的最大值推到末尾。

💡 核心机制：外层控制轮数（n-1轮），内层逐个比较相邻元素，如果前一个比后一个大就交换。优化版：如果某一轮没有发生任何交换，说明已经有序，可以提前结束。

时间复杂度：最坏 O(n²)，最好（优化版）O(n)，平均 O(n²)。空间复杂度 O(1)，是原地排序。

💻代码示例

#include <iostream>
using namespace std;
int main() {
    int a[] = {5, 3, 8, 1, 2};  // 待排序数组
    int n = 5;                   // 数组长度
    for (int i = 0; i < n - 1; i++) {    // 外层：控制比较轮数，共 n-1 轮
        for (int j = 0; j < n - 1 - i; j++) {  // 内层：比较相邻元素，末尾已排好不用比较
            if (a[j] > a[j + 1]) {          // 如果前面的比后面的大
                int tmp = a[j];         // 交换 a[j] 和 a[j+1]
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
    for (int i = 0; i < n; i++) cout << a[i] << " ";  // 输出排序结果
    return 0;
}
// 输出：1 2 3 5 8

🧩互动小测

Question 1：冒泡排序内层循环的上界为什么是 n-1-i 而不是 n-1？

Question 2：对数组 {4, 2, 5, 1, 3} 做冒泡排序，第一轮结束后数组变成什么？

Question 3：冒泡排序是稳定排序吗？

🏋️动手练一练

📝 编程练习

题目：给定一个长度为 n 的整数数组，用冒泡排序将其从小到大排列，然后输出排序过程中交换的总次数。

输入：第一行一个整数 n，第二行 n 个整数。
输出：交换的总次数。

样例输入：5\n5 3 8 1 2
样例输出：7

提示：在交换时加一个计数器，每次 swap 时 +1。

参考答案：

#include <iostream>
using namespace std;

int main() {
    int n, a[105];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int cnt = 0;  // 交换次数计数器
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                cnt++;  // 每交换一次计数+1
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

要点：冒泡排序的交换次数就是逆序对的数量。对于 {5,3,8,1,2}，逆序对有 (5,3)(5,1)(5,2)(3,1)(3,2)(8,1)(8,2) 共 7 对。

📝易错点提醒

⚠️ 内层循环条件是 j < n-1-i，不是 j < n-1-i-1。别少写那个 i，否则会越界访问 a[j+1]。
⚠️ 交换三步别写错：先用 tmp 存 a[j]，再把 a[j+1] 赋给 a[j]，最后把 tmp 赋给 a[j+1]。顺序反了就覆盖了。
⚠️ 边界情况：n=0 或 n=1 时不需要排序，循环不会执行，直接输出就行。
💡 优化写法：加一个 bool 标记，如果某轮没有交换就 break，最好情况能从 O(n²) 降到 O(n)。

📘冒泡排序

📖概念讲解

💻代码示例

🧩互动小测

Question 1：冒泡排序内层循环的上界为什么是 n-1-i 而不是 n-1？

Question 2：对数组 {4, 2, 5, 1, 3} 做冒泡排序，第一轮结束后数组变成什么？

Question 3：冒泡排序是稳定排序吗？

🏋️动手练一练

📝 编程练习

📝易错点提醒