“排序”的教学方法探究
中图分类号：G642.4 文献标志码：A 文章编号：1674-9324（2017）29-0194-02
一、引言
排序在现实生活中有非常重要的作用，许多场合，例如购物和数据分析都涉及对数据的排序。对于《程序设计》和《数据结构》这两门课程，“排序”都是一个非常重要的教学内容。排序算法实现的细节涉及的知识较多，包含变量、数组、选择结构、循环结构、数据交换与输入输出等，因而是课程教学的重点和难点。学生理解和掌握“排序”需要扎实的程序设计基础和良好的计算思维，教师讲授清楚“排序”则需要恰当的教学方法和丰富的教学设计，单单靠解释代码与演示排序过程不能达到良好的授课效果。许多文献如探讨了排序算法的教学策略。笔者在上海电机学院承担《软件开发基础Java》和《数据结构Java》两门课程，在“排序”章节的教学中，从概念引入、算法讲解、案例分析到课后实践等各环节，开展了和传统方式不同的教学方法和教学设计。本文以选择排序为例，探究了这种教学模式的有效性，希望为这一重要知识点的教学提供全新的思路。
二、概念引入设计
“排序”一节的知识理论上比较枯燥，排序算法比较多，各种排序算法的实现、区别和优缺点不容易理解。学生往往在学习时兴趣不高，对于算法代码、复杂度和稳定性等分析往往处于机械记忆，不能达到熟练应用的程度。让学生对这一知识点产生兴趣，并借助兴趣提高学习效果是概念引入环节的一个重要考虑。笔者在本章节开始时，提出三个生活中的实际例子供学生思考：①网购时经常按价格或销量的高低选择产品，网站如何快速实现海量商品信息的排序？②如何对学生的成绩按照某一学科或平均分排序？③打扑克牌抓牌时，手里的牌如何排放？学生往往在听到这三个例子后会引发短暂的思考，突然意识到排序这一问题并不抽象，出现在生活的方方面面，而且非常重要，愿意了解相关技术细节。
三、算法讲解设计
在讲解排序算法前，??该先让学生理解算法的主要思想。“选择排序”的思路很简单，即“拔大个”，每次在无序范围找出最大的，交换到无序范围的一端，无序区逐渐缩短，直到整个序列有序。在解释时，采取一边口述原理，一边在黑板上对一个序列进行相应操作的方式可以让学生非常直观的了解这一非常接近手工排序的算法的基本原理。在讲解完原理后，让学生对一个序列用该方法手工排序，加深对算法的理解，体会算法的自然性。然后就可以按照传统的做法，进行动画演示，先演示逐步排序的动画，再进一步演示逐趟的排序，最后自动演示一个完整的排序，让学生对算法的印象更深刻。对于动画的选择，可以采用传统的PPT动画、Flash动画和Gif动画等，甚至可以播放一些真人模拟排序过程的视频，提高课堂的活跃气氛和学生的兴趣。然后给出用编程语言，如Java语言描述的算法代码。排序是一个比较复杂的问题，在实际应用中远非对一组整数或浮点数进行排序那样简单。例如对商品，可以根据销量排序，可以根据价格排序，可以根据好评率排序等。因而理论上讲应该定义类描述待排序的物体，类中包含多个成员变量描述物体的不同属性，即排序的键值，排序时选择其中一个作为主键值，对多个对象进行排序。这样做虽然提高了程序的功能和通用性，但大大提高了代码的复杂性和实现算法的难度，让教学的重心从算法的核心思想分散到类与对象的操作，不利于让学生在短时间内快速而透彻的理解算法自身。因而可以采取简化策略，即使使用面向对象的程序设计语言，也将问题简化到只对一个整型数组进行排序，将所有其他复杂因素排除，将教学集中于算法的本质。在讲解代码前，可以先隐去最关键的部分，如循环体等，让学生根据算法的原理自行补充。这一环节的一个难点是设计的程序设计语言细节较多，如数组、选择结构、循环结构和数据交换等。对于《程序设计》这门课，排序的内容一般安排在学习数组时，此时学生对数组尚未完全掌握和理解，用数组实现排序算法比较有挑战性。对于《数据结构》这门课，学生可能对相关知识有所遗忘。程度一般的学生可以先用自然语言或伪代码书写，再翻译为编程语言，程度好的可以直接用编程语言书写。如果学生普遍不能写出，还可以对隐去的每一句代码都加一个注释，让学生将注释翻译为代码。最后再公布参考代码，供学生纠错。排序算法的实现通常有多种，对从小到大进行的选择排序而言，每次可以将最小的数据交换到无序区间的左侧，也可以将最大的数据交换到无序区间的右侧。在用二重循环实现算法时，内外循环的循环控制变量可以表示多重意义，例如外层循环控制变量可以表示无序区间的左端点、右端点、第几轮排序等，对每一种不同的变量意义，变量的初始值、循环条件、迭代方式和循环体可能都有区别。在代码实现这一环节，应鼓励学生用不同的方式去实现同一个算法，进一步加强学生程序设计的能力。最后是对算法的分析。对于选择排序，从算法每次选择最值再交换的做法能够简单地得到算法的时空复杂度。而对于算法的稳定性，从选择排序存在非相邻数据的交换过程也不难引导学生分析出这一算法是不稳定的。
四、案例分析设计
在完整讲解算法之后，使用一些案例演示排序算法能进一步增强学生对算法的理解。在选择实例时，数据应该丰富且量足够大，包含随机生成的数据、从小到大排好的数据、从大到小排好的数据等各种情况。每一轮排序后，输出当前的结果，并在结束时输出数据总量和所用时间。接下来可以将案例进行拓展，由数值排序引申到字符排序，因为字符的本质就是数值（Unicode或ASCII等），对字符排序既是对字符编码的数值进行排序，因而“选择排序”算法可以几乎不加修改地用于对单个字符排序。然后可以将排序的方式引申为对二维数组，例如像Excel表中按照最后一列排序。学生很自然地容易想到，在排序时，只对最后一列数据进行最值的选择，交换时整行数据都交换。但这样做显然数据的移动量较大，降低了速度，耗费了内存。这时可以启发学生注意最后一列的排序结果影响的是二维数组行的排列，即行序号的重排。那么在排序时可以暂时忽略其他列，对行序号和最后一列构成的二维数组按照最后一列的数据进行选择排序，每次交换都交换一整行，得到的行序号最终重排结果就是原二维数组每行的最终排列顺序。只要按照这个顺序重新排列各行就可以得到排序后的二维数组。这样做的好处是，无论该二维数组有多少列，排序过程都只对两列数据进行，时空复杂度都只和行数有关。 五、?n后实践设计
由于课堂时间有限，排序算法众多，需要学生通过课外加以扩展。可以让学生修改程序，每次随机生成大量数据，然后分别用不同的排序方法排序，统计每种方法的运行时间，画出曲线图以观察各算法的时间复杂度的实际差异是否符合理论差异。还可以通过不断增加数据量，画出曲线图以观察一种算法的运行时间随数据量的变化是否符合该算法的时间复杂度。另外，对于前面提到的用类定义包含多个键值的对象，再选定主键对对象进行排序的问题，也可以作为课后扩展作业。如果讲授过图形界面制作的相关知识，还可以让学生设计一个简单的排序系统，模拟购物场景中按多种标准对商品进行排序。
六、总结
本文以“选择排序”算法为例，探讨了在《程序设计》和《数据结构》两门课程中排序这一重难点的教学策略，介绍了在教学过程中从概念引入、算法讲解、案例分析到课后实践等各环节的教学方法和教学设计问题。本文希望通过这种授课方式提高重要知识点的教学效果，提高学生的理解和应用能力，进而提升课程的整体教学质量，为相关课程建设做出理论铺垫和实践探索。
