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

一、什么是冒泡排序？定义：冒泡排序是一种简单的排序算法，通过重复地遍历数组，比较相邻元素并交换顺序，直到数组有序。类比：就像水中的气泡逐渐上浮，较大的元素会“冒”到数组的末尾。特点：简单直观：适合初学者理解排序的基本原理。时间复杂度：最坏情况下为 (O(n^2))，适合小规模数据。二、冒泡排序的步骤遍历数组：从第一个元素开始，依次比较相邻元素。交换元素：如果前一个元素比后一个元素大，则交换它们的位置。重复遍历：每一轮遍历会将最大的元素“冒”到数组末尾。提前终止：如果某一轮遍历中没有发生交换，说明数组已经有序，可以提前结束排序。三、冒泡排序的代码实现1. 基础版本（未优化）#include<iostream>usingnamespacestd;intmain(){int arr[] = {5, 3, 8, 4, 2};int n = sizeof(arr) / sizeof(arr[]);// 外层循环控制排序轮数（共 n-1 轮）for (int i = ; i < n - 1; i++) {// 内层循环控制每轮比较的次数（每次减少 i 次比较）for (int j = ; 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 = ; i < n; i++) {cout << arr[i] << " "; }cout << endl;return;}运行结果：2 3 4 5 82. 优化版本（提前终止）#include<iostream>usingnamespacestd;intmain(){int arr[] = {5, 3, 8, 4, 2};int n = sizeof(arr) / sizeof(arr[]);bool swapped; // 标记是否发生交换for (int i = ; i < n - 1; i++) { swapped = false;for (int j = ; 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 = ; i < n; i++) {cout << arr[i] << " "; }cout << endl;return;}四、代码解析外层循环：控制排序的轮数（最多 n-1 轮）。每一轮确定一个最大值的位置。内层循环：每一轮遍历数组的前 n-i-1 个元素。比较相邻元素，如果顺序错误则交换。优化策略：使用 swapped 标志位，如果某一轮没有发生交换，提前终止排序。五、时间复杂度分析最坏情况：数组完全逆序，需要 (O(n^2)) 次比较和交换。例如：{5, 4, 3, 2, 1}。最好情况：数组已经有序，只需 (O(n)) 次比较（通过 swapped 提前终止）。六、竞赛注意事项数据范围：如果 n 超过 10000，冒泡排序可能超时，建议使用更高效的算法（如 sort）。边界条件：数组为空或只有一个元素时，无需排序。代码规范：确保循环变量正确，避免越界访问。七、综合练习练习 1：成绩排序输入一个整数 n，然后输入 n 个学生的成绩，按升序输出排序后的成绩。参考代码：#include<iostream>usingnamespacestd;intmain(){int n;cin >> n;int scores[n];for (int i = ; i < n; i++) {cin >> scores[i]; }// 冒泡排序bool swapped;for (int i = ; i < n - 1; i++) { swapped = false;for (int j = ; 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 = ; i < n; i++) {cout << scores[i] << " "; }cout << endl;return;}练习 2：找出第 k 大的元素输入一个整数 n 和 k，然后输入 n 个整数，使用冒泡排序找到第 k 大的元素。参考代码：#include<iostream>usingnamespacestd;intmain(){int n, k;cin >> n >> k;int arr[n];for (int i = ; i < n; i++) {cin >> arr[i]; }// 仅排序 k 轮，找到第 k 大元素for (int i = ; i < k; i++) {for (int j = ; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } }cout << "第 " << k << " 大的元素：" << arr[n - k] << endl;return;}八、总结冒泡排序通过相邻元素的交换逐步将最大值“冒”到数组末尾。优化策略：使用 swapped 标志位减少不必要的遍历。适用场景：小规模数据或教学示例。竞赛建议：优先使用 std::sort（更高效），但冒泡排序是理解排序逻辑的基础。