冒泡排序通过重复比较相邻元素并交换位置实现排序，每轮将最大元素“冒泡”至末尾。1. 基本实现使用双层循环进行逐对比较与交换；2. 优化版引入swapped标志位，若某轮无交换则提前结束，最好情况时间复杂度由O(n²)提升至O(n)；3. 时间复杂度最坏和平均为O(n²)，最好为O(n)，空间复杂度O(1)，具有稳定性；4. 虽效率低但易于理解，适合教学场景，实际开发推荐使用std::sort。
冒泡排序是一种简单直观的排序算法，适合初学者理解排序的基本逻辑。它的核心思想是重复遍历待排序数组，比较相邻元素并交换顺序错误的元素，直到整个数组有序。
基本冒泡排序实现
下面是一个标准的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++免费学习笔记（深入）”；
优化版冒泡排序
如果某一轮中没有发生任何交换，说明数组已经有序，可以提前结束。这个优化能显著提升在接近有序数据上的性能。
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)。
时间与空间复杂度分析
冒泡排序虽然实现简单，但效率不高，适用于小规模或教学场景。
- 最坏情况时间复杂度：O(n²)，完全逆序时
- 最好情况时间复杂度：O(n)，有序时（使用优化版本）
- 平均时间复杂度：O(n²)
- 空间复杂度：O(1)，只用常数额外空间
- 稳定性：稳定，相同元素相对位置不变
基本上就这些。冒泡排序重在理解过程，实际开发中建议使用 std::sort，它基于快速排序、堆排序和插入排序的混合实现，效率更高。但在学习排序原理时，自己动手写一遍冒泡排序很有帮助。
