冒泡排序是C++入门必学的排序算法，通过重复遍历数组、两两比较并交换相邻元素，使较大元素逐轮“浮”至末尾，实现升序排列；支持模板泛化，时间复杂度最坏O(n²)，最好O(n)，稳定且空间复杂度为O(1)。
冒泡排序是C++入门必学的排序算法，原理简单、逻辑清晰，适合理解排序的基本思想。它通过重复遍历待排序数组，比较相邻元素并交换位置，让较大（或较小）的元素像气泡一样逐渐“浮”到一端。
核心思路：两两比较，逐轮下沉
每一轮遍历中，从第一个元素开始，依次比较相邻两个数；如果顺序错误（比如升序时前一个比后一个大），就交换它们。这样每轮结束，当前未排序部分的最大值就会被“冒泡”到末尾。重复这个过程，直到没有交换发生，说明已排好序。
基础实现（升序排列）
以下是一个标准、易懂的C++实现：
// 冒泡排序函数（升序）
void bubbleSort(int arr[], int n) {
for (int i = 0; i bool swapped = false; // 优化：记录是否发生交换
for (int j = 0; j if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break; 
// 提前退出：已有序
}
}
关键细节与常见优化
-
边界控制：内层循环上限用
n - 1 - i，因为每轮后末尾 i 个元素已就位，无需再比 -
提前终止：引入
swapped标志，若某轮无交换，说明整体已有序，直接退出 - 稳定性：冒泡排序是稳定排序——相等元素不会因交换而改变相对位置
- 时间复杂度：最坏/平均 O(n²)，最好（已排序）O(n)；空间复杂度 O(1)
扩展：支持任意类型（模板写法）
用模板泛化，让函数能处理 double、string 或自定义类（需支持 ）：
template
void bubbleSort(T arr[], int n) {
for (int i = 0; i bool swapped = false;
for (int j = 0; j if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}
基本上就这些。掌握冒泡排序，不单是为了排序本身，更是为理解后续快排、归并等算法打下逻辑基础。
