一、算法核心原理（冒泡过程）

冒泡排序的本质是暴力迭代交换。对于长度为 n 的数组，外层循环控制“需要冒泡的轮数”（共 n-1 轮），内层循环控制“当前轮需要比较的相邻元素对”。每完成一轮，当前未排序区间的最大值就被推到了末尾，下一轮比较次数减 1。

二、基础版 C++ 实现（最朴素写法）

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    // 外层循环：需要冒泡 n-1 轮
    for (int i = 0; i < n - 1; i++) {
        // 内层循环：每轮比较相邻元素，末尾 i 个已经排好，无需再碰
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) { // 升序，若左边大于右边则交换
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

三、经典优化：标志位提前终止（面试高频考点）

痛点：若数组本来就是有序的（如 [1,2,3,4,5]），基础版仍会傻傻执行完所有 n-1 轮比较，极其浪费。
优化策略：引入 swapped 布尔标志。若在一整轮内层循环中没有发生任何交换，说明数组已经全局有序，直接跳出外层循环。

void bubbleSortOptimized(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // 若本轮无交换，排序已完成，提前结束
        if (!swapped) break;
    }
}

优化后最佳时间复杂度可降至 O(n)（完全有序时）。

四、进一步优化：记录最后交换位置（减少无用遍历）

每次交换后，记录最后一次交换的位置 lastSwapIndex。该位置之后的元素已经有序，下一轮内层循环只需遍历到该位置即可，进一步缩小扫描范围。

void bubbleSortAdvanced(vector<int>& arr) {
    int n = arr.size();
    int lastSwap = n - 1;
    for (int i = 0; i < n - 1; i++) {
        int newLast = 0;
        for (int j = 0; j < lastSwap; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                newLast = j; // 更新最后交换位置
            }
        }
        lastSwap = newLast;
        if (lastSwap == 0) break;
    }
}

五、与 STL 对比及面试建议

• 为什么工程不用？ 因为 std::sort（内省排序）在百万级数据上比冒泡快成千上万倍。

• 为什么面试要考？ 考察你的代码基本功（边界条件）、优化意识（标志位）以及稳定性理解。

• 手撕要点：注意内层循环边界是 n-1-i（因为每轮末尾已有序），千万别写成 n-1 导致越界或重复比较。

 资源推荐

《C++八股文》2026版

贪心算法