面向计算思维培养的选择排序算法可视化实现

摘要：计算性思维被视为21世纪每个人必备的核心技能之一。计算思维的培养已经成为国内外教育界的热门话题。为了辅助“数据结构与算法”课程教学，培养学生计算思维，文章基于RAPTOR设计并实现选择排序算法可视化，动态演示了算法执行过程，可以帮助学生直观理解算法精髓，提高教学效果。该研究可以为其他算法可视化实现提供新思路，也可以充当学生实践案例，旨在最大化降低语法要求的前提下，协助学生实现排序算法可视化。

关键词：排序算法；选择排序；计算思维；可视化；RAPTOR

中图分类号：TP311.1""文献标志码：A

0"引言

知名瑞士科学家、PASCAL语言之父沃思（N. Wirth）教授曾提出一个著名等式：程序=算法+数据结构^［1］。理解并掌握算法与数据结构的过程，实质上也是培养计算思维与问题解决能力的过程。通过掌握各种算法思想和数据结构的特性，程序员可以更加灵活地设计程序、优化代码结构并解决实际问题。这种思维能力不仅对于初学者来说至关重要，也是资深程序员不断提升自我、追求卓越的重要素质。

在“数据结构与算法”课程中，排序是教学重点之一，也是计算机程序设计领域的一项基础操作。采用传统教学手段，教师难以全面展现排序算法的抽象性及动态执行流程，要达到理想的教学效果颇具挑战。算法可视化技术，通过将抽象的数据和操作转化为动态的图像演示，使得学习者能够快速理解算法与编程代码之间的内在联系。

RAPTOR是一种基于流程图的可视化算法工具^［2-3］，它允许用户通过拖放操作，将流程图符号相互连接，以此构建算法程序。所生成的流程图不仅能在其内置环境中直接进行调试和运行，还能直观地指示出程序流程当前执行的位置，展示所有变量的变化情况，为初学者提供了一种注重思维、降低语法学习负担的编程途径。本文采用RAPTOR工具实现了选择排序算法的可视化，旨在帮助学生直观理解算法的工作原理，进而提升其计算思维能力。

1"总体设计

基于Raptor的排序算法教学演示系统，使用条形图模拟数据的相对大小和移动过程，可以实现代码、算法、运行环境以及数据结构的可视化。为了方便观察和简化程序，本文只需要模拟整数1到N排序的过程。主程序首先调用随机序列生成模块生成一个由自然数1到N组成的随机序列，输出到raw.csv文件；然后调用视窗初始化模块把原始数据以条形图的形式在窗体显示；接下来调用排序模块对原始数据进行排序，每执行一个步骤就刷新一次条形图。整个排序过程将在窗体动态演示，在比较、交换、循环结束等关键节点播放不同的音效，同时改变相关数据条的颜色。原始数据也可以直接从raw.csv文件读取。排序算法可视化主程序的流程如图1所示。

2"排序算法可视化实现

2.1"随机序列生成模块

主程序定义长度N为40的一维数组A，用于存放待处理数据；然后运行Init_Array随机序列生成模块，生成一个1至N的随机全排列，保存在数组A中。所谓全排列，就是将这N个整数按照一定的顺序排列，总共有N！种排列方法。随机序列生成模块首先使用Random获取［0，1）区间的随机小数，然后使用floor（Random*N）+1获取1到N之间的随机整数test。为了避免数组A中的元素重复，随机序列生成模块定义另外一个数组used，使用used［i］表示数字i是否已经出现过。used数组元素初始化为False。随机序列生成模块每轮循环生成一个随机整数test，如果used［test］等于False，说明test与数组A已有元素均不重复，就可以把test保存到数组A中，把used［test］设置为True；如果used［test］等于True，说明test已经是数组A的元素，就重新生成新的随机整数，直到出现未使用过的数为止^［4］。Init_Array子程序的流程如图2所示，注意Raptor中数组下标是以1开始的。

2.2"文件输入输出模块

