基于Matlab的選擇排序算法教學(xué)設(shè)計(jì)

衛(wèi)澤剛張小丹＊ 趙軍娣劉 飛錢 郁

（1.寶雞文理學(xué)院物理與光電技術(shù)學(xué)院，陜西 寶雞 721016；2.寶雞高新鳳師實(shí)驗(yàn)小學(xué)，陜西 寶雞 721016）

0 引言

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

1 選擇排序算法教學(xué)設(shè)計(jì)

1.1 選擇排序算法過程

選擇排序算法是一種簡(jiǎn)單直觀、易于學(xué)習(xí)的排序方法，其詳細(xì)排序過程（以升序排序?yàn)槔椋簩?duì)于待排序數(shù)據(jù)，首先遍歷并比較所有數(shù)據(jù)，找到最小值后與第一個(gè)數(shù)據(jù)進(jìn)行交換，此時(shí)第一個(gè)位置的數(shù)據(jù)就是所有數(shù)據(jù)中的最小值。然后再?gòu)牡诙€(gè)位置開始繼續(xù)尋找最小值，與第二個(gè)位置上的數(shù)據(jù)進(jìn)行交換。以此類推，直到所有數(shù)據(jù)處理完畢。由于每次都選擇剩余數(shù)據(jù)中的最小值進(jìn)行交換，因此稱此方法排序?yàn)檫x擇排序。

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

圖1 選擇排序示例（綠色數(shù)字表示每一趟排序后已經(jīng)排好序的數(shù)據(jù)部分）

1.2 選擇排序代碼實(shí)現(xiàn)

通過上述對(duì)選擇排序算法的過程分析和實(shí)例的詳細(xì)圖解，可以將選擇排序每一趟操作過程總結(jié)為兩個(gè)步驟：（1）在剩余未排序數(shù)據(jù)中找到最小值；（2）用最小值與未排序數(shù)據(jù)的第一個(gè)數(shù)進(jìn)行交換?；诖?，選擇排序的操作就轉(zhuǎn)化為在數(shù)據(jù)中尋找最小值后再與數(shù)據(jù)進(jìn)行交換的問題。其中找最小值可以使用打擂臺(tái)法，即按順序和后面的數(shù)據(jù)依次進(jìn)行數(shù)值大小比較，選出最小值。數(shù)據(jù)交換問題可以用Matlab的元素賦值操作完成。結(jié)合以上分析，選擇排序的Matlab編程實(shí)現(xiàn)代碼如下：

function out=selectSort（data）%輸入待排序數(shù)據(jù)data，輸出排好序的out

n=length（data）；%求取待排序數(shù)據(jù)的總個(gè)數(shù)n

for i=1：n-1 %外循環(huán)，總的排序趟數(shù)：n-1

min_num=data（i）；%每一趟先取第一個(gè)數(shù)據(jù)作為最小值

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

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

if min_num＞data（j）%與每個(gè)數(shù)據(jù)比較大小

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

min_index=j；%存取最小值的數(shù)據(jù)索引

end

end

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

data（min_index）=data（i）；%數(shù)據(jù)交換

data（i）=temp；%數(shù)據(jù)交換

end

out=data；%輸出排好序的數(shù)據(jù)

end

1.3 代碼難點(diǎn)及分析

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

1.4 拓展練習(xí)設(shè)計(jì)

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

2 結(jié)語

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