白洪濤 何麗莉 孫良鳳

摘 要 針對(duì)非計(jì)算機(jī)專(zhuān)業(yè)學(xué)生算法學(xué)習(xí)和程序?qū)崿F(xiàn)所面臨的困難，將選擇排序分解為在序列中尋找最值和元素交換兩個(gè)步驟，分析了學(xué)生在程序?qū)崿F(xiàn)上容易犯的典型錯(cuò)誤。本文對(duì)算法和程序設(shè)計(jì)類(lèi)教學(xué)有一定的借鑒意義。

關(guān)鍵詞 選擇排序 數(shù)據(jù)結(jié)構(gòu) 常見(jiàn)錯(cuò)誤 C語(yǔ)言

中圖分類(lèi)號(hào)：O156.4 文獻(xiàn)標(biāo)識(shí)碼：A

0引言

《算法與數(shù)據(jù)結(jié)構(gòu)》不僅是計(jì)算機(jī)科學(xué)的重要專(zhuān)業(yè)基礎(chǔ)和核心課程，而且也越來(lái)越多地被非計(jì)算機(jī)專(zhuān)業(yè)所要求學(xué)習(xí)和掌握。排序算法是該課程的重要組成部分，在筆者所教授的地學(xué)各學(xué)院的《C語(yǔ)言程序設(shè)計(jì)基礎(chǔ)》和《數(shù)據(jù)結(jié)構(gòu)》課程中均是講解的重點(diǎn)和難點(diǎn)，尤其是《C語(yǔ)言程序設(shè)計(jì)基礎(chǔ)》一般安排在《數(shù)據(jù)結(jié)構(gòu)》課程之前，如何在基本的程序設(shè)計(jì)都比較陌生的學(xué)生中建立算法的思維，從而將排序算法和實(shí)際的程序?qū)?yīng)起來(lái)，更是一個(gè)挑戰(zhàn)。

本文在《C語(yǔ)言程序設(shè)計(jì)基礎(chǔ)》課程教學(xué)過(guò)程中，設(shè)計(jì)選擇排序教學(xué)過(guò)程，分析了學(xué)生典型的兩種實(shí)現(xiàn)錯(cuò)誤。

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

1.1算法思想

選擇排序是一種直觀的排序算法。它的工作原理如下（以升序?yàn)槔?。首先在未排序序列中找到最小元素，存放到該序列的第一個(gè)位置，即第一個(gè)位置的元素與該序列中最小元素交換，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素，放到第二個(gè)位置（交換）。以此類(lèi)推，直到所有元素均排序完畢。

1.2算法實(shí)現(xiàn)

通過(guò)上述算法分析講解，可以將選擇排序過(guò)程具體化為兩個(gè)步驟：

（1）在一個(gè)特定（未排序）序列中找出最小值（最大值）。

（2）用該數(shù)和未排序序列中的第一個(gè)數(shù)進(jìn)行交換。

給出選擇排序的C語(yǔ)言程序如下：

#include

int main（）

{

int i， a[6]；

int min， loc；

int j， t；

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

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

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

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；

}

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

printf（"%d "， a[i]）；

printf（"＼n"）；

return 0；

}

2常見(jiàn)錯(cuò)誤分析

在C語(yǔ)言程序編寫(xiě)過(guò)程中，有的同學(xué)未能正確實(shí)現(xiàn)算法，典型的問(wèn)題如下：

錯(cuò)誤實(shí)現(xiàn)1：

for （ j=0； j<5； j++ ）

{

min = a[j]；

loc = j；

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

if （ min > a[i] ）

{

min = a[i]；

loc = i；

}

a[j] = a[loc]；

}

在算法的主體程序塊，能夠正確在未排序序列中選出最小值a[loc]，但是該元素只是簡(jiǎn)單地復(fù)制到了a[j]中，原有的a[j]被覆蓋，沒(méi)有保存下來(lái)，錯(cuò)誤結(jié)果如下圖所示：

錯(cuò)誤實(shí)現(xiàn)2：

for （ j=0； j<5； j++ ）

{

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

if （ a[j] > a[i] ）

{

t = a[i]；

a[i] = a[j]；

a[j] = t；

}

}

本程序在未排序序列中只要找到一個(gè)“小值”，就迫不及待地進(jìn)行交換，雖然也能正確地實(shí)現(xiàn)排序，但這不是嚴(yán)格的選擇排序，產(chǎn)生了很多“無(wú)用”的交換步驟，降低了程序?qū)嶋H執(zhí)行效率。

3結(jié)束語(yǔ)

熟練掌握一門(mén)計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言無(wú)論是對(duì)計(jì)算機(jī)還是非計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生都是非常重要的。算法的學(xué)習(xí)不應(yīng)該是死記硬背，要學(xué)會(huì)分析問(wèn)題，并能夠通過(guò)從錯(cuò)誤逐步走向正確，增強(qiáng)學(xué)生獨(dú)立解決實(shí)際問(wèn)題的編程能力。

作者簡(jiǎn)介：白洪濤（1975-），男，漢族，吉林榆樹(shù)人，博士，副教授，主要從事高性能計(jì)算研究；通信作者：何麗莉（1976-），女，漢族，吉林洮南人，博士，副教授，主要從事基于WSN的環(huán)境智能研究。

參考文獻(xiàn)

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2004.

[2] 譚浩強(qiáng).C 程序設(shè)計(jì)（第四版）[M].北京：清華大學(xué)出版社，2010.