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

一、核心原理重复相邻元素两两比较若逆序则交换每一轮把当前最大元素冒泡到末尾像气泡往上浮。每一轮确定一个末尾有序元素下一轮只需比较前面无序部分。二、算法特点稳定排序相等元素相对位置不变原地排序只常数级额外空间最好时间复杂度O(n)优化版已有序最坏 / 平均复杂度O(n2)空间复杂度O(1)三、普通版冒泡排序思路外层循环控制排序轮数共n-1轮内层循环每轮比较0 ~ n-1-i相邻元素前 后 就交换四、优化版思路设置标记位若某一轮没有发生任何交换说明数组已有序直接提前退出。C 源代码1. 基础版 冒泡排序cpp运行#include iostream #include vector using namespace std; // 基础冒泡排序 void bubbleSort(vectorint 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() { vectorint 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(vectorint 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() { vectorint a {1, 2, 3, 4, 5}; bubbleSortOpt(a); for (int x : a) cout x ; return 0; }五、关键知识点总结轮数最多n-1轮每轮结束后末尾 i 个元素已有序无需再比较优化核心标志位减少不必要循环适用场景数据量很小、几乎接近有序的场景不适合大数据量排序平方级复杂度效率太低