CSP-J 初赛（以满分为目标）：第十课《排序算法基础——让一群“乱站的同学”排好队》
第十课：排序算法基础
——让一群“乱站的同学”排好队
一、这节课我们到底要学什么？
这一课结束以后，同学们看到下面的代码：
for(int i=0;i<n;i++) { for(int j=0;j<n-1-i;j++) { if(a[j]>a[j+1]) swap(a[j],a[j+1]); } }要马上想到：
这是冒泡排序。
并且能够回答：
排序是什么意思？
什么是升序、降序？
什么是比较？
什么是交换？
冒泡排序是怎么一步一步工作的？
为什么冒泡排序是
O(n²)？选择排序和冒泡排序有什么区别？
插入排序是怎么工作的？
CSP-J初赛程序阅读中，如何手算排序后的结果？
二、先问大家：为什么需要排序？
假设老师有5个同学：
小明 85 小红 72 小刚 96 小丽 81 小强 90现在老师问：
谁的成绩最高？
如果没有排序，可以一个一个比较。
但如果要求：
按照成绩从高到低排列。
我们就需要把数据重新安排：
96 90 85 81 72这就是：
排序。
三、什么叫排序？
排序就是：
按照某种规则，把一组数据重新排列。
最常见的是：
从小到大
1 2 3 4 5叫：
升序
从大到小
5 4 3 2 1叫：
降序
四、排序最核心的两个动作
绝大多数初学排序算法都在反复做两件事情：
比较 + 交换例如：
8 3我们比较：
8 > 3如果要求升序：
3 8这就叫：
交换。
五、C++中的swap()
C++提供了一个非常方便的函数：
swap(a,b);它的意思就是：
交换
a和b的值。
例如：
int a=10; int b=20; swap(a,b);执行以后：
a = 20 b = 10六、没有swap()怎么办？
假设：
int a=10; int b=20;不能直接：
a=b; b=a;因为第一步以后：
a=20 b=20原来的10丢掉了。
所以需要一个“临时小盒子”：
int t=a; a=b; b=t;模拟：
开始： a=10 b=20 t=a t=10 a=10 b=20 a=b a=20 b=20 b=t b=10最终：
a=20 b=10这就是交换的基本原理。
七、第一种基础排序：冒泡排序
想象有一排小朋友：
8 3 6 2 5我们要求：
从小到大排列。
我们从左向右比较相邻的两个数字。
八、第一轮
先比较：
8 3发现：
8 > 3应该交换：
3 8现在：
3 8 6 2 5继续比较：
8 6交换：
3 6 8 2 5继续：
8 2交换：
3 6 2 8 5继续：
8 5交换：
3 6 2 5 8注意发生了什么？
最大的8一路“冒”到了最右边。
所以叫：
冒泡排序。
九、第一轮之后发生了什么？
原来：
8 3 6 2 5第一轮：
3 6 2 5 8我们可以确定：
8已经到了正确的位置。
所以第二轮：
根本不需要再比较最后一个8。
十、第二轮
现在：
3 6 2 5 | 8比较：
3 6不用交换。
继续：
6 2交换：
3 2 6 5 8继续：
6 5交换：
3 2 5 6 8现在：
3 2 5 6 | 8又有一个数字：
6到了正确的位置。
十一、第三轮
3 2 5 | 6 8比较：
3 2交换：
2 3 5 6 8然后：
3 5不交换。
现在：
2 3 5 | 6 8十二、第四轮
只剩：
2 3已经有序。
最终：
2 3 5 6 8排序完成。
十三、把冒泡排序写成程序
for(int i=0;i<n-1;i++) { for(int j=0;j<n-1-i;j++) { if(a[j]>a[j+1]) { swap(a[j],a[j+1]); } } }这是初赛经常考的一段代码。
十四、外层循环是什么意思？
for(int i=0;i<n-1;i++)表示：
一共进行若干轮。
对于：
n个数字最多需要：
n-1轮十五、内层循环是什么意思？
for(int j=0;j<n-1-i;j++)它负责：
这一轮从左到右比较相邻元素。
为什么是：
n-1-i而不是：
n-1因为每做完一轮：
最右边就有一个元素已经确定。
例如：
第一轮： □□□□8最后一个位置确定。
第二轮：
□□□68最后两个位置确定。
所以已经确定的位置不用再比较。
十六、冒泡排序的核心代码
真正的“灵魂”是相邻交换：
if(a[j]>a[j+1]) { swap(a[j],a[j+1]); }这句话翻译成中文：
如果左边比右边大，就把它们交换。
这样大的数字就不断往右移动。
十七、如果改成降序呢？
升序：
if(a[j]>a[j+1]) swap(a[j],a[j+1]);降序：
if(a[j]<a[j+1]) swap(a[j],a[j+1]);只需要改变：
>和：
<十八、CSP-J程序阅读特别容易考这个
例如：
int a[5]={4,1,5,2,3}; for(int i=0;i<4;i++) { for(int j=0;j<4-i;j++) { if(a[j]>a[j+1]) swap(a[j],a[j+1]); } }如果题目问：
最终数组是什么？
答案：
1 2 3 4 5但是如果题目问：
第一轮结束后是什么？
就必须要去模拟操作：
4 1 5 2 3比较：
4 1 → 1 4 1 5 → 不变 5 2 → 2 5 5 3 → 3 5所以：
1 4 2 3 5十九、第二轮
从：
1 4 2 3 5开始。
比较：
1 4不变。
4 2交换：
1 2 4 3 54 3交换：
1 2 3 4 5所以第二轮结束：
1 2 3 4 5二十、为什么冒泡排序是 O(n²)？
外层循环：
大约n次内层循环：
大约n次所以：
n × n大约是：
n²因此：
冒泡排序的时间复杂度是 O(n²)。
这与讲义的复杂度表一致：冒泡排序属于O(n²)。
二十一、第二种：选择排序
接下来讲另一个经典的：
选择排序。
它和冒泡排序的思想完全不同。
二十二、选择排序像“选冠军”
还是：
8 3 6 2 5我们要升序。
第一步：
从所有数字里面找最小的。
最小的是：
2把它放到第一个位置：
2 3 6 8 5现在第一个位置确定。
二十三、第二轮
剩下：
3 6 8 5找最小：
3它已经在正确位置。
所以：
2 3 6 8 5二十四、第三轮
剩下：
6 8 5最小：
5把5放到第三个位置：
2 3 5 8 6二十五、第四轮
剩下：
8 6最小：
6交换：
2 3 5 6 8完成。
二十六、选择排序的核心思想
冒泡排序：
不断比较相邻元素，把大数往右推。
选择排序：
每一轮找一个最小值，放到正确位置。
一定要区分。
二十七、选择排序代码
for(int i=0;i<n-1;i++) { int k=i; for(int j=i+1;j<n;j++) { if(a[j]<a[k]) k=j; } swap(a[i],a[k]); }这里最重要的不是swap。
而是：
int k=i;以及：
if(a[j]<a[k]) k=j;二十八、k到底是什么？
例如：
8 3 6 2 5开始：
i=0我们暂时认为：
k=0也就是：
a[k]=8然后不断寻找：
更小的数字发现：
3于是：
k=1发现：
2于是：
k=3最终：
k=3所以：
swap(a[i],a[k]);就是：
交换a[0]和a[3]结果：
2 3 6 8 5二十九、选择排序也是 O(n²)
外层：
n次每次都需要寻找剩余元素中的最小值：
n次所以：
O(n²)三十、第三种：直接插入排序
这一种可以想象成：
你在整理扑克牌。
手里已经有：
3 5 8现在摸到：
4怎么办？
把4插入到：
3和5之间。得到：
3 4 5 8这就是：
插入排序。
三十一、插入排序过程
例如：
5 3 8 2 6第一张：
5已经有序。
第二张：
3插入：
3 5第三张：
8插入：
3 5 8第四张：
2插入到最前面：
2 3 5 8第五张：
6插入：
2 3 5 6 8完成。
三十二、插入排序代码
for(int i=1;i<n;i++) { int x=a[i]; int j=i-1; while(j>=0 && a[j]>x) { a[j+1]=a[j]; j--; } a[j+1]=x; }这一段对于小学生来说比冒泡、选择稍微难一点。
三十三、为什么叫“插入”？
假设：
已经排好： 2 4 7 9现在：
x=6我们从后面开始：
9 > 6所以：
2 4 7 9 ↓ 2 4 7 9把9往右移动：
2 4 7 _ 9继续：
7 > 6继续移动：
2 4 _ 7 9发现：
4 < 6停止。
把6放进去：
2 4 6 7 9这就是插入。
三十四、三个排序放在一起比较
| 排序 | 核心思想 | 平均/常见复杂度 |
|---|---|---|
| 冒泡排序 | 相邻比较，大数往后冒 | O(n²) |
| 选择排序 | 找最小值放前面 | O(n²) |
| 直接插入 | 把新元素插入已有序部分 | O(n²) |
三十五、容易混淆的地方
冒泡排序
关键词：
相邻比较
a[j] a[j+1]选择排序
关键词：
寻找最小值/最大值
k记录最优位置。
插入排序
关键词：
插入已有序部分
x j不断移动元素。
三十六、sort（）排序
如果题目给出：
sort(a,a+n);不要把它和冒泡排序混为一谈。
这是C++标准库提供的排序函数：
sort()对于进入复赛后，题目有排序的需求，我们首选就是sort（）排序。
三十七、排序中的“比较器”
先简单认识：
sort(a,a+n);默认：
从小到大如果：
sort(a,a+n,greater<int>());则：
从大到小例如：
int a[5]={3,1,5,2,4}; sort(a,a+5);得到：
1 2 3 4 5而：
sort(a,a+5,greater<int>());得到：
5 4 3 2 1这一部分和我们后面结构体排序课程还会再次联系起来。
三十八、CSP-J程序阅读综合题
现在来做一道初赛的题。
int a[5]={5,2,4,1,3}; for(int i=0;i<4;i++) { int k=i; for(int j=i+1;j<5;j++) { if(a[j]<a[k]) k=j; } swap(a[i],a[k]); }问：
程序结束以后数组是什么？
第一轮
5 2 4 1 3最小值：
1交换：
1 2 4 5 3第二轮
剩余：
2 4 5 3最小：
2不变：
1 2 4 5 3第三轮
剩余：
4 5 3最小：
3交换：
1 2 3 5 4第四轮
剩余：
5 4最小：
4交换：
1 2 3 4 5最终：
1 2 3 4 5三十九、初赛可能问：排序后某个元素在哪里？
例如：
int a[5]={5,2,4,1,3};排序以后：
1 2 3 4 5如果问：
4的下标是多少？
答案：
3注意C++数组下标从：
0开始。
所以：
1 → 0 2 → 1 3 → 2 4 → 3 5 → 4这又连接回前面的数组课程。
四十、排序为什么值得专门学习？
因为排序不是孤零零的一个算法。
它会和很多后面的算法连接起来：
排序 ↓ 二分查找 ↓ 贪心 ↓ 区间问题 ↓ 结构体排序 ↓ 优先队列 ↓ 图算法而考试也明确把排序和查找作为常见算法的重要组成部分；其中顺序查找为O(n)，二分查找为O(logn)且要求数列有序。
所以：
“先排序，再查找”
是竞赛程序中经常使用的思想。
四十一、本课和第10课的连接
第10课我们说：
冒泡排序 O(n²) 选择排序 O(n²)现在终于知道：
为什么它们是O(n²)。
例如冒泡：
外层： n 内层： n 总工作量： n×n = n²而选择：
第1轮：n-1 第2轮：n-2 第3轮：n-3 ……总次数大约：
(n-1)+(n-2)+...+1虽然不是严格的n²，但数量级是：
O(n²)这就是：
“会写算法”升级为“会分析算法”。
四十二、本课同学们要记住的“排序三兄弟”
建议课后画图：
排序 │ ┌──────────┼──────────┐ ↓ ↓ ↓ 冒泡 选择 插入 │ │ │ ↓ ↓ ↓ 相邻比较 找最小 往里插入 大数后移 放到前面 移动让位置 │ │ │ └──────────┼──────────┘ ↓ O(n²)只要看到代码里的：
相邻比较首先想到：
冒泡。
看到：
k 寻找最小值首先想到：
选择。
如果看到：
x=a[i] while(...) a[j+1]=a[j]可以想到：
插入。
四十三、本课CSP-J必考点总结
★ 必须掌握
1. 排序
按照一定规则重新排列数据。
2. 升序
小 → 大3. 降序
大 → 小4.swap(a,b)
交换两个变量的值。
5. 冒泡排序
相邻元素比较，需要时交换。
6. 选择排序
每一轮找最小/最大元素，放到正确位置。
7. 插入排序
把当前元素插入前面已经排好序的部分。
8. 三种基础排序
冒泡 O(n²) 选择 O(n²) 插入 O(n²)四十四、课后练习
1、重点：
排序概念 ↓ 比较 ↓ 交换 ↓ swap ↓ 冒泡排序 ↓ 手工模拟冒泡 ↓ 冒泡 O(n²)练习：
给一个5～8个数的数组，让孩子写出每一轮结束后的数组。
2、重点：
选择排序 ↓ 插入排序 ↓ 三种排序比较 ↓ sort() ↓ CSP-J程序阅读题训练：
不运行程序，只通过纸笔模拟排序过程。
四十五、最后的一句话
排序不是“把数字排整齐”这么简单。
真正重要的是：
我们要学会让计算机用一套明确的方法，把混乱的数据变得有顺序。
再问大家：
“如果有100万个数字，冒泡排序，时间复杂度O(n²)还好不好？”
我们就产生了下一个问题：
“有没有比O(n²)更快的排序？”