C++如何实现冒泡排序_C++基础排序算法代码与优化-C++-PHP中文网

C++如何实现冒泡排序_C++基础排序算法代码与优化

下次还敢

发布： 2025-12-03 05:23:13

原创

520人浏览过

冒泡排序通过重复比较相邻元素并交换位置实现排序，每轮将最大元素“冒泡”至末尾。1. 基本实现使用双层循环进行逐对比较与交换；2. 优化版引入swapped标志位，若某轮无交换则提前结束，最好情况时间复杂度由O(n²)提升至O(n)；3. 时间复杂度最坏和平均为O(n²)，最好为O(n)，空间复杂度O(1)，具有稳定性；4. 虽效率低但易于理解，适合教学场景，实际开发推荐使用std::sort。

c++如何实现冒泡排序_c++基础排序算法代码与优化

冒泡排序是一种简单直观的排序算法，适合初学者理解排序的基本逻辑。它的核心思想是重复遍历待排序数组，比较相邻元素并交换顺序错误的元素，直到整个数组有序。

基本冒泡排序实现

下面是一个标准的C++冒泡排序代码实现：

#include <iostream>
#include <vector>
<p>void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}</p><p>int main() {
std::vector<int> data = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(data);</p><pre class='brush:php;toolbar:false;'>std::cout << "排序后: ";
for (int x : data) {
    std::cout << x << " ";
}
std::cout << std::endl;
return 0;

登录后复制

}

说明：外层循环控制排序轮数，内层循环负责每一轮的相邻比较。每轮结束后，最大的元素会“冒泡”到末尾位置。

立即学习“C++免费学习笔记（深入）”；

百灵大模型

蚂蚁集团自研的多模态AI大模型系列

331

查看详情

优化版冒泡排序

如果某一轮中没有发生任何交换，说明数组已经有序，可以提前结束。这个优化能显著提升在接近有序数据上的性能。

void optimizedBubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    for (int i = 0; i < n - 1; ++i) {
        swapped = false;
        for (int 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; // 没有发生交换，已有序
    }
}

登录后复制

优化点：使用 swapped 标志位判断是否提前终止，最好情况时间复杂度可从 O(n²) 提升到 O(n)。