论文部分内容阅读
摘要：作者针对数据结构与算法课程理论复杂和概念抽象的特点，以Visual Basic 6.0为开发环境，设计实现了常用经典排序算法的二维动态可视化演示软件。教学实践证明，直观生动的动态排序过程演示，有利于学生更好地理解和掌握各排序算法的基本思想，锻炼学生算法的理解、设计和实现的能力，从而有效地提高教与学效率。
关键词：数据结构;排序算法;动态演示;算法可视化
中图分类号：G434 文献标识码：A 论文编号：1674-2117（2021）22-0072-04
排序算法是数据结构与算法中最基本的算法之一，是信息检索和数据处理的基础。排序算法分类繁多，过程抽象，学生理解起来较为困难。算法可视化通过对具体算法流程进行高度抽象，将计算过程用动画的形式展现出来，使算法执行过程形象可见，从而降低算法的理解难度，对学生来说具有重要的意义。它以算法思想、流程为主要内容，通过让学生自由控制算法动画的播放速度、流程，以及所演示算法的数据，使学生更容易掌握算法的基本思想，熟悉算法流程。[1-2]
本文借助Visual Basic 6.0开发环境设计并实现了算法演示的可视化动态演示软件，师生可自行设置数据规模及大小范围，适时调整控制排序速度，直观形象地感知各排序算法的具体执行过程，更好地理解和掌握算法的精髓，从而达到辅助教学，提高教学效率的目的。
● 排序算法
排序，就是为了使一组数或一串记录，通过编辑与操作，使它从无序到有序。一个经过优化的简捷的算法可以节省大量的时间和空间资源，即不同的算法有不同的时间复杂度和空间复杂度。排序算法主要分为内部排序和外部排序，通常所说的排序算法指的是内部排序算法，即数据记录在内存中进行排序。内部排序算法大体可分为两种：一种是比较排序，时间复杂度为O（nlogn）～O（n2），如冒泡排序、选择排序、插入排序、归并排序、堆排序、快速排序等;另一種是非比较排序，时间复杂度可以达到O（n），如计数排序、基数排序、桶排序等。
本软件主要设计并实现了比较排序中的三种经典排序算法（选择排序、插入排序、冒泡排序）的动态排序演示过程。这三种排序算法也是初学者需要掌握的最基本的算法，它们之间既有区别也有联系：三者都是将序列分成两部分——已排序序列和乱序序列;在选择排序和插入排序中，已排序序列在前面，乱序序列在后面;在冒泡排序中，已排序序列在后面，乱序序列在前面;每次均从乱序序列中选择一个合适的数，放到已排序序列合适的位置，直到乱序序列中没有数据，完成整个排序过程。
该软件旨在让学生形象直观地感知各排序算法的执行过程，掌握各算法的基本思想及其区别与联系，了解比较次数与算法时间复杂度之间的关系以及算法稳定性方面的知识，为学生后续学习其他排序算法、设计并编写程序代码打下坚实的基础。
● 动态演示软件的界面与功能设计
本软件用户界面设计简单友好，操作清晰明了，主要实现了排序算法动态演示处理，如上页图1所示。其功能结构主要分为用户参数设置模块、随机数据生成模块、排序算法演示模块和数据输出模块。用户参数设置模块可以让用户设置初始数据序列的数据个数以及数据的大小范围，选择排序算法的类型，还可以设定排序速度。随机数据生成模块可以根据用户参数设置生成初始随机数列，并且自适应生成一系列与各数据大小相对应高度的条形图，将数据大小与随机状态可视化地显示出来。排序算法演示模块能够根据用户选择的排序算法对数据进行排序，动态显示整个排序过程。数据输出模块主要记录两个方面的内容：其一，记录排序趟数以及数据比较的次数，为算法时间复杂度的学习提供准确的数据支持;其二，排序过程中对相同大小的数据元素标记初始位置序号，为了解算法稳定性提供直观的数据支持。
● 动态演示软件的设计与实现
1.数据大小的可视化显示
用系列条形图直观表示数据序列，用高度表示其数据大小。特别地，条形图的显示具有自适应性，即能够根据用户设置的数据范围自适应调整高度，能够根据用户设置的数据个数自适应调整条形图的宽度，如图2所示。
2.数据状态的可视化显示
用条形图的颜色表示该数据的状态：淡蓝色表示待排的无序数据;绿色表示当前正在进行比较的数据;红色表示当前查找到的一些特征数据（选择排序和插入排序）;橙黄色表示已排的有序数据，如下页图3所示。
3.排序算法的动态演示实现
借助VB6.0的timer时间控件来实现排序过程的动态演示。通过触发Timer控件的Timer事件，可以有规律地间隔一定时间执行一次代码;Interval属性可用来设置触发的时间间隔，以此来设置排序速度;Enabled属性决定该控件是否对时间的推移做响应，以此来控制排序过程的开始与停止。因此，各排序算法动态演示过程的不同关键在于timer事件的代码编写，以下为冒泡排序timer事件伪代码（如图4）。
● 排序算法动态演示过程及其对算法学习的帮助
1.透过动态过程演示动画便于理解算法的基本思想
通过动态演示过程，可以直观获取各个算法具体而完整的执行过程，理解算法的基本思想，掌握各算法的区别与联系，为后期算法的设计以及代码实现提供有力的知识基础。
2.便于探究算法的时间复杂度
当数据规模为n时，通过多组数据输出模块记录的比较次数并结合执行过程，可以很容易得出冒泡排序和选择排序的比较次数均为n（n-1）/2，时间复杂度为O（n^2）;插入排序在最好的情况下（初始数据已有序）比较次数为n-1，在最差的情况下（初始数据完全逆序）比较次数为n（n-1）/2，因此平均比较次数约为n^2/4，故时间复杂度也为O（n^2）。
3.便于探究算法的稳定性
排序算法往往还需要考察其算法稳定性。排序算法稳定性可简单定义为：如果Ai=Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。通俗地讲，就是保证排序前后两个相等的数的相对顺序不变。
本软件对于相同的数据，在条形图上方标记该数据在相同数据序列中的原始排位，通过多组实验数据验证了冒泡排序和插入排序是稳定的排序算法，而选择排序是不稳定的排序算法，如下页图5所示。本软件对算法稳定性的探究为学生提供了直观清晰的数据分析。
● 结束语
本软件实现了对冒泡排序、选择排序和插入排序三种基本排序算法的动态排序演示，用户界面简单友好、清楚明了。对于抽象难懂的排序算法，此系统生动形象的动态演示使算法的执行过程一目了然，可以帮助学生更好地掌握排序算法的基本思想，更为直观地了解算法时间复杂度以及算法稳定性方面的知识。当然，排序算法很多，学生可以在此基础上优化改进、分析设计出更加高效的排序算法。同时，此系统可以起到抛砖引玉的作用，鼓励学生为此系统添加新的排序算法演示功能，活学活用，深入理解并实践排序算法，进一步锻炼算法设计与实现能力。
参考文献：
[1]刘斌，徐秀娟，王胜法，等.计算机图形学可视化教学综合实验平台开发[J].实验室科学，2018，21（04）：53-56.
[2]李晓鸿，刘丛，骆嘉伟.基于学习者视角的算法可视化系统研究综述[J].计算机科学，2015，42（11）：431-437.
[3]郭伊.《数据结构》课程教学动态演示系统的设计与实现[D].咸阳：西北农林科技大学，2015：1-56.
郭良敏，孙圳昊，罗永龙，等.“算法设计与分析”中经典算法动态演示软件的设计与实现[J].电脑知识与技术，2016，12（20）：224-225.
作者简介：高向敏（1987—），女，江苏镇江人，南京师范大学硕士研究生，研究方向为计算机图形学。
关键词：数据结构;排序算法;动态演示;算法可视化
中图分类号：G434 文献标识码：A 论文编号：1674-2117（2021）22-0072-04
排序算法是数据结构与算法中最基本的算法之一，是信息检索和数据处理的基础。排序算法分类繁多，过程抽象，学生理解起来较为困难。算法可视化通过对具体算法流程进行高度抽象，将计算过程用动画的形式展现出来，使算法执行过程形象可见，从而降低算法的理解难度，对学生来说具有重要的意义。它以算法思想、流程为主要内容，通过让学生自由控制算法动画的播放速度、流程，以及所演示算法的数据，使学生更容易掌握算法的基本思想，熟悉算法流程。[1-2]
本文借助Visual Basic 6.0开发环境设计并实现了算法演示的可视化动态演示软件，师生可自行设置数据规模及大小范围，适时调整控制排序速度，直观形象地感知各排序算法的具体执行过程，更好地理解和掌握算法的精髓，从而达到辅助教学，提高教学效率的目的。
● 排序算法
排序，就是为了使一组数或一串记录，通过编辑与操作，使它从无序到有序。一个经过优化的简捷的算法可以节省大量的时间和空间资源，即不同的算法有不同的时间复杂度和空间复杂度。排序算法主要分为内部排序和外部排序，通常所说的排序算法指的是内部排序算法，即数据记录在内存中进行排序。内部排序算法大体可分为两种：一种是比较排序，时间复杂度为O（nlogn）～O（n2），如冒泡排序、选择排序、插入排序、归并排序、堆排序、快速排序等;另一種是非比较排序，时间复杂度可以达到O（n），如计数排序、基数排序、桶排序等。
本软件主要设计并实现了比较排序中的三种经典排序算法（选择排序、插入排序、冒泡排序）的动态排序演示过程。这三种排序算法也是初学者需要掌握的最基本的算法，它们之间既有区别也有联系：三者都是将序列分成两部分——已排序序列和乱序序列;在选择排序和插入排序中，已排序序列在前面，乱序序列在后面;在冒泡排序中，已排序序列在后面，乱序序列在前面;每次均从乱序序列中选择一个合适的数，放到已排序序列合适的位置，直到乱序序列中没有数据，完成整个排序过程。
该软件旨在让学生形象直观地感知各排序算法的执行过程，掌握各算法的基本思想及其区别与联系，了解比较次数与算法时间复杂度之间的关系以及算法稳定性方面的知识，为学生后续学习其他排序算法、设计并编写程序代码打下坚实的基础。
● 动态演示软件的界面与功能设计
本软件用户界面设计简单友好，操作清晰明了，主要实现了排序算法动态演示处理，如上页图1所示。其功能结构主要分为用户参数设置模块、随机数据生成模块、排序算法演示模块和数据输出模块。用户参数设置模块可以让用户设置初始数据序列的数据个数以及数据的大小范围，选择排序算法的类型，还可以设定排序速度。随机数据生成模块可以根据用户参数设置生成初始随机数列，并且自适应生成一系列与各数据大小相对应高度的条形图，将数据大小与随机状态可视化地显示出来。排序算法演示模块能够根据用户选择的排序算法对数据进行排序，动态显示整个排序过程。数据输出模块主要记录两个方面的内容：其一，记录排序趟数以及数据比较的次数，为算法时间复杂度的学习提供准确的数据支持;其二，排序过程中对相同大小的数据元素标记初始位置序号，为了解算法稳定性提供直观的数据支持。
● 动态演示软件的设计与实现
1.数据大小的可视化显示
用系列条形图直观表示数据序列，用高度表示其数据大小。特别地，条形图的显示具有自适应性，即能够根据用户设置的数据范围自适应调整高度，能够根据用户设置的数据个数自适应调整条形图的宽度，如图2所示。
2.数据状态的可视化显示
用条形图的颜色表示该数据的状态：淡蓝色表示待排的无序数据;绿色表示当前正在进行比较的数据;红色表示当前查找到的一些特征数据（选择排序和插入排序）;橙黄色表示已排的有序数据，如下页图3所示。
3.排序算法的动态演示实现
借助VB6.0的timer时间控件来实现排序过程的动态演示。通过触发Timer控件的Timer事件，可以有规律地间隔一定时间执行一次代码;Interval属性可用来设置触发的时间间隔，以此来设置排序速度;Enabled属性决定该控件是否对时间的推移做响应，以此来控制排序过程的开始与停止。因此，各排序算法动态演示过程的不同关键在于timer事件的代码编写，以下为冒泡排序timer事件伪代码（如图4）。
● 排序算法动态演示过程及其对算法学习的帮助
1.透过动态过程演示动画便于理解算法的基本思想
通过动态演示过程，可以直观获取各个算法具体而完整的执行过程，理解算法的基本思想，掌握各算法的区别与联系，为后期算法的设计以及代码实现提供有力的知识基础。
2.便于探究算法的时间复杂度
当数据规模为n时，通过多组数据输出模块记录的比较次数并结合执行过程，可以很容易得出冒泡排序和选择排序的比较次数均为n（n-1）/2，时间复杂度为O（n^2）;插入排序在最好的情况下（初始数据已有序）比较次数为n-1，在最差的情况下（初始数据完全逆序）比较次数为n（n-1）/2，因此平均比较次数约为n^2/4，故时间复杂度也为O（n^2）。
3.便于探究算法的稳定性
排序算法往往还需要考察其算法稳定性。排序算法稳定性可简单定义为：如果Ai=Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。通俗地讲，就是保证排序前后两个相等的数的相对顺序不变。
本软件对于相同的数据，在条形图上方标记该数据在相同数据序列中的原始排位，通过多组实验数据验证了冒泡排序和插入排序是稳定的排序算法，而选择排序是不稳定的排序算法，如下页图5所示。本软件对算法稳定性的探究为学生提供了直观清晰的数据分析。
● 结束语
本软件实现了对冒泡排序、选择排序和插入排序三种基本排序算法的动态排序演示，用户界面简单友好、清楚明了。对于抽象难懂的排序算法，此系统生动形象的动态演示使算法的执行过程一目了然，可以帮助学生更好地掌握排序算法的基本思想，更为直观地了解算法时间复杂度以及算法稳定性方面的知识。当然，排序算法很多，学生可以在此基础上优化改进、分析设计出更加高效的排序算法。同时，此系统可以起到抛砖引玉的作用，鼓励学生为此系统添加新的排序算法演示功能，活学活用，深入理解并实践排序算法，进一步锻炼算法设计与实现能力。
参考文献：
[1]刘斌，徐秀娟，王胜法，等.计算机图形学可视化教学综合实验平台开发[J].实验室科学，2018，21（04）：53-56.
[2]李晓鸿，刘丛，骆嘉伟.基于学习者视角的算法可视化系统研究综述[J].计算机科学，2015，42（11）：431-437.
[3]郭伊.《数据结构》课程教学动态演示系统的设计与实现[D].咸阳：西北农林科技大学，2015：1-56.
郭良敏，孙圳昊，罗永龙，等.“算法设计与分析”中经典算法动态演示软件的设计与实现[J].电脑知识与技术，2016，12（20）：224-225.
作者简介：高向敏（1987—），女，江苏镇江人，南京师范大学硕士研究生，研究方向为计算机图形学。