面向計(jì)算思維培養(yǎng)的選擇排序算法可視化實(shí)現(xiàn)

摘要：計(jì)算性思維被視為21世紀(jì)每個(gè)人必備的核心技能之一。計(jì)算思維的培養(yǎng)已經(jīng)成為國內(nèi)外教育界的熱門話題。為了輔助“數(shù)據(jù)結(jié)構(gòu)與算法”課程教學(xué)，培養(yǎng)學(xué)生計(jì)算思維，文章基于RAPTOR設(shè)計(jì)并實(shí)現(xiàn)選擇排序算法可視化，動(dòng)態(tài)演示了算法執(zhí)行過程，可以幫助學(xué)生直觀理解算法精髓，提高教學(xué)效果。該研究可以為其他算法可視化實(shí)現(xiàn)提供新思路，也可以充當(dāng)學(xué)生實(shí)踐案例，旨在最大化降低語法要求的前提下，協(xié)助學(xué)生實(shí)現(xiàn)排序算法可視化。

關(guān)鍵詞：排序算法；選擇排序；計(jì)算思維；可視化；RAPTOR

中圖分類號(hào)：TP311.1""文獻(xiàn)標(biāo)志碼：A

0"引言

知名瑞士科學(xué)家、PASCAL語言之父沃思（N. Wirth）教授曾提出一個(gè)著名等式：程序=算法+數(shù)據(jù)結(jié)構(gòu)^［1］。理解并掌握算法與數(shù)據(jù)結(jié)構(gòu)的過程，實(shí)質(zhì)上也是培養(yǎng)計(jì)算思維與問題解決能力的過程。通過掌握各種算法思想和數(shù)據(jù)結(jié)構(gòu)的特性，程序員可以更加靈活地設(shè)計(jì)程序、優(yōu)化代碼結(jié)構(gòu)并解決實(shí)際問題。這種思維能力不僅對(duì)于初學(xué)者來說至關(guān)重要，也是資深程序員不斷提升自我、追求卓越的重要素質(zhì)。

在“數(shù)據(jù)結(jié)構(gòu)與算法”課程中，排序是教學(xué)重點(diǎn)之一，也是計(jì)算機(jī)程序設(shè)計(jì)領(lǐng)域的一項(xiàng)基礎(chǔ)操作。采用傳統(tǒng)教學(xué)手段，教師難以全面展現(xiàn)排序算法的抽象性及動(dòng)態(tài)執(zhí)行流程，要達(dá)到理想的教學(xué)效果頗具挑戰(zhàn)。算法可視化技術(shù)，通過將抽象的數(shù)據(jù)和操作轉(zhuǎn)化為動(dòng)態(tài)的圖像演示，使得學(xué)習(xí)者能夠快速理解算法與編程代碼之間的內(nèi)在聯(lián)系。

RAPTOR是一種基于流程圖的可視化算法工具^［2-3］，它允許用戶通過拖放操作，將流程圖符號(hào)相互連接，以此構(gòu)建算法程序。所生成的流程圖不僅能在其內(nèi)置環(huán)境中直接進(jìn)行調(diào)試和運(yùn)行，還能直觀地指示出程序流程當(dāng)前執(zhí)行的位置，展示所有變量的變化情況，為初學(xué)者提供了一種注重思維、降低語法學(xué)習(xí)負(fù)擔(dān)的編程途徑。本文采用RAPTOR工具實(shí)現(xiàn)了選擇排序算法的可視化，旨在幫助學(xué)生直觀理解算法的工作原理，進(jìn)而提升其計(jì)算思維能力。

1"總體設(shè)計(jì)

基于Raptor的排序算法教學(xué)演示系統(tǒng)，使用條形圖模擬數(shù)據(jù)的相對(duì)大小和移動(dòng)過程，可以實(shí)現(xiàn)代碼、算法、運(yùn)行環(huán)境以及數(shù)據(jù)結(jié)構(gòu)的可視化。為了方便觀察和簡化程序，本文只需要模擬整數(shù)1到N排序的過程。主程序首先調(diào)用隨機(jī)序列生成模塊生成一個(gè)由自然數(shù)1到N組成的隨機(jī)序列，輸出到raw.csv文件；然后調(diào)用視窗初始化模塊把原始數(shù)據(jù)以條形圖的形式在窗體顯示；接下來調(diào)用排序模塊對(duì)原始數(shù)據(jù)進(jìn)行排序，每執(zhí)行一個(gè)步驟就刷新一次條形圖。整個(gè)排序過程將在窗體動(dòng)態(tài)演示，在比較、交換、循環(huán)結(jié)束等關(guān)鍵節(jié)點(diǎn)播放不同的音效，同時(shí)改變相關(guān)數(shù)據(jù)條的顏色。原始數(shù)據(jù)也可以直接從raw.csv文件讀取。排序算法可視化主程序的流程如圖1所示。