1到N这N个整数的随机序列生成完毕以后，保存在数组A中。主程序调用文件输出模块Out_File把数组A输出到文件raw.csv中。csv文件可以用Excel打开查看。Out_File子程序的流程如图3所示，使用数组长度N控制循环，PUT输出语句每轮循环向文件写入一个数组元素并且换行。RAPTOR程序在执行过程中遇到PUT输出语句，系统会检查输出是否已经被重定向。如果输出被Redirect_Output重定向语句指定输出文件，系统会将输出数据写入指定文件；如果没有重定向，输出数据将直接显示在主控制台^［4］。因此，输出数据之前，Out_File子程序先执行Redirect_Output（file）输出重定向语句；文件输出完成以后，Out_File子程序需要调用Redirect_Output（False）输出重定向结束语句，关闭输出文件，使后续输出内容继续写到主控制台。

主程序设置Input_Mode变量，用于选择排序前原始数据的输入方式，如图1所示。如果Input_Mode等于0，则主程序调用Init_Array子程序重新生成一个随机的全排列，输出到文件raw.csv中；如果Input_Mode不等于0，则主程序调用In_File子程序，从raw.csv读入原始数据，保存到数组A中。文件输入模块In_File在输入数据之前，先执行Redirect_Input（file）输入重定向语句；文件输入完成以后，需要调用Redirect_Input（False）输入重定向结束语句^［4］。文件输入模块使用文件长度和读入指针控制输入循环^［4］，每轮循环使用GET输入语句从文件读入一个数组元素。文件输入模块的流程如图4所示。

2.3"视窗初始化模块

原始数据保存在数组A以后，主程序调用Visu_Array子程序，初始化图形视窗界面，流程如图5所示。视窗初始化模块Visu_Array首先调用Open_Graph_Window创建图形窗口。然后，调用Clear_Window（White），使用白色覆盖清空整个窗口。接着，调用Draw_Box绘制矩形背景，用黑色描边；调用Display_Text显示标题栏“Selection Sort”。最后，使用数组长度N控制循环，输出深灰色的原始数据条形图。第i个数据条的高度是A［i］×10，与数组元素A［i］的大小成正比。

需要注意的问题是，动画运行的时候，如果每次执行绘制指令都立即更新视窗，直接在屏幕上切换图像，可能会造成动画不稳和屏幕闪烁^［5］。尤其是复杂的动画，图像切换很频繁，往往需要花费大量的绘制时间。减少图像闪烁的技术^［6］有很多，例如：增量更新、页面切换以及双缓冲等。这些技术手段各自拥有其特定的优势与局限性，适用于不同的应用场景。本文采用双缓冲技术^［6］，使用Freeze_Graph_Window和Update_Graph_Window指令来平滑动画的显示。在绘制或者更新动画之前，Visu_Array子程序调用Freeze_Graph_Window，生成一个可以绘制图形对象的屏幕缓冲区，这个缓冲区被用于所有图形的绘制。也就是说，图形对象不是直接绘制到屏幕上，而是绘制到屏幕缓冲区。在屏幕缓冲区，完成一帧动画的绘制和更新以后，Visu_Array子程序调用Update_Graph_Window就可以立即将缓冲区图像一次性显示到屏幕上，有效避免了直接在屏幕上进行动画消除和刷新处理所带来的屏幕闪烁情况。

2.4"排序算法动态演示及音效模块

选择排序是一种简单直观的排序算法，类似于整理扑克牌，流程如图6所示。选择排序算法使用双重循环，外层循环变量是i，内层循环变量是j。排序过程的动态演示如图7所示，整个数组分为2个子集，左边浅灰色区域是已经排序的子集，右边深灰色区域是未排序的子集。每一轮外层循环从未排序子集A［i］到A［N］中选出最小的元素，放入有序子集A［1］到A［i-1］的后面。这个过程重复进行，每轮循环只需交换一次，直到整个数组都排好序。双层循环执行过程如图7（a）到图7（f）所示。

（1）假设未排序子集的首元素A［i］为当前未排序数据的最小元素，排序模块把A［i］数据条改成白色，再把当前外层循环未排序子集的最小元素下标minIndex赋值为i，如图7（a）所示。

（2）进入内层循环后，循环变量j取值为i+1到N。在每轮内层循环中，排序模块2次调用Visu_Color子程序，使当前元素A［j］所对应的数据条先变成黑色，再变回深灰色。为了便于观察，数据条变黑以后使用Delay_For（0.3）延迟0.3 s，再变回深灰色，如图7（a）（b）所示。排序模块每次改变循环变量j的值，都会调用Play_Sound_Background播放元素大小比较的音效compare.wav。

