大家好！今天我们来学习一个简单又经典的排序算法——冒泡排序，并且用C++语言实现它。冒泡排序的名字听起来很有趣，它的核心思想就像水中的气泡会向上浮一样，小的元素会逐渐“冒”到数组的顶端，最终让整个数组变得有序。
一、冒泡排序的基本思想¶
冒泡排序的核心是重复比较相邻的两个元素，如果它们的顺序错误就交换位置。具体来说：
- 从数组的第一个元素开始，依次比较相邻的两个元素。
- 如果前一个元素比后一个元素大，就交换它们的位置。
- 这样一轮比较下来，数组中最大的元素会“冒泡”到数组的末尾。
- 重复上述过程，每一轮都能确定一个最大元素的最终位置，直到整个数组有序。
二、举个例子理解过程¶
假设我们有一个数组：[5, 2, 9, 1, 5, 6]，我们用冒泡排序来让它有序。
第一轮（确定最大元素9的位置）：
- 比较5和2：5>2，交换 → [2, 5, 9, 1, 5, 6]
- 比较5和9：5<9，不交换
- 比较9和1：9>1，交换 → [2, 5, 1, 9, 5, 6]
- 比较9和5：9>5，交换 → [2, 5, 1, 5, 9, 6]
- 比较9和6：9>6，交换 → [2, 5, 1, 5, 6, 9]
此时最大元素9已“冒泡”到数组末尾，无需再比较。
第二轮（确定第二大元素6的位置）：
- 比较2和5：2<5，不交换
- 比较5和1：5>1，交换 → [2, 1, 5, 5, 6, 9]
- 比较5和5：相等，不交换
- 比较5和6：5<6，不交换
此时第二大元素6已确定位置。
后续轮次类似，直到所有元素有序。
三、C++代码实现¶
下面是冒泡排序的C++代码实现，附带详细注释：
#include <iostream>
using namespace std;
// 冒泡排序函数：参数为数组和数组长度
void bubbleSort(int arr[], int n) {
// 外层循环：控制需要进行多少轮比较（n个元素需n-1轮）
for (int i = 0; i < n - 1; ++i) {
bool swapped = false; // 标记本轮是否发生交换
// 内层循环：每轮比较相邻元素，范围为数组前n-i-1个元素（已排好的最大元素不需要再比较）
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;
}
}
}
// 主函数：测试冒泡排序
int main() {
int arr[] = {5, 2, 9, 1, 5, 6}; // 待排序数组
int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
cout << "排序前数组：";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
bubbleSort(arr, n); // 调用冒泡排序函数
cout << "排序后数组：";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
四、代码解释¶
-
外层循环：
for (int i = 0; i < n - 1; ++i)
控制排序的轮数。由于n个元素最多需要n-1轮（每轮确定一个最大元素的位置），所以循环次数为n-1。 -
内层循环：
for (int j = 0; j < n - i - 1; ++j)
控制每轮的比较次数。每轮结束后，最大元素已“冒泡”到末尾，因此下一轮无需比较最后i个元素（i为当前轮次），比较范围缩小到n - i - 1。 -
交换逻辑：
int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;
使用临时变量temp交换相邻元素，确保交换过程中数据不丢失。 -
优化点：
bool swapped = false
如果某一轮没有发生交换，说明数组已完全有序，可提前退出外层循环，避免无效比较，提升效率。
五、运行结果¶
上述代码运行后，输出如下：
排序前数组：5 2 9 1 5 6
排序后数组：1 2 5 5 6 9
六、复杂度分析¶
- 时间复杂度：
- 最坏情况（完全逆序）：O(n²)（需完整n-1轮，每轮比较n-i次）。
- 最好情况（已排序）：O(n)（优化后仅需1轮，无交换直接退出）。
-
平均情况：O(n²)。
-
空间复杂度：O(1)（仅使用1个临时变量，原地排序）。
-
稳定性：稳定排序（相等元素不会交换位置）。
七、总结¶
冒泡排序是学习排序算法的入门首选，它的核心思想简单直观，容易理解。虽然效率不如快速排序、归并排序等高级算法，但通过它能帮助我们掌握“比较交换”的基本排序逻辑。如果你想进一步优化，可以尝试调整数组的初始化、修改交换条件等。动手实践是理解算法的最好方式，不妨尝试修改代码中的数组元素，看看不同情况下冒泡排序的表现吧！