基于VB6.0的排序算法動(dòng)態(tài)演示軟件的設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

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

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

● 排序算法

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

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

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

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

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

● 動(dòng)態(tài)演示軟件的設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

● 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

作者簡(jiǎn)介：高向敏（1987—），女，江蘇鎮(zhèn)江人，南京師范大學(xué)碩士研究生，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。