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

白洪濤　何麗莉　孫良鳳　金龍海

摘要：針對非計算機專業(yè)學(xué)生算法學(xué)習(xí)和程序?qū)崿F(xiàn)所面臨的困難，采用分階段、逐步遞進的思路對選擇排序方法進行了介紹，將選擇排序分解為在序列中尋找最值和元素交換兩個步驟，提供了選擇排序算法的C語言實現(xiàn)。

關(guān)鍵詞：選擇排序；數(shù)據(jù)結(jié)構(gòu)；教學(xué)過程；C語言

中圖分類號：G642 文獻(xiàn)標(biāo)志碼：A 文章編號：1674-9324（2018）35-0196-02

一、引言

為了更好地使初學(xué)者掌握排序算法，廣大計算機教學(xué)工作者研究了多種有效的教學(xué)手段，如：謝翠萍等結(jié)合雙向思維法，口訣教學(xué)法的教學(xué)過程設(shè)計，使學(xué)生更好得掌握冒泡排序算法，培養(yǎng)學(xué)生的發(fā)散思維能力[1]；馬秀榮闡述了選擇法排序的過程，側(cè)重使學(xué)生理解數(shù)組的定義、數(shù)組元素的引用以及數(shù)組下標(biāo)和數(shù)組元素之間一對一的關(guān)系[2]。為了算法的過程更直觀，學(xué)生更容易理解，文獻(xiàn)[3]借助現(xiàn)代多媒體技術(shù)手段設(shè)計了基于Flash和其他動畫等的排序過程和結(jié)果演示，并取得了不錯的教學(xué)效果。本文在非計算機專業(yè)《C語言程序設(shè)計基礎(chǔ)》課程教學(xué)過程中設(shè)計了先“打擂臺”再“排序”的遞進式選擇排序教學(xué)過程，并分析了學(xué)生典型的兩種現(xiàn)實錯誤。

二、選擇排序算法教學(xué)設(shè)計

1.算法思想。選擇排序是一種直觀的排序算法，它的工作原理如下（以升序為例）：首先在未排序序列中找到最小元素，存放到該序列的第一個位置，即第一個位置的元素與該序列中最小元素交換，然后再從剩余未排序元素中繼續(xù)尋找最小元素，放到第二個位置（交換）。以此類推，直到所有元素均排序完畢。我們以一個6個整型數(shù)據(jù)實例進行講解：有21、25、67、89、32、19未排序序列，要求將它們使用選擇排序方法進行升序排序。

如圖1所示，用向下的箭頭指向未排序序列中的第一個數(shù)，用向上的箭頭指向該序列的最小數(shù)，這兩個數(shù)進行交換便完成了一趟排序。整個序列分成兩個部分：已排序部分（中括號外）和未排序部分（中括號內(nèi)），每一趟排序使得整個序列中的一個數(shù)“就位”，這樣若序列的長度為n，則需要n-1趟交換，即可完成整個序列的排序。

2.算法實現(xiàn)。通過上述算法分析和實例講解，可以將選擇排序過程具體化為兩個步驟：（1）在一個特定（未排序）序列中找出最小值（最大值）；（2）用該數(shù)和未排序序列中的第一個數(shù)進行交換。如此，把選擇排序轉(zhuǎn)換成在序列中找最值和元素的交換問題。其中，找最值可以使用打擂臺的算法，給出選出序列最小值及其位置的C語言程序如下：

#include

int main（）

{

int i，a[6]；

int min，loc；

printf（"please input 6 integer numbers：＼n"）；

for （ i=0；i<6；i++ ）

scanf（"%d"，&a;[i]）；

min = a[0]；

loc = 0；

for（ i=1；i<6；i++ ）

if （ min > a[i] ）

{

min = a[i]；

loc = i；

}

printf（"the min of array is %d，loc is %d＼n"，min，loc）；

return 0；

}

在打擂臺算法的基礎(chǔ)上，我們再補充元素交換，即將最小值a[loc]與a[0]進行交換：

t = a[0]；

a[0] = a[loc]；

a[loc] = t；

如此，我們再將趟數(shù)的外層循環(huán)作用在如上程序塊上，a[0]中的0變成外層循環(huán)控制變量j，內(nèi)層循環(huán)從j+1（未排序序列）開始，這樣選擇排序的整體算法便不難了（只給出關(guān)鍵程序段）。

for （ j=0；j<5；j++ ） //控制循環(huán)的趟數(shù) n-1

{

min = a[j]；

loc = j；

for （ i=j+1；i<6；i++ ） //在未排序序列中選最小a[loc]

if （ min > a[i] ）

{

min = a[i]；

loc = i；

}

//a[loc]與a[j]交換

t = a[j]；

a[j] = a[loc]；

a[loc]=t；

}

當(dāng)然，求最小值時可以不用min變量存放，直接使用a[loc]即可。

參考文獻(xiàn)：

[1]謝翠萍，陳家益，朱兵章.C語言中冒泡排序教學(xué)設(shè)計與分析[J].福建電腦，2013，（5）：50-51.

[2]馬秀榮.《C程序設(shè)計》中選擇法排序教學(xué)方法的探討[J].佳木斯教育學(xué)院學(xué)報，2010，（1）：115-116.

[3]邱秀榮，趙莉蘋，蔡鑌.基于Flash的冒泡排序算法的演示實現(xiàn)[J].安陽工學(xué)院學(xué)報，2011，10（6）：48-50.