基于Matlab的選擇排序算法教學設計

衛澤剛張小丹＊ 趙軍娣劉 飛錢 郁

（1.寶雞文理學院物理與光電技術學院，陜西 寶雞 721016；2.寶雞高新鳳師實驗小學，陜西 寶雞 721016）

0 引言

Matlab和C語言都是面向工科專業開設的編程語言類專業基礎課，相對于C語言，Matlab操作更方便，編程語法更簡單，因此更易于學生學習。同時，Matlab也與其他編程語言有很多語法相通的地方，學好Matlab一方面可以提高學生的編程技能，加深對“軟件程序”這一概念的理解，另一方面還能對學習其他編程語言起到理解促進作用。排序作為計算機軟件數據處理中最基本的操作之一，已成為計算機編程語言學習的重要內容，其中對不同排序方法的理解與編程實現也是測試學生是否掌握編程語言學習的重要手段。因此，為了更好地使學生理解、掌握排序方法的排序過程，很多教學工作者研究了多種有效的教學手段。例如，張文慧著重分析了冒泡排序方法的特點，并以數據排序問題引導學生學會主動思考問題，并學會對問題進行總結歸納，培養學生獨立思考與總結能力；曹春梅等通過引導學生對冒泡排序及其改進算法的學習，著重提高學生的程序設計能力，可為相關算法與程序設計方面的進一步學習和研究打下良好基礎。本文針對非計算機專業Matlab語言與應用課程教學過程設計了循序漸進、由淺入深、難點分析、拓展練習的遞進式選擇排序教學過程，首先通過簡單形象例子詳細介紹了選擇排序算法的過程，其次用Matlab進行編程代碼實現，針對代碼難點進行重點分析，最后設計了兩個拓展練習題，加深學生對選擇排序算法的理解，并培養學生根據項要求獨立編寫程序的能力。

1 選擇排序算法教學設計

1.1 選擇排序算法過程

選擇排序算法是一種簡單直觀、易于學習的排序方法，其詳細排序過程（以升序排序為例）為：對于待排序數據，首先遍歷并比較所有數據，找到最小值后與第一個數據進行交換，此時第一個位置的數據就是所有數據中的最小值。然后再從第二個位置開始繼續尋找最小值，與第二個位置上的數據進行交換。以此類推，直到所有數據處理完畢。由于每次都選擇剩余數據中的最小值進行交換，因此稱此方法排序為選擇排序。

用一個簡單的例子對選擇排序過程進行詳細講解，加深學生對選擇排序的理解。如圖1所示，假如要對五個數據進行排序，五個待排序數據為：16、19、15、39、8。要求使用選擇排序方法對它們進行升序排序。首先進行第一趟排序，選取所有數據中的最小值8，并與第一個位置上的數據16交換，此時第一趟排序結束。然后進行第二趟排序，從第二個位置開始選取剩余數據（19、15、39、16）中的最小值15，再與第二個位置上的數據19進行交換，此時第二趟排序結束，且前兩個位置上的數據已排好序。然后進行第三趟排序，從第三個位置開始選取剩余數據（19、39、16）中的最小值16，與第三個位置上的數據19進行交換，此時第三趟排序結束，且前三個位置上的數據已排好序。然后進行第四趟排序，從第四個位置開始選取剩余數據（39、19）中的最小值19，與第四個位置上的數據39進行交換，此時第四趟排序結束，且前四個位置上的數據已排好序。第四趟排序后只剩下一個數據39，即為數據中的最大值，不需要進行額外操作，此時排序結束。圖1共排序四趟，即可得到最終的排序結果：8、15、16、19、39。圖1中綠色數字表示每一趟排序后已經排好序的數據部分。根據圖1可以得出，若數據的總個數為n，則需要n-1趟完成對整個數據的排序。

圖1 選擇排序示例（綠色數字表示每一趟排序后已經排好序的數據部分）

1.2 選擇排序代碼實現

