冒泡排序模板

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[] = {5, 3, 8, 1, 2, 7, 4, 6};
    int n = 8;

    // 基本冒泡排序
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j+1])
                swap(a[j], a[j+1]);

    for (int x : a) cout << x << " ";  // 1 2 3 4 5 6 7 8
    cout << endl;

    // 优化：提前退出
    int b[] = {5, 3, 8, 1, 2, 7, 4, 6};
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (b[j] > b[j+1]) {
                swap(b[j], b[j+1]);
                swapped = true;
            }
        }
        if (!swapped) break;  // 没有交换说明已排好
    }

    return 0;
}

📖 要点说明

• 时间复杂度 O(n²)，空间 O(1)
• 每轮把最大值冒泡到末尾
• 优化：加 swapped 标志，已排好提前退出
• 稳定排序：相等元素不交换，相对位置不变

⚠️ 常见错误

• 内层循环范围写错：j < n 越界
• 忘优化导致最好情况也是 O(n²)
• 降序排序判断方向写反