摘要：作者針對數(shù)據(jù)結(jié)構(gòu)與算法課程理論復(fù)雜和概念抽象的特點，以Visual Basic 6.0為開發(fā)環(huán)境，設(shè)計實現(xiàn)了常用經(jīng)典排序算法的二維動態(tài)可視化演示軟件。教學(xué)實踐證明，直觀生動的動態(tài)排序過程演示，有利于學(xué)生更好地理解和掌握各排序算法的基本思想，鍛煉學(xué)生算法的理解、設(shè)計和實現(xiàn)的能力，從而有效地提高教與學(xué)效率。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu);排序算法;動態(tài)演示;算法可視化

中圖分類號：G434? 文獻(xiàn)標(biāo)識碼：A? 論文編號：1674-2117（2021）22-0072-04

排序算法是數(shù)據(jù)結(jié)構(gòu)與算法中最基本的算法之一，是信息檢索和數(shù)據(jù)處理的基礎(chǔ)。排序算法分類繁多，過程抽象，學(xué)生理解起來較為困難。算法可視化通過對具體算法流程進(jìn)行高度抽象，將計算過程用動畫的形式展現(xiàn)出來，使算法執(zhí)行過程形象可見，從而降低算法的理解難度，對學(xué)生來說具有重要的意義。它以算法思想、流程為主要內(nèi)容，通過讓學(xué)生自由控制算法動畫的播放速度、流程，以及所演示算法的數(shù)據(jù)，使學(xué)生更容易掌握算法的基本思想，熟悉算法流程。[1-2]

本文借助Visual Basic 6.0開發(fā)環(huán)境設(shè)計并實現(xiàn)了算法演示的可視化動態(tài)演示軟件，師生可自行設(shè)置數(shù)據(jù)規(guī)模及大小范圍，適時調(diào)整控制排序速度，直觀形象地感知各排序算法的具體執(zhí)行過程，更好地理解和掌握算法的精髓，從而達(dá)到輔助教學(xué)，提高教學(xué)效率的目的。

● 排序算法

排序，就是為了使一組數(shù)或一串記錄，通過編輯與操作，使它從無序到有序。一個經(jīng)過優(yōu)化的簡捷的算法可以節(jié)省大量的時間和空間資源，即不同的算法有不同的時間復(fù)雜度和空間復(fù)雜度。排序算法主要分為內(nèi)部排序和外部排序，通常所說的排序算法指的是內(nèi)部排序算法，即數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序。內(nèi)部排序算法大體可分為兩種：一種是比較排序，時間復(fù)雜度為O（nlogn）～O（n2），如冒泡排序、選擇排序、插入排序、歸并排序、堆排序、快速排序等;另一種是非比較排序，時間復(fù)雜度可以達(dá)到O（n），如計數(shù)排序、基數(shù)排序、桶排序等。

本軟件主要設(shè)計并實現(xiàn)了比較排序中的三種經(jīng)典排序算法（選擇排序、插入排序、冒泡排序）的動態(tài)排序演示過程。這三種排序算法也是初學(xué)者需要掌握的最基本的算法，它們之間既有區(qū)別也有聯(lián)系：三者都是將序列分成兩部分——已排序序列和亂序序列;在選擇排序和插入排序中，已排序序列在前面，亂序序列在后面;在冒泡排序中，已排序序列在后面，亂序序列在前面;每次均從亂序序列中選擇一個合適的數(shù)，放到已排序序列合適的位置，直到亂序序列中沒有數(shù)據(jù)，完成整個排序過程。

該軟件旨在讓學(xué)生形象直觀地感知各排序算法的執(zhí)行過程，掌握各算法的基本思想及其區(qū)別與聯(lián)系，了解比較次數(shù)與算法時間復(fù)雜度之間的關(guān)系以及算法穩(wěn)定性方面的知識，為學(xué)生后續(xù)學(xué)習(xí)其他排序算法、設(shè)計并編寫程序代碼打下堅實的基礎(chǔ)。

● 動態(tài)演示軟件的界面與功能設(shè)計

本軟件用戶界面設(shè)計簡單友好，操作清晰明了，主要實現(xiàn)了排序算法動態(tài)演示處理，如上頁圖1所示。其功能結(jié)構(gòu)主要分為用戶參數(shù)設(shè)置模塊、隨機數(shù)據(jù)生成模塊、排序算法演示模塊和數(shù)據(jù)輸出模塊。用戶參數(shù)設(shè)置模塊可以讓用戶設(shè)置初始數(shù)據(jù)序列的數(shù)據(jù)個數(shù)以及數(shù)據(jù)的大小范圍，選擇排序算法的類型，還可以設(shè)定排序速度。隨機數(shù)據(jù)生成模塊可以根據(jù)用戶參數(shù)設(shè)置生成初始隨機數(shù)列，并且自適應(yīng)生成一系列與各數(shù)據(jù)大小相對應(yīng)高度的條形圖，將數(shù)據(jù)大小與隨機狀態(tài)可視化地顯示出來。排序算法演示模塊能夠根據(jù)用戶選擇的排序算法對數(shù)據(jù)進(jìn)行排序，動態(tài)顯示整個排序過程。數(shù)據(jù)輸出模塊主要記錄兩個方面的內(nèi)容：其一，記錄排序趟數(shù)以及數(shù)據(jù)比較的次數(shù)，為算法時間復(fù)雜度的學(xué)習(xí)提供準(zhǔn)確的數(shù)據(jù)支持;其二，排序過程中對相同大小的數(shù)據(jù)元素標(biāo)記初始位置序號，為了解算法穩(wěn)定性提供直觀的數(shù)據(jù)支持。

● 動態(tài)演示軟件的設(shè)計與實現(xiàn)

