基本概念
排序是计算机中非常重要的一种操作，其目的是将一组无序的数据元素通过某种算法调整为有序的数据元素。
冒泡排序是一种简单直观的排序算法，简单来说就是，从第一个元素开始，依次比较相邻两个元素的大小，如果左边的数更大，则交换，然后进行下一个元素的比较，第一趟比较过后，可以确定最大的元素放到最后的位置，接着进行第二趟比较（遍历范围递减），直到完成所有排序。
示例步骤
核心思想：像气泡上浮一样，每次遍历将最大的数“冒”到数组末尾。
示例：排序 [5, 3, 8, 4]
第 1 轮遍历：（确定最大值8）
- 比较 5 和 3，交换 → [3, 5, 8, 4]
- 比较 5 和 8，不交换 → [3, 5, 8, 4]
- 比较 8 和 4，交换 → [3, 5, 4, 8]
- 最大值 8 被移到末尾。
第 2 轮遍历：（确定次大值5）
- 比较 3 和 5，不交换 → [3, 5, 4, 8]
- 比较 5 和 4，交换 → [3, 4, 5, 8]
- 次大值 5 被移到倒数第二位。
第 3 轮遍历：（完成排序）
- 比较 3 和 4，不交换 → [3, 4, 5, 8]
- 数组已有序。
代码实现
基本实现
void bubbleSort(int arr[], int len)
{for (int i = 0; i < len - 1; i++){// 每轮比较范围减少for (int j = 0; j < len - 1 - i; j++){if (arr[j] > arr[j + 1]) // 升序排序条件{//swap(arr[j], arr[j + 1]);int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}
优化实现
如果在某一轮遍历中没有发生任何交换，说明数组已经有序，可以提前结束排序。
void bubbleSort(int arr[], int len)
{for (int i = 0; i < len - 1; i++){bool flag = false; // 优化点：标记是否发生交换for (int j = 0; j < len - 1 - i; j++){if (arr[j] > arr[j + 1]){swap(arr[j], arr[j + 1]);flag = true;}}if (!flag) // 无交换说明已有序，提前终止{break;}}
}
算法分析
| 指标 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | 平均 O(n²) | 适合小规模数据 |
| 空间复杂度 | O(1) | 原地排序，无需额外内存 |
| 稳定性 | 稳定 | 相等元素不交换 |
一句话总结：冒泡排序通过多次遍历数组，将较大的元素逐步“冒泡”到数组末尾，直到所有元素都归位。