（3）在内层循环中，排序模块逐个比较A［j］与A［minIndex］，如果发现当前元素A［j］小于原有最小值A［minIndex］，排序模块就调用Visu_Min子程序，把A［minIndex］变回深灰色，A［j］数据条改成白色。为了便于观察，每个动画结束后都延迟0.3s。排序模块把minIndex赋值为新最小元素的下标j，播放最小值音效min.wav，如图7（a）（b）所示。

（4）当j等于N+1，未排列子集的遍历已经完成，内层循环结束，A［minIndex］为整个未排序子集的最小元素，如图7（c）所示。排序模块判断未排序子集首元素A［i］与最小元素A［minIndex］是否位置相同，如果i不等于minIndex，说明两者位置不同。排序模块调用Visu_Color子程序使数据条A［i］和A［minIndex］均为白色，如图7（d）所示。此时，排序模块交换A［i］与A［minIndex］，让本轮外层循环的最小未排序元素紧跟在有序子集（浅灰色区域）的后面，播放交换音效swap.wav，如图7（e）所示。外层循环结束时，排序模块调用Visu_Color子程序把数据条A［i］改成浅灰色，播放结束一轮外层循环的音效Loop.wav，如图7（f）所示。

（5）排序模块把i+1赋值给i，继续进行下一轮外层循环，重复步骤（1）到（4），直到i等于N，排序结束。排序模块调用Visu_Color，让末位数据条A［N］变成浅灰色。

子程序Visu_Color、Visu_Min，Visu_Swap用于动态演示过程中数据条的着色和变色效果。其中，子程序Visu_Swap（i，minIndex，Array）用于数据条A［i］与A［minIndex］交换位置。子程序Visu_Swap首先覆盖绘图区域背景色，用来擦除2个数据条；然后绘制交换后的数据条，涂成白色，如图7（d）（e）所示。延迟0.3s以后，数据条A［i］与A［minIndex］变回深灰色。子程序Visu_Color（i，A，color）由于改变数据条A［i］的颜色。子程序Visu_Min（j，minIndex，A）是在内层循环发现新最小值时，把原有最小数据条A［minIndex］变回深灰色，新最小数据条A［j］改成白色。

3"结语

本文依托RAPTOR工具，实现了选择排序算法的可视化，动态地演示了该算法的执行流程，将原本在学习过程中难以直观呈现的思维结构与方法，借助动画等手段予以显性化展现，实质上是一个将隐性思维显性化的过程，有助于提升教学质量。本项目同样可作为一个实践案例。学生利用RAPTOR算法工具，无须分心于复杂的语法规则，就能够专注于算法设计，学生可以直接构建流程图并获取运行结果，真正实现强化与锻炼计算思维的目标。

参考文献

［1］沃思 N.算法+数据结构=程序［M］.曹德和，刘椿年，译.北京：科学出版社，1984.

［2］程向前，周梦远.基于RAPTOR的可视化计算案例教程［M］.北京：清华大学出版社，2014.

［3］边晶，冯萍.基于流程图的可视化算法工具RAPTOR在计算思维培养中的应用实践［J］.吉林广播电视大学学报，2021（3）：154-157.

［4］谢涛，程向前，杨金成.RAPTOR程序设计案例教程［M］.北京：清华大学出版社，2014.

［5］刘卫光，夏敏捷.从Java到Android游戏编程开发［M］.北京：清华大学出版社，2021.

［6］江建国，温少营，张瑞楠.基于双缓冲技术的GDI+无闪烁绘图［J］.计算机应用，2012（增刊2）：136-139.

（编辑"王永超）

Visual implementation of selection sorting algorithm for computational thinking cultivation

ZHANG "Yueyin

（School of Software， Guangdong Food and Drug Vocational College， Guangzhou 510520， China）

Abstract： "Computational thinking is regarded as one of the core skills necessary for everyone in the 21st century. Cultivating computational thinking has become a hot topic in educational circles at home and abroad. To assist the teaching of “Data Structure and Algorithm” and develop students’ computational thinking， this paper designs and implements the visualization for the selection sorting algorithm based on RAPTOR， and dynamically demonstrates the algorithm execution process， which can help students intuitively understand the essence of the algorithm， and improve the teaching effect. This research can provide new ideas for other algorithm visualization implementations. It can also serve as a practical case for students， aiming to assist them in visualizing sorting algorithms while minimizing the syntax requirements.

Key words： sorting algorithm; selection sorting; computational thinking; visualization; RAPTOR