通過上述對選擇排序算法的過程分析和實例的詳細圖解，可以將選擇排序每一趟操作過程總結為兩個步驟：（1）在剩余未排序數據中找到最小值；（2）用最小值與未排序數據的第一個數進行交換。基于此，選擇排序的操作就轉化為在數據中尋找最小值后再與數據進行交換的問題。其中找最小值可以使用打擂臺法，即按順序和后面的數據依次進行數值大小比較，選出最小值。數據交換問題可以用Matlab的元素賦值操作完成。結合以上分析，選擇排序的Matlab編程實現代碼如下：

function out=selectSort（data）%輸入待排序數據data，輸出排好序的out

n=length（data）；%求取待排序數據的總個數n

for i=1：n-1 %外循環，總的排序趟數：n-1

min_num=data（i）；%每一趟先取第一個數據作為最小值

min_index=i；%存取最小值的索引位置

for j=i+1：n %打擂臺法，與后面的數據依次比較大小

if min_num＞data（j）%與每個數據比較大小

min_num=data（j）；%存取最小值

min_index=j；%存取最小值的數據索引

end

end

temp=data（min_index）；%提取最小值

data（min_index）=data（i）；%數據交換

data（i）=temp；%數據交換

end

out=data；%輸出排好序的數據

end

1.3 代碼難點及分析

上述代碼以函數定義的形式對選擇排序算法進行編程實現，最直觀地體現了選擇排序的排序過程。其中有以下兩處代碼是學生難以理解的。（1）代碼第四行最小值賦值，有很多學生不理解為什么最小值初值選取數據的第i個元素。主要原因在于沒有理解排序算法每一趟最小值的選取問題。每一趟的最小值選取采用打擂臺方法，即把當前值（min_num）先作為最小值，然后再與后面的數據“打擂臺”，即依次比較大小，如果比當前最小值（min_num）小，就交換數據，否則不交換數據。通過與每個數據比較后即可將最小值選取出來。（2）數據交換過程（第12、13、14行）為什么要先定義一個臨時變量（temp）而不是直接對兩個數據進行賦值。這主要原因在于沒有將Matlab的賦值操作與現實問題有效結合。學生們都能直觀地理解交換兩個數據的概念，但是將其用編程語言實現就需要一定的“技巧”，如果直接按照以下代碼操作：data（min_index）=data（i）；data（i）=data（min_index）；，就會把原來data（min_index）數據丟掉，造成的結果就是data（min_index）和data（i）都變成同一個數據了。而通過提前定義一個臨時變量temp，就可以將最小值data（min_index）先保存起來，再賦值給變量data（i），完成數據的交換。

1.4 拓展練習設計

為進一步提高學生對選擇排序算法的理解與編程能力，在完全理解上述代碼排序的基礎上，增加以下兩個問題讓學生進行拓展訓練：（1）在2.2節代碼基礎上修改，完成選擇排序算法的降序排序過程，即將數據從大到小進行排序。（2）上述代碼會改變原始數據的排列，如何新建一個同樣大小的數組a，將每一趟選取的最小值依次放入數組a中并輸出，以保證原始數據未被修改。第一個拓展練習題用類似的代碼編程方式完成降序排序過程，可以加深學生對排序算法的理解。第二個拓展練習題可以提高學生的編程能力，如何根據項目需求進行思考，再將思考過程轉化成具體的代碼，同時可以讓學生們深刻認識到，實現相同的排序功能，代碼編寫方式可以是不一樣的。

2 結語

Matlab是一門應用性很強的實踐性課程，必須結合具體問題開展課程教學。本文以排序算法中簡單直觀的選擇排序算法入手，采用分階段、逐步遞進、難點分析、拓展練習的思路對選擇排序方法進行了詳細介紹，由淺入深、循序漸進，針對學生難以理解的代碼難點進行了深入分析，降低了學生用Matlab編寫選擇排序程序的難度。最后用兩個拓展練習，強化學生對選擇排序算法的理解，同時提高學生根據問題需求，編寫代碼解決問題的能力。