面向計算思維培養的選擇排序算法可視化實現

摘要：計算性思維被視為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