数据结构排序算法学习意义感的建立

2022-08-12余艳邢远秀刘云冰

高师理科学刊 2022年7期

余艳，邢远秀，刘云冰

（武汉科技大学理学院，湖北武汉 430065）

几乎所有的数据结构类教材都将“排序”设为独立的一章，其重要性不言而喻.数据结构课程在“排序”这一章涵盖的内容通常包括：直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、锦标赛排序、堆排序、归并排序和基数排序[1-2].但在教学过程中，发现学生面对这一章学习内容时却有些不屑之情：“用Python 的一个sort()就可以解决的问题，为何要花这么多时间去学习”.作为教师倘若没有帮助学生解此疑惑，怕是难以调动起他们的学习热情，更不要提其他更宏伟的教学目标了.当学生心中有所思而不能通时，正是教师给予教学的最适宜和最关键时刻[3].

1 建立学习意义感的必要性

哲学家赫舍尔说，“人之为人的独特难题就是如何进入意义”[4].当学生在学习过程中缺乏学习意义感，则会出现“学习奴隶化”现象[5]：对学习内容不感兴趣，缺乏主动思考，学习过程沦为被动接受教师的安排.这种情况下，无论采取何种教学方式，呈现何种教学内容，教学都将只是一个灌输符号的过程[6].

因此，有必要在教学过程中带领学生建立起学习的意义感，让学生对学习活动产生自我认同，并在学习过程中获得价值体验.由此激发学生的求知欲望和思考能力，产生强烈的学习参与意识，从而实现真正意义上的教与学.本文以数据结构课程中“排序”这一章的教学为例，以改变学生初学“排序”时所持的学习态度为目标，探讨引导学生对学习内容产生正确认知并建立学习意义感的方法.

2 建立学习意义感的方法

2.1 分析学习现状，建立学习信心

排序算法虽然种类很多，但代码都不长，同时具有一定的难度和实现细节的要求，适合程序设计的初学者进阶学习.学生在数据结构正式学习之前，通常学习了计算机基础和C 语言程序设计，所积累的程序设计经验并不多，依然是程序设计的初学者.排序算法这种“踮踮脚”就可以够得到的问题，不会因为问题的复杂度而影响学习者的信心，同时排序算法内在的细节要求也可以打磨学习者的思维能力和编程能力，安排在这个阶段进行学习符合认知规律的要求.

2.2 明确学习目标的多样性，产生认同感

排序算法的学习目标并不仅局限于排序算法策略的学习，时间复杂度、空间复杂度的分析方法也是数据结构学习过程中需要重点打磨的基本功之一.作为一名专业的程序开发者，只有具备了时间空间复杂度的观念、分析方法和权衡方法，才有能力在工程实践中为具体的应用问题选择合适的、正确的算法.

在排序算法的学习过程中，学生将进一步学习时间复杂度、空间复杂度分析和计算的方法，并用于比较和评价各种排序算法在各种场景下的性能.如果把时间空间复杂度的分析看作是编程的一件工具，那么使用这件工具可以帮助学生理解各种排序算法的特性和适用场合；从另一个角度来看，“排序”这一章也为学生提供了学习这种工具使用方法的应用背景.排序算法时间复杂度的对比分析见表1（其中基数排序中的d 表示元素的位数）.

表1 排序算法的对比分析

2.3 了解岗位需求，激发学习动力

真正学懂计算机的人既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题.而这种思维和手段的最佳演绎就是“算法”[7].许多大型软件企业技术岗位的面试都很重视对数据结构与算法的考察，且注重能否迅速将解题思路转换为代码的能力，其中排序算法就是经常被考察的问题之一.有程序员在博客中提到自己的面试经历：“很多公司的面试，如百度、腾讯、阿里都问到了堆排序，虽然问的形式不一样，但都是堆排序的相关知识”[8].其他面试经历，例如：“请说出各种排序算法的稳定性”[9].“知道哪些排序算法，选一个自己熟悉的排序算法，讲下它的主要特点，如时间复杂度、稳定性.一般会把重点放在快速排序和堆排序，进一步要求手写实现.讨论下在输入是特定序列的情况下，当前的算法有什么缺点或优点”[10].

可见，软件企业对排序算法的考察涉及到对排序算法策略的理解、代码实现、算法稳定性的分析以及算法时间复杂度的分析等，这些知识点恰好与数据结构的教学内容相吻合.由此可见，要为自己的专业面试加分，就需要在数据结构学习过程中深入理解各种排序算法的原理和特性，并在实验环节认真完成上机任务，积累编写代码的技巧和经验.

2.4 审视算法背后的逻辑，实现正确认知

