CSP-J/S冲奖第16天：冒泡排序

摘要：定义：冒泡排序是一种简单的排序算法，通过重复地遍历数组，比较相邻元素并交换顺序，直到数组有序。类比：就像水中的气泡逐渐上浮，较大的元素会“冒”到数组的末尾。特点：简单直观：适合初学者理解排序的基本原理。时间复杂度：最坏情况下为 (O(n^2))，适合小规模数据

一、什么是冒泡排序？

定义：冒泡排序是一种简单的排序算法，通过重复地遍历数组，比较相邻元素并交换顺序，直到数组有序。类比：就像水中的气泡逐渐上浮，较大的元素会“冒”到数组的末尾。特点：简单直观：适合初学者理解排序的基本原理。时间复杂度：最坏情况下为 (O(n^2))，适合小规模数据。

二、冒泡排序的步骤

遍历数组：从第一个元素开始，依次比较相邻元素。交换元素：如果前一个元素比后一个元素大，则交换它们的位置。重复遍历：每一轮遍历会将最大的元素“冒”到数组末尾。提前终止：如果某一轮遍历中没有发生交换，说明数组已经有序，可以提前结束排序。

三、冒泡排序的代码实现

1. 基础版本（未优化）

#include
usingnamespacestd;

intmain{
int arr = {5, 3, 8, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);

// 外层循环控制排序轮数（共 n-1 轮）
for (int i = 0; i < n - 1; i++) {
// 内层循环控制每轮比较的次数（每次减少 i 次比较）
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;
}
}
}

// 输出排序后的数组
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;

return0;
}

运行结果：

2 3 4 5 8

2. 优化版本（提前终止）

#include
usingnamespacestd;

intmain{
int arr = {5, 3, 8, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);
bool swapped; // 标记是否发生交换

for (int i = 0; i < n - 1; i++) {
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;
}
}

for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;

return0;
}

四、代码解析

外层循环：

控制排序的轮数（最多 n-1 轮）。每一轮确定一个最大值的位置。

内层循环：

每一轮遍历数组的前 n-i-1 个元素。比较相邻元素，如果顺序错误则交换。

优化策略：

使用 swapped 标志位，如果某一轮没有发生交换，提前终止排序。

五、时间复杂度分析

最坏情况：

数组完全逆序，需要 (O(n^2)) 次比较和交换。例如：{5, 4, 3, 2, 1}。

最好情况：

数组已经有序，只需 (O(n)) 次比较（通过 swapped 提前终止）。

六、竞赛注意事项

数据范围：如果 n 超过 10000，冒泡排序可能超时，建议使用更高效的算法（如 sort）。数组为空或只有一个元素时，无需排序。确保循环变量正确，避免越界访问。输入一个整数，然后输入n个学生的成绩，按升序输出排序后的成绩。

参考代码：

#include
usingnamespacestd;

intmain{
int n;
cin >> n;
int scores[n];
for (int i = 0; i < n; i++) {
cin >> scores[i];
}

// 冒泡排序
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (scores[j] > scores[j + 1]) {
swap(scores[j], scores[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}

for (int i = 0; i < n; i++) {
cout << scores[i] << " ";
}
cout << endl;

return0;
}

练习 2：找出第 k 大的元素

输入一个整数n和k，然后输入n个整数，使用冒泡排序找到第k大的元素。

参考代码：

#include
usingnamespacestd;

intmain{
int n, k;
cin >> n >> k;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}

// 仅排序 k 轮，找到第 k 大元素
for (int i = 0; i < k; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}

cout << "第 " << k << " 大的元素：" << arr[n - k] << endl;
return0;
}