c++中如何进行冒泡排序_c++冒泡排序代码实现

冒泡排序核心是外层n-1轮遍历、内层每轮比较前n-i-1对相邻元素并交换，用std::swap和vector模板实现更安全；避免裸数组因长度退化导致越界，且不可用于生产环境。

冒泡排序的核心逻辑怎么写

冒泡排序本质是重复遍历数组，每次比较相邻两个元素，把较大（升序时）的“冒泡”到末尾。关键不是嵌套循环本身，而是边界控制和交换条件。

常见错误是内层循环上限写成 size 而非 size - i - 1，导致已排好序的末尾元素被反复比较甚至越界访问。

• 外层循环控制轮数，共 n-1 轮即可；第 i 轮后末尾 i 个元素已就位
• 内层循环只需比较前 n - i - 1 对相邻元素，避免冗余和越界
• 使用 std::swap() 比手写临时变量更安全、可读性更好

标准 C++ 实现（含 vector 支持）

用 std::vector 替代裸数组更符合现代 C++ 习惯，也避免手动传长度。注意函数模板能自动适配不同数值类型。

template 
void bubble_sort(std::vector& arr) {
    size_t n = arr.size();
    for (size_t i = 0; i < n - 1; ++i) {
        bool 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; // 提前退出优化
    }
}

为什么不用 raw array 写通用函数

对 int arr[5] 这类原始数组，无法直接推导长度（sizeof(arr) 在函数参数中退化为指针），必须额外传 size_t n。这容易出错且不安全：

• 调用者可能传错长度，导致越界读写
• 无法对 std::array 或 std::vector 复用同一接口
• std::vector 的 .data() 和 .size() 已封装好底层细节

所以优先用 std::vector& 或带长度的模板（如 template void bubble_sort(int (&arr)[N])），但后者仅限编译期确定大小的数组。

性能与实际使用提醒

冒泡排序时间复杂度始终是 O(n²)，即使加了提前退出，在随机数据下也几乎不起作用。它只适合教学、极小数据（≤50 元素）或已基本有序的特殊场景。

• 生产环境请直接用 std::sort() —— 它是混合算法（introsort），平均 O(n log n)
• 若需稳定排序且不能用 std::stable_sort()，考虑归并排序而非冒泡
• 调试时可在内层循环末尾加 std::cout 观察每轮结果

真正容易被忽略的是：很多人实现时忘了提前退出优化，或在多线程/并发环境下误以为冒泡“简单所以安全”——其实它不具备任何并发友好特性。