2"排序算法可視化實(shí)現(xiàn)

2.1"隨機(jī)序列生成模塊

主程序定義長度N為40的一維數(shù)組A，用于存放待處理數(shù)據(jù)；然后運(yùn)行Init_Array隨機(jī)序列生成模塊，生成一個(gè)1至N的隨機(jī)全排列，保存在數(shù)組A中。所謂全排列，就是將這N個(gè)整數(shù)按照一定的順序排列，總共有N！種排列方法。隨機(jī)序列生成模塊首先使用Random獲?。?，1）區(qū)間的隨機(jī)小數(shù)，然后使用floor（Random*N）+1獲取1到N之間的隨機(jī)整數(shù)test。為了避免數(shù)組A中的元素重復(fù)，隨機(jī)序列生成模塊定義另外一個(gè)數(shù)組used，使用used［i］表示數(shù)字i是否已經(jīng)出現(xiàn)過。used數(shù)組元素初始化為False。隨機(jī)序列生成模塊每輪循環(huán)生成一個(gè)隨機(jī)整數(shù)test，如果used［test］等于False，說明test與數(shù)組A已有元素均不重復(fù)，就可以把test保存到數(shù)組A中，把used［test］設(shè)置為True；如果used［test］等于True，說明test已經(jīng)是數(shù)組A的元素，就重新生成新的隨機(jī)整數(shù)，直到出現(xiàn)未使用過的數(shù)為止^［4］。Init_Array子程序的流程如圖2所示，注意Raptor中數(shù)組下標(biāo)是以1開始的。

2.2"文件輸入輸出模塊

1到N這N個(gè)整數(shù)的隨機(jī)序列生成完畢以后，保存在數(shù)組A中。主程序調(diào)用文件輸出模塊Out_File把數(shù)組A輸出到文件raw.csv中。csv文件可以用Excel打開查看。Out_File子程序的流程如圖3所示，使用數(shù)組長度N控制循環(huán)，PUT輸出語句每輪循環(huán)向文件寫入一個(gè)數(shù)組元素并且換行。RAPTOR程序在執(zhí)行過程中遇到PUT輸出語句，系統(tǒng)會(huì)檢查輸出是否已經(jīng)被重定向。如果輸出被Redirect_Output重定向語句指定輸出文件，系統(tǒng)會(huì)將輸出數(shù)據(jù)寫入指定文件；如果沒有重定向，輸出數(shù)據(jù)將直接顯示在主控制臺(tái)^［4］。因此，輸出數(shù)據(jù)之前，Out_File子程序先執(zhí)行Redirect_Output（file）輸出重定向語句；文件輸出完成以后，Out_File子程序需要調(diào)用Redirect_Output（False）輸出重定向結(jié)束語句，關(guān)閉輸出文件，使后續(xù)輸出內(nèi)容繼續(xù)寫到主控制臺(tái)。

主程序設(shè)置Input_Mode變量，用于選擇排序前原始數(shù)據(jù)的輸入方式，如圖1所示。如果Input_Mode等于0，則主程序調(diào)用Init_Array子程序重新生成一個(gè)隨機(jī)的全排列，輸出到文件raw.csv中；如果Input_Mode不等于0，則主程序調(diào)用In_File子程序，從raw.csv讀入原始數(shù)據(jù)，保存到數(shù)組A中。文件輸入模塊In_File在輸入數(shù)據(jù)之前，先執(zhí)行Redirect_Input（file）輸入重定向語句；文件輸入完成以后，需要調(diào)用Redirect_Input（False）輸入重定向結(jié)束語句^［4］。文件輸入模塊使用文件長度和讀入指針控制輸入循環(huán)^［4］，每輪循環(huán)使用GET輸入語句從文件讀入一個(gè)數(shù)組元素。文件輸入模塊的流程如圖4所示。

2.3"視窗初始化模塊

