冒泡排序通过相邻元素比较交换使较大元素逐步移到末尾，每轮确定一个最大值位置，共执行n-1轮，内层循环范围递减，若某轮无交换则提前结束，c++实现包含优化机制，时间复杂度最坏O(n²)、最好O(n)，空间复杂度O(1)，适用于小数据量或教学场景。
冒泡排序是一种基础的排序算法，核心思想是通过相邻元素的比较和交换，将较大（或较小）的元素逐步“浮”到数组末尾。虽然效率不高，适合小数据量排序，但它是理解排序逻辑的良好起点。
冒泡排序的基本逻辑
冒泡排序的过程就像气泡上升一样：每一轮比较相邻两个元素，如果前一个比后一个大（假设升序排列），就交换它们的位置。这样每一趟遍历后，最大的元素就会移动到当前未排序部分的最后位置。
重复这个过程，直到整个数组有序。总共需要进行 n-1 趟比较，每趟比较的范围逐渐缩小。
实现步骤与关键点
要正确实现冒泡排序，需注意以下几点：
立即学习“C++免费学习笔记（深入）”；
- 外层循环控制排序轮数：共执行 n-1 次，每轮确定一个最大值的位置
- 内层循环进行相邻比较：从第一个元素开始，比较到未排序部分的倒数第二个元素
- 交换条件判断：当前元素大于下一个元素时执行交换
- 优化机制可选：若某轮没有发生交换，说明数组已有序，可以提前结束
C++代码实现示例
下面是一个完整的C++冒泡排序实现，包含基础版本和优化版本：
#include <iostream> #include <vector> <p>void bubblesort(std::vector<int>& arr) { int n = arr.size(); bool swapped;</p><pre class='brush:php;toolbar:false;'>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; }
}
int main() { std::vector<int> data = {64, 34, 25, 12, 22, 11, 90};
std::cout << "排序前: "; for (int x : data) std::cout << x << " "; std::cout << "n"; bubbleSort(data); std::cout << "排序后: "; for (int x : data) std::cout << x << " "; std::cout << "n"; return 0;
}
该程序输出结果为：
排序前: 64 34 25 12 22 11 90
排序后: 11 12 22 25 34 64 90
时间复杂度与适用场景
冒泡排序在最坏情况下的时间复杂度是 O(n²)，最好情况（已有序）下为 O(n)，空间复杂度为 O(1)。由于其简单直观，常用于教学演示或对极小规模数据排序。实际项目中更推荐使用标准库中的 std::sort 函数。
基本上就这些，理解了比较和交换的核心机制，就能轻松掌握冒泡排序的实现逻辑。