第十七次课堂小结

今天，继续我们的排序算法。

上一节课完成了最小泡的冒出，即一次冒泡，这次课我们要依次将第二小值，第三大值…直到最后一个数据，分别冒出，实现链表所有值的排序。

第一次冒泡，n个数，需要比较n-1次，第二次冒泡，需要比较多少次呢？

显然，n-1个数需要比较n-2次……，直到最后剩余两个数，只需比较1次。因此，每一次冒泡是一个两两比较的循环，比较的位置终点逐渐少一，共有n-1次冒泡的过程。

完整的冒泡排序是一个两层循环嵌套。外层是冒泡的次数，内层是两两比较次数。两个循环变量之和为n。

每次比较后，相邻两数满足排序规则，但是被甩到链表前部的数值不一定满足排序，所以需要外层循环。

然而，如果我们遇到一些特殊的序列如“6 1 2 3 4 5”，显然，一次冒泡就可以实现排序，此时，有没有必要再外层循环呢？如何使计算机明白无需再进行冒泡了呢？

如果，在某次冒泡中，所有数值比较后没有发生交换，则说明已经排序完毕，无需继续；只要有一次交换，则不能停止下次冒泡。

是不是可以举个小旗子来标识有没有发生交换呢？

循环开始，举起旗子，只要有一次交换，就放下旗子，示意继续。

这个旗子可以用变量来标识。如果旗子变量为down，则意味着绿灯通行，继续循环，直到旗子变量为up，红灯亮起，停止运行。

标识变量在编程中用途很广，直接反应解决问题的逻辑，体现了人在计算机程序中的控制作用，是人脑智慧的用武之地。

冒泡排序算法中，两层循环的作用、循环变量的设置、都需要在深刻理解原理的基础上，用代码一句句完成。这是个长久发酵的内化过程，是细致梳理思维逻辑的结果。

打铁趁热，完整地实现了任意长链表的冒泡排序后，我们立刻投入到了一个新的链表应用项目：轮流开关灯。

一排N个灯泡，每个灯泡由一个开关单独控制。早晨，M个调皮学生陆续到校。第一个学生过来，每隔一个灯按一下开关，第二个学生，每隔两盏灯按一下开关，……，请统计，对于任意的M和N，最终亮灯的是哪几盏灯？

这是一群熊孩子的故事，题目很有趣，吸引了大家的注意力。

那么如何实现呢？利用公式求解？公式哪里来？

其实，这是一个利用计算机来模拟过程的项目，正是利用了计算机处理速度的优势，从而可以对很多不方便得到或没有公式解的问题，来进行模拟求解。

项目关键是确定灯的开关两种状态的表示。两个状态，用二进制数0和1来表示，这应该是最简便的一种表示方法了吧。

实现的过程仍然是链表、循环、判断等思维逻辑的整理，不再赘述。

为了简化大家的编程，着重理解解决问题的思路，Free老师特意要求大家只需给出亮灯结果即可，无需添加灯具角色，因为这涉及到消息传递，需附加更多的脚本。

然而，天一同学表现出了积极的主动性，为了让求解的过程可视化，在找不到灯泡角色的情况下，自己特意选了蜡烛，设计亮灭两种造型，开发相应脚本，同步显示计算机模拟的过程。

作为一个风华正茂的少年，具有这样旺盛的求知欲，怎么可能在学业上不进步呢？

最近看到一段关于成长的话，深以为然，权做结尾：

当一个人感觉到，他的生命能够按照他的自由意志展开，他会被热情充满，困顿、拖延、封闭和消极等将远离他，每一段时光他都不想浪费。

如果你正在养育一个孩子，你可以给他这种感觉。同时也别忘了，你自己也一样需要这种感觉。