選擇排序算法常見問題分析

白洪濤 何麗莉 孫良鳳

摘 要 針對非計算機專業學生算法學習和程序實現所面臨的困難，將選擇排序分解為在序列中尋找最值和元素交換兩個步驟，分析了學生在程序實現上容易犯的典型錯誤。本文對算法和程序設計類教學有一定的借鑒意義。

關鍵詞 選擇排序 數據結構 常見錯誤 C語言

中圖分類號：O156.4 文獻標識碼：A

0引言

《算法與數據結構》不僅是計算機科學的重要專業基礎和核心課程，而且也越來越多地被非計算機專業所要求學習和掌握。排序算法是該課程的重要組成部分，在筆者所教授的地學各學院的《C語言程序設計基礎》和《數據結構》課程中均是講解的重點和難點，尤其是《C語言程序設計基礎》一般安排在《數據結構》課程之前，如何在基本的程序設計都比較陌生的學生中建立算法的思維，從而將排序算法和實際的程序對應起來，更是一個挑戰。

本文在《C語言程序設計基礎》課程教學過程中，設計選擇排序教學過程，分析了學生典型的兩種實現錯誤。

1選擇排序算法教學設計

1.1算法思想

選擇排序是一種直觀的排序算法。它的工作原理如下（以升序為例）。首先在未排序序列中找到最小元素，存放到該序列的第一個位置，即第一個位置的元素與該序列中最小元素交換，然后，再從剩余未排序元素中繼續尋找最小元素，放到第二個位置（交換）。以此類推，直到所有元素均排序完畢。

1.2算法實現

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

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

（2）用該數和未排序序列中的第一個數進行交換。

給出選擇排序的C語言程序如下：

#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++ ） //控制循環的趟數 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常見錯誤分析

在C語言程序編寫過程中，有的同學未能正確實現算法，典型的問題如下：

錯誤實現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]，但是該元素只是簡單地復制到了a[j]中，原有的a[j]被覆蓋，沒有保存下來，錯誤結果如下圖所示：

錯誤實現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；

}

}

本程序在未排序序列中只要找到一個“小值”，就迫不及待地進行交換，雖然也能正確地實現排序，但這不是嚴格的選擇排序，產生了很多“無用”的交換步驟，降低了程序實際執行效率。

3結束語

熟練掌握一門計算機程序設計語言無論是對計算機還是非計算機專業的學生都是非常重要的。算法的學習不應該是死記硬背，要學會分析問題，并能夠通過從錯誤逐步走向正確，增強學生獨立解決實際問題的編程能力。

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

參考文獻

[1] 嚴蔚敏，吳偉民.數據結構[M].北京：清華大學出版社，2004.

[2] 譚浩強.C 程序設計（第四版）[M].北京：清華大學出版社，2010.