原始數(shù)據(jù)保存在數(shù)組A以后，主程序調(diào)用Visu_Array子程序，初始化圖形視窗界面，流程如圖5所示。視窗初始化模塊Visu_Array首先調(diào)用Open_Graph_Window創(chuàng)建圖形窗口。然后，調(diào)用Clear_Window（White），使用白色覆蓋清空整個(gè)窗口。接著，調(diào)用Draw_Box繪制矩形背景，用黑色描邊；調(diào)用Display_Text顯示標(biāo)題欄“Selection Sort”。最后，使用數(shù)組長度N控制循環(huán)，輸出深灰色的原始數(shù)據(jù)條形圖。第i個(gè)數(shù)據(jù)條的高度是A［i］×10，與數(shù)組元素A［i］的大小成正比。

需要注意的問題是，動(dòng)畫運(yùn)行的時(shí)候，如果每次執(zhí)行繪制指令都立即更新視窗，直接在屏幕上切換圖像，可能會(huì)造成動(dòng)畫不穩(wěn)和屏幕閃爍^［5］。尤其是復(fù)雜的動(dòng)畫，圖像切換很頻繁，往往需要花費(fèi)大量的繪制時(shí)間。減少圖像閃爍的技術(shù)^［6］有很多，例如：增量更新、頁面切換以及雙緩沖等。這些技術(shù)手段各自擁有其特定的優(yōu)勢與局限性，適用于不同的應(yīng)用場景。本文采用雙緩沖技術(shù)^［6］，使用Freeze_Graph_Window和Update_Graph_Window指令來平滑動(dòng)畫的顯示。在繪制或者更新動(dòng)畫之前，Visu_Array子程序調(diào)用Freeze_Graph_Window，生成一個(gè)可以繪制圖形對(duì)象的屏幕緩沖區(qū)，這個(gè)緩沖區(qū)被用于所有圖形的繪制。也就是說，圖形對(duì)象不是直接繪制到屏幕上，而是繪制到屏幕緩沖區(qū)。在屏幕緩沖區(qū)，完成一幀動(dòng)畫的繪制和更新以后，Visu_Array子程序調(diào)用Update_Graph_Window就可以立即將緩沖區(qū)圖像一次性顯示到屏幕上，有效避免了直接在屏幕上進(jìn)行動(dòng)畫消除和刷新處理所帶來的屏幕閃爍情況。

2.4"排序算法動(dòng)態(tài)演示及音效模塊

選擇排序是一種簡單直觀的排序算法，類似于整理撲克牌，流程如圖6所示。選擇排序算法使用雙重循環(huán)，外層循環(huán)變量是i，內(nèi)層循環(huán)變量是j。排序過程的動(dòng)態(tài)演示如圖7所示，整個(gè)數(shù)組分為2個(gè)子集，左邊淺灰色區(qū)域是已經(jīng)排序的子集，右邊深灰色區(qū)域是未排序的子集。每一輪外層循環(huán)從未排序子集A［i］到A［N］中選出最小的元素，放入有序子集A［1］到A［i-1］的后面。這個(gè)過程重復(fù)進(jìn)行，每輪循環(huán)只需交換一次，直到整個(gè)數(shù)組都排好序。雙層循環(huán)執(zhí)行過程如圖7（a）到圖7（f）所示。

（1）假設(shè)未排序子集的首元素A［i］為當(dāng)前未排序數(shù)據(jù)的最小元素，排序模塊把A［i］數(shù)據(jù)條改成白色，再把當(dāng)前外層循環(huán)未排序子集的最小元素下標(biāo)minIndex賦值為i，如圖7（a）所示。

（2）進(jìn)入內(nèi)層循環(huán)后，循環(huán)變量j取值為i+1到N。在每輪內(nèi)層循環(huán)中，排序模塊2次調(diào)用Visu_Color子程序，使當(dāng)前元素A［j］所對(duì)應(yīng)的數(shù)據(jù)條先變成黑色，再變回深灰色。為了便于觀察，數(shù)據(jù)條變黑以后使用Delay_For（0.3）延遲0.3 s，再變回深灰色，如圖7（a）（b）所示。排序模塊每次改變循環(huán)變量j的值，都會(huì)調(diào)用Play_Sound_Background播放元素大小比較的音效compare.wav。

（3）在內(nèi)層循環(huán)中，排序模塊逐個(gè)比較A［j］與A［minIndex］，如果發(fā)現(xiàn)當(dāng)前元素A［j］小于原有最小值A(chǔ)［minIndex］，排序模塊就調(diào)用Visu_Min子程序，把A［minIndex］變回深灰色，A［j］數(shù)據(jù)條改成白色。為了便于觀察，每個(gè)動(dòng)畫結(jié)束后都延遲0.3s。排序模塊把minIndex賦值為新最小元素的下標(biāo)j，播放最小值音效min.wav，如圖7（a）（b）所示。

