冒泡排序：原理与优化全解析

一、核心原理

重复相邻元素两两比较，若逆序则交换；每一轮把当前最大元素冒泡到末尾，像气泡往上浮。每一轮确定一个末尾有序元素，下一轮只需比较前面无序部分。

二、算法特点

1. 稳定排序：相等元素相对位置不变
2. 原地排序：只常数级额外空间
3. 最好时间复杂度：O(n)（优化版，已有序）
4. 最坏 / 平均复杂度：O(n2)
5. 空间复杂度：O(1)

三、普通版冒泡排序思路

1. 外层循环：控制排序轮数，共n-1轮
2. 内层循环：每轮比较0 ~ n-1-i相邻元素
3. 前 > 后 就交换

四、优化版思路

设置标记位，若某一轮没有发生任何交换，说明数组已有序，直接提前退出。

C++ 源代码

1. 基础版 冒泡排序

cpp

运行

#include <iostream> #include <vector> using namespace std; // 基础冒泡排序 void bubbleSort(vector<int>& arr) { int n = arr.size(); // 共 n-1 轮 for (int i = 0; i < n - 1; ++i) { // 每轮比较到 n-1-i for (int j = 0; j < n - 1 - i; ++j) { if (arr[j] > arr[j + 1]) { // 交换 swap(arr[j], arr[j + 1]); } } } } int main() { vector<int> a = {5, 2, 9, 1, 5, 6}; bubbleSort(a); for (int x : a) cout << x << " "; return 0; }

2. 优化版（带有序标记）

cpp

运行

#include <iostream> #include <vector> using namespace std; // 优化冒泡排序：已有序直接提前结束 void bubbleSortOpt(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { bool isSorted = true; // 标记是否已有序 for (int j = 0; j < n - 1 - i; ++j) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); isSorted = false; } } if (isSorted) break; // 无交换，直接退出 } } int main() { vector<int> a = {1, 2, 3, 4, 5}; bubbleSortOpt(a); for (int x : a) cout << x << " "; return 0; }

五、关键知识点总结

1. 轮数：最多n-1轮
2. 每轮结束后，末尾 i 个元素已有序，无需再比较
3. 优化核心：标志位减少不必要循环
4. 适用场景：数据量很小、几乎接近有序的场景
5. 不适合：大数据量排序，平方级复杂度效率太低