选择排序算法常见问题分析

白洪涛 何丽莉 孙良凤

摘 要 针对非计算机专业学生算法学习和程序实现所面临的困难，将选择排序分解为在序列中寻找最值和元素交换两个步骤，分析了学生在程序实现上容易犯的典型错误。本文对算法和程序设计类教学有一定的借鉴意义。

关键词 选择排序 数据结构 常见错误 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.