第十课排序算法基础——让一群“乱站的同学”排好队一、这节课我们到底要学什么这一课结束以后同学们看到下面的代码for(int i0;in;i) { for(int j0;jn-1-i;j) { if(a[j]a[j1]) swap(a[j],a[j1]); } }要马上想到这是冒泡排序。并且能够回答排序是什么意思什么是升序、降序什么是比较什么是交换冒泡排序是怎么一步一步工作的为什么冒泡排序是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 a10; int b20; swap(a,b);执行以后a 20 b 10六、没有swap()怎么办假设int a10; int b20;不能直接ab; ba;因为第一步以后a20 b20原来的10丢掉了。所以需要一个“临时小盒子”int ta; ab; bt;模拟开始 a10 b20 ta t10 a10 b20 ab a20 b20 bt b10最终a20 b10这就是交换的基本原理。七、第一种基础排序冒泡排序想象有一排小朋友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 i0;in-1;i) { for(int j0;jn-1-i;j) { if(a[j]a[j1]) { swap(a[j],a[j1]); } } }这是初赛经常考的一段代码。十四、外层循环是什么意思for(int i0;in-1;i)表示一共进行若干轮。对于n个数字最多需要n-1轮十五、内层循环是什么意思for(int j0;jn-1-i;j)它负责这一轮从左到右比较相邻元素。为什么是n-1-i而不是n-1因为每做完一轮最右边就有一个元素已经确定。例如第一轮 □□□□8最后一个位置确定。第二轮□□□68最后两个位置确定。所以已经确定的位置不用再比较。十六、冒泡排序的核心代码真正的“灵魂”是相邻交换if(a[j]a[j1]) { swap(a[j],a[j1]); }这句话翻译成中文如果左边比右边大就把它们交换。这样大的数字就不断往右移动。十七、如果改成降序呢升序if(a[j]a[j1]) swap(a[j],a[j1]);降序if(a[j]a[j1]) swap(a[j],a[j1]);只需要改变和十八、CSP-J程序阅读特别容易考这个例如int a[5]{4,1,5,2,3}; for(int i0;i4;i) { for(int j0;j4-i;j) { if(a[j]a[j1]) swap(a[j],a[j1]); } }如果题目问最终数组是什么答案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 i0;in-1;i) { int ki; for(int ji1;jn;j) { if(a[j]a[k]) kj; } swap(a[i],a[k]); }这里最重要的不是swap。而是int ki;以及if(a[j]a[k]) kj;二十八、k到底是什么例如8 3 6 2 5开始i0我们暂时认为k0也就是a[k]8然后不断寻找更小的数字发现3于是k1发现2于是k3最终k3所以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 i1;in;i) { int xa[i]; int ji-1; while(j0 a[j]x) { a[j1]a[j]; j--; } a[j1]x; }这一段对于小学生来说比冒泡、选择稍微难一点。三十三、为什么叫“插入”假设已经排好 2 4 7 9现在x6我们从后面开始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[j1]选择排序关键词寻找最小值/最大值k记录最优位置。插入排序关键词插入已有序部分x j不断移动元素。三十六、sort排序如果题目给出sort(a,an);不要把它和冒泡排序混为一谈。这是C标准库提供的排序函数sort()对于进入复赛后题目有排序的需求我们首选就是sort排序。三十七、排序中的“比较器”先简单认识sort(a,an);默认从小到大如果sort(a,an,greaterint());则从大到小例如int a[5]{3,1,5,2,4}; sort(a,a5);得到1 2 3 4 5而sort(a,a5,greaterint());得到5 4 3 2 1这一部分和我们后面结构体排序课程还会再次联系起来。三十八、CSP-J程序阅读综合题现在来做一道初赛的题。int a[5]{5,2,4,1,3}; for(int i0;i4;i) { int ki; for(int ji1;j5;j) { if(a[j]a[k]) kj; } 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 寻找最小值首先想到选择。如果看到xa[i] while(...) a[j1]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²)练习给一个58个数的数组让孩子写出每一轮结束后的数组。2、重点选择排序 ↓ 插入排序 ↓ 三种排序比较 ↓ sort() ↓ CSP-J程序阅读题训练不运行程序只通过纸笔模拟排序过程。四十五、最后的一句话排序不是“把数字排整齐”这么简单。真正重要的是我们要学会让计算机用一套明确的方法把混乱的数据变得有顺序。再问大家“如果有100万个数字冒泡排序时间复杂度O(n²)还好不好”我们就产生了下一个问题“有没有比O(n²)更快的排序”下课预告第十一课高效排序与查找——快速排序、归并排序、二分查找为什么这么快