冒泡排序通过重复比较相邻元素并交换位置，使较大元素逐步“浮”至末尾，实现数组排序。1. 从第一个元素开始，比较相邻两元素，若顺序错误则交换；2. 每轮遍历后最大元素移至末尾；3. 对前n-1个元素重复操作直至有序。C++实现中采用swapped标志位优化，若某轮无交换则提前结束。时间复杂度最坏为O(n²)，最好为O(n)，空间复杂度O(1)，是稳定排序算法，适合教学演示。
冒泡排序是一种简单直观的排序算法，适合初学者理解排序的基本逻辑。它的核心思想是重复遍历数组，比较相邻元素，如果顺序错误就交换它们。经过多轮遍历，较大的元素会像“气泡”一样逐渐“浮”到数组末尾。
冒泡排序基本原理
假设有 n 个元素的数组：
- 从第一个元素开始，比较相邻两个元素的大小
- 如果前面的元素比后面的大，就交换它们的位置
- 一轮遍历后，最大的元素会移动到数组末尾
- 对前 n-1 个元素重复上述过程，直到整个数组有序
C++ 实现代码示例
以下是一个完整的 C++
冒泡排序实现：
#includeusing namespace std; void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { // 标记是否发生交换，用于优化 bool swapped = false; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { // 交换相邻元素 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = true; } } // 如果没有发生交换，说明数组已经有序 if (!swapped) break; } }
// 打印数组 void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; }
// 示例使用 int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]);
cout zuojiankuohaophpcnzuojiankuohaophpcn "原始数组: "; printArray(arr, n); bubbleSort(arr, n); cout zuojiankuohaophpcnzuojiankuohaophpcn "排序后数组: "; printArray(arr, n); return 0;}
算法特点与优化说明
冒泡排序虽然效率不高，但易于理解和实现：
- 时间复杂度：最坏和平均情况为 O(n²)，最好情况（已排序）可优化到 O(n)
- 空间复杂度：O(1)，只使用常数额外空间
- 稳定性：是稳定排序，相等元素的相对位置不会改变
- 代码中使用了 swapped 标志位进行优化，若某轮无交换，立即结束
基本上就这些。冒泡排序适合小规模数据或教学演示，实际开发中更推荐使用快速排序或 std::sort。