数据结构教程中经典排序算法种类繁多，在赞叹每种算法精妙绝伦的思想之余，不能忽视每种排序算法的背后还蕴含着不同的知识点和底层逻辑.通过学习不同的算法策略，可以收获不同角度的思维训练和编程技巧.带领学生理解算法背后的逻辑，从而使他们对排序算法的学习拥有更全面的认识，从而获取学习意义感.

2.4.1 学习排序算法可以启迪发散性思维 “直接插入排序”的想法与手起扑克牌的过程如出一辙.通过不断地将一张新牌插入到现有的有序序列中，使得有序序列长度每次增一，最终使得手里起到的所有牌排列有序.这种排序算法的构思来源于日常生活，是人类最直观的一种排序思维.这个例子也启发我们，在求解各类问题时可以从日常生活甚至是大自然现象中寻求更一般的规律，从而获得灵感.在智能计算领域有很多类似的例子，如粒子群算法，就是通过模拟鸟群觅食行为而发展起来的一种随机搜索优化算法.

2.4.2 学习排序算法可以收获普适性的编程思想递归形式的“快速排序”和“归并排序”都采用了“分而治之”的编程思想.快速排序的“分”对应“一次划分”的操作，“治”对应枢轴前后2个子序列分别进行快速排序的操作.归并排序将原始序列分割成2个子序列，分别对2个子序列进行归并排序，再把2个有序的子序列归并成1个有序的子序列.这2 种排序算法的共性，都是将原始问题分解为规模更小但性质相同的子问题.这种情况下可以用“分而治之”的思想去解决问题，用代码实现上述思想就是递归程序.可以这么说，“快速排序”和“归并排序”为“分而治之”提供了应用场景；反之，通过对“快速排序”和“归并排序”的学习，又可以加深对“分而治之”的理解，更好地掌握递归程序编写的方法和实现细节.

2.4.3 学习排序算法可以强化对数据结构的理解 “堆排序”利用了“堆”的数据结构，它是一种特殊的完全二叉树.大顶堆上任意结点上的值都不小于左右孩子结点的值，小顶堆上任意结点上的值都不大于左右孩子结点的值.堆排序的整个过程就是利用了堆的这种逻辑特性，当对序列按正序排序（元素由小到大），则需要使用大顶堆.创建大顶堆后，最大的元素一定在堆顶，将其与最后一个元素交换，最大的元素就落到了正确的位置，排序过程可以不再考虑它，称其为“出堆”.对于剩余的元素，除了堆顶元素不满足堆的要求，其左右子树依然是堆.此时，从堆顶向下进行调整，称为“筛选”操作，可以将其重新调整为一个“大顶堆”，堆顶元素即为整个序列的次大元，将其与整个序列的倒数第2 个元素交换，次大元落到正确的位置，次大元即可出堆.这个过程重复执行，即可实现整个序列的排序.

如果没有“堆排序”的应用背景，直接生硬地讨论“堆”的逻辑结构、存储结构及其上的“插入”、“删除”操作，学生必然会觉得枯燥和无味.在“堆排序”的学习过程中，才可以深刻体会到“堆”这种数据结构设计上的巧妙性和存在的必要性，从而加深对“数据结构”这种抽象概念的理解.

2.4.4 学习排序算法可以延伸学习的深度借助排序算法的教学内容，可以引导学生进行教材以外的深度思考，如思考算法的改进策略并进行研究性的实验探索.如教材中快速排序枢轴元素的选取原则很简单：固定选择第1 个元素作为枢轴.通过分析快速排序的时间复杂度可知，若一次划分后枢轴两侧子序列长度相差很大，即枢轴位置落在最左边或最右边，算法的时间效率就会退化到O（n2）.为提高算法时间效率，可考虑使用三者取中（从序列的首元素、中间位置的元素、尾元素中选取中位数作为枢轴）或五者取中法避免极端情况的发生，并通过实验来测试不同枢轴选取方法对快速排序算法时间效率的影响.

除此之外，还可以引导学生从递归的角度思考快速排序的改进策略.原始快速排序算法的递归操作会执行到序列长度为1 的情况，通过提前结束递归来提升算法时间效率：当待排子序列长度小于某个阈值时，则终止递归调用，并采用直接插入排序算法.阈值设定对算法时间效率的影响也可以通过实验来测试.另外，还可以将这2 种改进策略进行组合，并通过实验来测试改进算法在不同排列性质的数据集上的性能.这些研究性的实验过程可以由学生自己来设计，实验的完成可以促进学生获得学习的价值感.

引导学生探究工业界软件采用的排序算法，也可以增强学生对排序算法的学习价值感.如引导学生调研Matlab 软件内置排序函数的实现方法，会发现它是几种快速算法的智能混合版本，从而体会到排序算法在工业实践中的真实应用模式.