标准冒泡排序用两层for循环实现：外层控制n-1轮，内层逐对比较相邻元素并交换，确保每轮最大值沉底；常见错误是内层边界误写为i而非n-1-i。

冒泡排序的 C++ 基础实现长什么样

标准冒泡排序就是两层 for 循环，外层控制轮数（最多 n-1 轮），内层逐对比较相邻元素并交换。关键在于「相邻」和「每轮后最大值沉底」这个逻辑。

常见错误是内层循环边界写成 i 导致越界，或漏掉 swap 后的边界收缩（每轮后末尾已有序，可缩短比较范围）：

void bubbleSort(vector& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - 1 - i; ++j) { // 注意：上限是 n-1-i，不是 n-1
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

怎么提前终止优化冒泡排序

如果某一轮内一次交换都没发生，说明数组已完全有序，后续轮次纯属浪费。加个标志位就能让最好情况时间复杂度从 O(n²) 降到 O(n)。

容易忽略的是：标志位必须在每轮开始前重置为 false，否则会误判；且不能只靠外层 i 判断是否提前退出。

• 用 bool swapped = false 记录本轮是否有交换
• 每次交换后设为 true
• 本轮结束若仍是 false，直接 break

void bubbleSortOptimized(vector& 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; // 没交换，已有序
    }
}

C++ 中

vector 和原生数组写法有啥区别

核心逻辑一致，但传参方式和长度获取不同。用 vector 更安全（自动管理内存、支持 .size()），而原生数组传参会退化为指针，必须额外传长度。

常见坑是把数组名直接传给函数却没传 len，导致无法知道边界；或者误用 sizeof(arr)/sizeof(arr[0]) 在函数内部计算长度（此时 arr 是指针，结果恒为 1 或 2）。

• 原生数组推荐签名：void bubbleSort(int arr[], int len)
• 别在函数里用 sizeof 算长度
• 迭代器版本更泛型，但初学易绕晕，不建议一上来就写

为什么它被列为“经典”却不该在实际项目中用

冒泡排序教学价值远大于实用价值。它的 O(n²) 时间复杂度、频繁的交换操作（比快排/归并多得多）、以及无法利用 CPU 缓存局部性，让它在任何稍大点的数据集上都明显慢于 std::sort（通常是 introsort，平均 O(n log n)）。

真正要注意的是：面试写冒泡时，考官往往看的是你能否指出它的缺陷、能否写出带提前终止的版本、能否对比它和插入排序的异同——而不是只默写一个能跑通的循环。

如果你真在工程代码里写了冒泡排序，而且数据量超过几百，那问题大概率不在算法本身，而在你没搞清需求或没查 STL 文档。