摘要:作者針對數(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é)。