1.數(shù)據(jù)大小的可視化顯示

用系列條形圖直觀表示數(shù)據(jù)序列，用高度表示其數(shù)據(jù)大小。特別地，條形圖的顯示具有自適應(yīng)性，即能夠根據(jù)用戶設(shè)置的數(shù)據(jù)范圍自適應(yīng)調(diào)整高度，能夠根據(jù)用戶設(shè)置的數(shù)據(jù)個數(shù)自適應(yīng)調(diào)整條形圖的寬度，如圖2所示。

2.數(shù)據(jù)狀態(tài)的可視化顯示

用條形圖的顏色表示該數(shù)據(jù)的狀態(tài)：淡藍(lán)色表示待排的無序數(shù)據(jù);綠色表示當(dāng)前正在進(jìn)行比較的數(shù)據(jù);紅色表示當(dāng)前查找到的一些特征數(shù)據(jù)（選擇排序和插入排序）;橙黃色表示已排的有序數(shù)據(jù)，如下頁圖3所示。

3.排序算法的動態(tài)演示實現(xiàn)

借助VB6.0的timer時間控件來實現(xiàn)排序過程的動態(tài)演示。通過觸發(fā)Timer控件的Timer事件，可以有規(guī)律地間隔一定時間執(zhí)行一次代碼;Interval屬性可用來設(shè)置觸發(fā)的時間間隔，以此來設(shè)置排序速度;Enabled屬性決定該控件是否對時間的推移做響應(yīng)，以此來控制排序過程的開始與停止。因此，各排序算法動態(tài)演示過程的不同關(guān)鍵在于timer事件的代碼編寫，以下為冒泡排序timer事件偽代碼（如圖4）。

● 排序算法動態(tài)演示過程及其對算法學(xué)習(xí)的幫助

1.透過動態(tài)過程演示動畫便于理解算法的基本思想

通過動態(tài)演示過程，可以直觀獲取各個算法具體而完整的執(zhí)行過程，理解算法的基本思想，掌握各算法的區(qū)別與聯(lián)系，為后期算法的設(shè)計以及代碼實現(xiàn)提供有力的知識基礎(chǔ)。

2.便于探究算法的時間復(fù)雜度

當(dāng)數(shù)據(jù)規(guī)模為n時，通過多組數(shù)據(jù)輸出模塊記錄的比較次數(shù)并結(jié)合執(zhí)行過程，可以很容易得出冒泡排序和選擇排序的比較次數(shù)均為n（n-1）/2，時間復(fù)雜度為O（n^2）;插入排序在最好的情況下（初始數(shù)據(jù)已有序）比較次數(shù)為n-1，在最差的情況下（初始數(shù)據(jù)完全逆序）比較次數(shù)為n（n-1）/2，因此平均比較次數(shù)約為n^2/4，故時間復(fù)雜度也為O（n^2）。

3.便于探究算法的穩(wěn)定性

排序算法往往還需要考察其算法穩(wěn)定性。排序算法穩(wěn)定性可簡單定義為：如果Ai=Aj，排序前Ai在Aj之前，排序后Ai還在Aj之前，則稱這種排序算法是穩(wěn)定的。通俗地講，就是保證排序前后兩個相等的數(shù)的相對順序不變。

本軟件對于相同的數(shù)據(jù)，在條形圖上方標(biāo)記該數(shù)據(jù)在相同數(shù)據(jù)序列中的原始排位，通過多組實驗數(shù)據(jù)驗證了冒泡排序和插入排序是穩(wěn)定的排序算法，而選擇排序是不穩(wěn)定的排序算法，如下頁圖5所示。本軟件對算法穩(wěn)定性的探究為學(xué)生提供了直觀清晰的數(shù)據(jù)分析。

● 結(jié)束語

本軟件實現(xiàn)了對冒泡排序、選擇排序和插入排序三種基本排序算法的動態(tài)排序演示，用戶界面簡單友好、清楚明了。對于抽象難懂的排序算法，此系統(tǒng)生動形象的動態(tài)演示使算法的執(zhí)行過程一目了然，可以幫助學(xué)生更好地掌握排序算法的基本思想，更為直觀地了解算法時間復(fù)雜度以及算法穩(wěn)定性方面的知識。當(dāng)然，排序算法很多，學(xué)生可以在此基礎(chǔ)上優(yōu)化改進(jìn)、分析設(shè)計出更加高效的排序算法。同時，此系統(tǒng)可以起到拋磚引玉的作用，鼓勵學(xué)生為此系統(tǒng)添加新的排序算法演示功能，活學(xué)活用，深入理解并實踐排序算法，進(jìn)一步鍛煉算法設(shè)計與實現(xiàn)能力。

參考文獻(xiàn)：

[1]劉斌，徐秀娟，王勝法，等.計算機圖形學(xué)可視化教學(xué)綜合實驗平臺開發(fā)[J].實驗室科學(xué)，2018，21（04）：53-56.

[2]李曉鴻，劉叢，駱嘉偉.基于學(xué)習(xí)者視角的算法可視化系統(tǒng)研究綜述[J].計算機科學(xué)，2015，42（11）：431-437.

[3]郭伊.《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)動態(tài)演示系統(tǒng)的設(shè)計與實現(xiàn)[D].咸陽：西北農(nóng)林科技大學(xué)，2015：1-56.

郭良敏，孫圳昊，羅永龍，等.“算法設(shè)計與分析”中經(jīng)典算法動態(tài)演示軟件的設(shè)計與實現(xiàn)[J].電腦知識與技術(shù)，2016，12（20）：224-225.

作者簡介：高向敏（1987—），女，江蘇鎮(zhèn)江人，南京師范大學(xué)碩士研究生，研究方向為計算機圖形學(xué)。