選擇排序算法教學設計

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

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

關鍵詞：選擇排序；數據結構；教學過程；C語言

中圖分類號：G642 文獻標志碼：A 文章編號：1674-9324（2018）35-0196-02

一、引言

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

二、選擇排序算法教學設計

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

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

2.算法實現。通過上述算法分析和實例講解，可以將選擇排序過程具體化為兩個步驟：（1）在一個特定（未排序）序列中找出最小值（最大值）；（2）用該數和未排序序列中的第一個數進行交換。如此，把選擇排序轉換成在序列中找最值和元素的交換問題。其中，找最值可以使用打擂臺的算法，給出選出序列最小值及其位置的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；

}

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

t = a[0]；

a[0] = a[loc]；

a[loc] = t；

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

for （ j=0；j<5；j++ ） //控制循環的趟數 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；

}

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

參考文獻：

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

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

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