授课定位适用人群初中竞赛生、已掌握一维数组基础及变形操作的 CSP-J 入门选手前置基础熟练掌握数组遍历、元素交换、循环结构本节课目标吃透冒泡排序原理与代码模板掌握系统 sort 函数的竞赛标准用法升序、降序能独立完成排序类基础竞赛题理解排序的核心逻辑比较 交换一、课程导入竞赛考点说明在 CSP-J 入门组竞赛中排序是必考基础考点几乎所有数组综合题、统计题、模拟题都会用到排序比如 “找出第 k 大的数”“按成绩排序输出”“去重前先排序”。 上一节课我们学了数组元素交换而排序的核心就是 “反复比较 交换”—— 本节课我们重点掌握两种竞赛常用排序方式冒泡排序理解原理应对填空、简答题、系统 sort 函数实战首选高效简洁。 排序类题目难度低、套路固定掌握本节课内容能轻松拿下入门组排序类送分题占比约 25%同时为后续前缀和、差分、贪心等高阶算法打基础。二、核心知识点精讲配竞赛标准模板下标从 1 开始1. 排序的核心概念竞赛基础排序将数组中的元素按照从小到大升序或从大到小降序的顺序重新排列是数据处理的基础操作。 竞赛中最常用的排序场景统计元素出现频率前先排序方便去重查找第 k 大 / 第 k 小的数先排序模拟题中按要求排序输出如按成绩、按编号。2. 冒泡排序必学原理竞赛填空 / 简答常考核心原理通俗理解像水中的气泡一样每次从数组开头开始相邻两个元素两两比较如果顺序不对升序要求前小后大降序相反就交换它们的位置每一轮循环都会将当前未排序部分的 “最大数”升序或 “最小数”降序“冒泡” 到数组末尾重复多轮直到整个数组有序。升序冒泡排序竞赛标准模板默写#include iostream using namespace std; const int N 1005; int a[N]; int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; // 冒泡排序核心代码升序 // 外层循环控制排序轮数共n-1轮n个元素排n-1轮即可有序 for (int i 1; i n - 1; i) { // 内层循环控制每一轮的比较次数每轮比上一轮少1次末尾已排序 for (int j 1; j n - i; j) { // 相邻元素比较前大后小则交换升序 if (a[j] a[j 1]) { int temp a[j]; a[j] a[j 1]; a[j 1] temp; } } } // 输出排序后的数组 for (int i 1; i n; i) cout a[i] ; return 0; }降序冒泡排序修改一处即可只需将内层循环的比较条件改为 “前小后大则交换”if (a[j] a[j 1]) { // 降序前小后大交换 int temp a[j]; a[j] a[j 1]; a[j 1] temp; }冒泡排序关键注意点竞赛易错外层循环次数n-1轮n 个元素最后一个元素无需再排序内层循环次数n-i次每轮排序后末尾 i 个元素已有序无需再比较相邻元素比较时下标是j和j1避免越界内层循环j n-i确保j1 n。3. 系统 sort 函数竞赛实战首选高效简洁冒泡排序效率较低适合小数据竞赛中大数据量排序优先使用 C 标准库的sort函数 ——一行代码实现排序效率高、不易出错是竞赛选手的必备技巧。第一步引入头文件必须写否则编译错误#include algorithm // sort函数的头文件竞赛代码必加第二步sort 函数基础用法升序默认语法sort(数组起始地址, 数组结束地址1)下标从 1 开始时结束地址为a n#include iostream #include algorithm // 必须引入 using namespace std; const int N 1005; int a[N]; int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; // 升序排序默认排序a[1]~a[n] sort(a 1, a n 1); for (int i 1; i n; i) cout a[i] ; return 0; }第三步sort 函数降序排序竞赛高频两种常用写法推荐写法 1简洁不易出错写法 1使用 greaterint()推荐// 降序排序需包含algorithm头文件 sort(a 1, a n 1, greaterint());写法 2自定义比较函数了解即可应对复杂排序// 自定义比较函数返回true时a在前b在后降序 bool cmp(int a, int b) { return a b; // 降序a比b大a在前 } // 调用sort时传入比较函数 sort(a 1, a n 1, cmp);sort 函数竞赛注意事项重中之重必须引入#include algorithm头文件否则编译报错排序范围sort(a 1, a n 1)表示排序a[1]到a[n]下标从 1 开始漏写1会导致最后一个元素不参与排序数据类型匹配greaterint()对应 int 类型数组若为 double、char 数组需改为greaterdouble()、greaterchar()效率优势sort 函数底层是快速排序比冒泡排序快得多适合n≤1e5的大数据量竞赛常见。4. 冒泡排序与 sort 函数对比竞赛选择建议排序方式优点缺点竞赛使用场景冒泡排序原理简单适合理解排序逻辑应对填空 / 简答题效率低大数据量超时简答题、填空题、小数据排序sort 函数效率高代码简洁不易出错原理复杂无需掌握实战编程题、大数据量排序首选竞赛结论编程题优先用 sort 函数省时间、少出错填空题 / 简答题需写冒泡排序代码。三、课堂完整示范例题例题题目输入 n 个整数完成以下操作用 sort 函数将数组升序排序输出排序结果用冒泡排序将数组降序排序输出排序结果输出排序后数组的第 3 个元素若 n3输出最后一个元素。完整可直接提交代码#include iostream #include algorithm // sort函数头文件 using namespace std; const int N 1005; int a[N], b[N]; // a存原数组b存备份避免两次排序相互影响 int main() { int n; cin n; for (int i 1; i n; i) { cin a[i]; b[i] a[i]; // 备份原数组 } // 1. sort函数升序排序a数组 sort(a 1, a n 1); cout 升序排序结果; for (int i 1; i n; i) cout a[i] ; cout endl; // 2. 冒泡排序降序排序b数组 for (int i 1; i n - 1; i) { for (int j 1; j n - i; j) { if (b[j] b[j 1]) { // 降序比较条件 int temp b[j]; b[j] b[j 1]; b[j 1] temp; } } } cout 降序排序结果; for (int i 1; i n; i) cout b[i] ; cout endl; // 3. 输出指定位置元素 if (n 3) cout 第3个元素 a[3] endl; else cout 最后一个元素 a[n] endl; return 0; }四、本节课高频易错点课堂重点强调冒泡排序外层循环次数写错写成i n导致多循环一次浪费时间冒泡排序内层循环次数写错写成j n导致数组越界 RE 错误使用 sort 函数时忘记引入#include algorithm头文件编译报错sort 函数排序范围写错漏写a n 1的1导致最后一个元素不参与排序降序排序时greaterint()漏写括号写成greaterint编译错误两次排序共用一个数组导致第二次排序的原数组被修改结果错误需备份数组混淆升序、降序的比较条件导致排序结果颠倒。五、课堂配套练习题当堂训练 3-4 题练习 1 冒泡排序专项洛谷 P5715 数组排序要求用冒泡排序实现升序输出 考察冒泡排序模板的直接应用巩固原理练习 2 sort 函数专项洛谷 P1059 明明的随机数先用 sort 排序再去重 考察sort 函数升序用法排序后去重的基础思维练习 3 降序排序专项洛谷 P1781 宇宙总统用 sort 降序排序找出最大值及其位置 考察sort 降序用法结合查找操作练习 4 综合应用洛谷 P1116 车厢重组用 sort 排序统计交换次数基础 考察排序的实际应用理解排序与交换的关联六、课堂知识小结掌握冒泡排序的核心原理相邻比较 交换能默写升序、降序两种模板熟练使用系统 sort 函数记住 “升序默认、降序用 greaterint()”牢记头文件和排序范围明确竞赛场景选择编程题用 sort高效填空 / 简答用冒泡考原理规避排序常见错误越界、头文件遗漏、排序范围错误理解排序的核心价值排序后能更方便地进行查找、去重、统计等操作。七、课后作业布置默写冒泡排序升序、降序和 sort 函数升序、降序的代码模板每种写 2 遍独立完成当堂 4 道洛谷练习题提交 AC截图保存提交记录自主编写代码输入 n 个整数用 sort 函数降序排序后输出前 5 个元素若 n5输出所有元素预习下一节课 “桶排序计数思想与频率统计”了解 “桶” 的基本概念。