第十七次课堂小结

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

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

第一次冒泡,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老师特意要求大家只需给出亮灯结果即可,无需添加灯具角色,因为这涉及到消息传递,需附加更多的脚本。

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

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

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

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

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

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180509G14MT800?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券