（4）當(dāng)j等于N+1，未排列子集的遍歷已經(jīng)完成，內(nèi)層循環(huán)結(jié)束，A［minIndex］為整個(gè)未排序子集的最小元素，如圖7（c）所示。排序模塊判斷未排序子集首元素A［i］與最小元素A［minIndex］是否位置相同，如果i不等于minIndex，說明兩者位置不同。排序模塊調(diào)用Visu_Color子程序使數(shù)據(jù)條A［i］和A［minIndex］均為白色，如圖7（d）所示。此時(shí)，排序模塊交換A［i］與A［minIndex］，讓本輪外層循環(huán)的最小未排序元素緊跟在有序子集（淺灰色區(qū)域）的后面，播放交換音效swap.wav，如圖7（e）所示。外層循環(huán)結(jié)束時(shí)，排序模塊調(diào)用Visu_Color子程序把數(shù)據(jù)條A［i］改成淺灰色，播放結(jié)束一輪外層循環(huán)的音效Loop.wav，如圖7（f）所示。

（5）排序模塊把i+1賦值給i，繼續(xù)進(jìn)行下一輪外層循環(huán)，重復(fù)步驟（1）到（4），直到i等于N，排序結(jié)束。排序模塊調(diào)用Visu_Color，讓末位數(shù)據(jù)條A［N］變成淺灰色。

子程序Visu_Color、Visu_Min，Visu_Swap用于動(dòng)態(tài)演示過程中數(shù)據(jù)條的著色和變色效果。其中，子程序Visu_Swap（i，minIndex，Array）用于數(shù)據(jù)條A［i］與A［minIndex］交換位置。子程序Visu_Swap首先覆蓋繪圖區(qū)域背景色，用來擦除2個(gè)數(shù)據(jù)條；然后繪制交換后的數(shù)據(jù)條，涂成白色，如圖7（d）（e）所示。延遲0.3s以后，數(shù)據(jù)條A［i］與A［minIndex］變回深灰色。子程序Visu_Color（i，A，color）由于改變數(shù)據(jù)條A［i］的顏色。子程序Visu_Min（j，minIndex，A）是在內(nèi)層循環(huán)發(fā)現(xiàn)新最小值時(shí)，把原有最小數(shù)據(jù)條A［minIndex］變回深灰色，新最小數(shù)據(jù)條A［j］改成白色。

3"結(jié)語

本文依托RAPTOR工具，實(shí)現(xiàn)了選擇排序算法的可視化，動(dòng)態(tài)地演示了該算法的執(zhí)行流程，將原本在學(xué)習(xí)過程中難以直觀呈現(xiàn)的思維結(jié)構(gòu)與方法，借助動(dòng)畫等手段予以顯性化展現(xiàn)，實(shí)質(zhì)上是一個(gè)將隱性思維顯性化的過程，有助于提升教學(xué)質(zhì)量。本項(xiàng)目同樣可作為一個(gè)實(shí)踐案例。學(xué)生利用RAPTOR算法工具，無須分心于復(fù)雜的語法規(guī)則，就能夠?qū)Ｗ⒂谒惴ㄔO(shè)計(jì)，學(xué)生可以直接構(gòu)建流程圖并獲取運(yùn)行結(jié)果，真正實(shí)現(xiàn)強(qiáng)化與鍛煉計(jì)算思維的目標(biāo)。

參考文獻(xiàn)

［1］沃思 N.算法+數(shù)據(jù)結(jié)構(gòu)=程序［M］.曹德和，劉椿年，譯.北京：科學(xué)出版社，1984.

［2］程向前，周夢遠(yuǎn).基于RAPTOR的可視化計(jì)算案例教程［M］.北京：清華大學(xué)出版社，2014.

［3］邊晶，馮萍.基于流程圖的可視化算法工具RAPTOR在計(jì)算思維培養(yǎng)中的應(yīng)用實(shí)踐［J］.吉林廣播電視大學(xué)學(xué)報(bào)，2021（3）：154-157.

［4］謝濤，程向前，楊金成.RAPTOR程序設(shè)計(jì)案例教程［M］.北京：清華大學(xué)出版社，2014.

［5］劉衛(wèi)光，夏敏捷.從Java到Android游戲編程開發(fā)［M］.北京：清華大學(xué)出版社，2021.

［6］江建國，溫少營，張瑞楠.基于雙緩沖技術(shù)的GDI+無閃爍繪圖［J］.計(jì)算機(jī)應(yīng)用，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