循序渐进学习C语言选择排序算法

闫鑫,王琴竹

（1.山西财经大学信息管理学院，太原 030006；2.运城学院公共计算机教学部，运城 044000）

0 引言

《C语言程序设计》课程不仅是计算机专业必修的一门专业基础课，而且是非计算机理工类各专业计算机基础教育的重要组成部分。学生学习《C语言程序设计》课程的主要目的是锻炼思维能力，并能应用所学知识解决实际问题。

在《C语言程序设计》课程的学习内容中，算法是非常重要的组成部分，在培养学生的思维能力方面起着至关重要的作用[1]。在要求掌握的各个典型算法中，排序算法尤其是选择排序算法是最难掌握的算法之一。

本文首先介绍顺序结构程序设计中的交换算法，这是选择排序算法的基础。其次，应用选择结构程序设计中的单分支if语句和比较交换排序思想，实现了三个数、四个数的排序；应用循环结构程序设计中的for语句、数组数据结构和比较交换排序思想，实现了N个数的排序。针对比较交换排序算法效率低的问题，在其中结合假设思想，应用选择排序算法实现N个数的排序。

1 交换算法

问题描述：已知变量x的值是2，y的值是1，编写程序使x和y中的数据按升序排序。

算法分析：借助第三个变量，交换变量x和y的值即可。

应用C语言编写的交换算法代码如下：t=x；x=y；y=t；

可见，应用交换算法实现了x和y两个数据的升序排序。

2 比较交换排序

在程序设计中，一般要求所设计的算法具有通用性[2]。因此，假设x和y的值是在程序运行过程中输入的，则需要对x和y的值进行比较。实现升序排序的代码如下：

if(x>y){t=x；x=y；y=t；}/*x中存放 x和 y中较小的数*/

这种排序方法就是比较交换的方法。下面应用比较交换的方法分别对三个数、四个数进行排序，总结这种排序的思想，然后应用该方法对N个数进行排序。

2.1 三个数的排序

问题描述：已知三个变量x、y和z，编写程序使x、y和z中的数据按升序排序。

算法分析：先通过比较交换，使x中存放三个数中的最小数，然后应用两个数的排序方法使y和z中的数据按升序排序。

应用C语言编写的排序算法代码如下：

if(x>y){t=x；x=y；y=t；}

if(x>z){t=x；x=z；z=t；}

/*经过第一趟比较交换，最小数存放在x中，下一趟x不参与排序*/

if(y>z){t=y；y=z；z=t；}

/*经过第二趟比较交换，y和z中的数据按升序排序，排序结束*/

2.2 四个数的排序

问题描述：编写程序使四个变量w、x、y和z中的数组按升序排序。

算法分析：首先使w中存放四个数中的最小数，然后应用三个数的排序方法使x、y和z中的数据按升序排序。

应用C语言编写的排序算法代码如下：

if(w>x){t=w；w=x；x=t；}

if(w>y){t=w；w=y；y=t；}

if(w>z){t=w；w=z；z=t；}

/*经过第一趟比较交换，最小数存放在变量w中，下一趟w不参与排序*/

if(x>y){t=x；x=y；y=t；}

if(x>z){t=x；x=z；z=t；}

/*经过第二趟比较交换，次小的数存放在变量x中，下一趟x也不参与排序*/

if(y>z){t=y；y=z；z=t；}

/*经过第三趟比较交换，y和z中的数据按升序排序，排序结束*/

分析以上的排序过程，可以总结出应用比较交换的思想进行排序的方法如下：

（1）用待排序范围内的第一个数据分别与其他数据进行比较，并交换不满足顺序要求的那些数据对，第一趟排序后待排序范围内的第一个数据排好序。

（2）第二趟排序时待排序范围为除了第一个数据以外的其他数据，按照第一趟比较交换方法排好第二个数据。

（3）以此类推，直到所有数据排好序。

2.3 N个数的排序

问题描述：已知整型数组s中包含N个数组元素，应用比较交换的思想，将数组中的数据按照升序排序。算法分析：在比较交换排序过程中，需要解决两个关键问题，一是排序的趟数，二是每趟排序过程中的比较次数[3]。表1列出了三个数和四个数排序时，排序趟数和每趟排序过程中的比较次数。

分析表1中的数据可知，排序趟数为待排序数据个数减1，某趟的比较次数与第几趟有关，二者之和为待排序数据个数。因此，当待排序数据个数为N时，排序趟数为 N-1，分别为第 1、2、…，N-1，即 i的取值范围。在某趟排序时，比较次数为N-i,参与比较的数据对为下标为i-1的数组元素和其后所有的数组元素。表2列出了N个数组元素排序时的排序趟数、比较次数和参与比较的数据对。

表2 排序趟数、比较次数和比较数据对

分析表2可见，当i取某个值时，j需要取不同的值，需要用循环的嵌套来实现。

应用C语言编写的排序算法程序代码如下：

for(i=1;i

for(j=1;j<=N-i;j++)/*变量j控制某趟排序的比较次数*/

if(s[i-1]>s[i+j-1])

{t=s[i-1];s[i-1]=s[i+j-1];s[i+j-1]=t;}

算法解析：

（1）在程序中变量j的作用是控制某趟排序时的比较次数，如果和数组元素的下标相联系可以使j的取值范围从i到N-1。应用C语言编写的排序算法程序代码如下：

for(i=1;i

for(j=i;j

if(s[i-1]>s[j])

{t=s[i-1];s[i-1]=s[j];s[j]=t;}

（2）通过分析该算法可知，在最坏的情况下（原数据降序时），每次比较的数据对都不满足排序要求，即每次比较都需要交换，算法的效率较低。事实上，该排序算法的每趟排序结果都是将待排序范围内的最小数据置于第一个数据的位置，和选择排序算法的思想相一致。

3 选择排序算法

选择排序算法结合了求极值算法中的假设思想和比较交换思想，需要用一个标记变量记录待排序范围内最小（大）数据的下标[4]。应用选择排序算法进行升序排序的具体方法为：

（1）假设第一个数据最小，用一个标记变量记录其下标。

（2）用下标为该标记变量的数据分别与其他数据进行比较，如果标记变量记录的不是较小值，则修改标记变量的值为较小数据的下标，第一趟比较结束后标记变量记录的是所有数据中最小值的下标。

（3）如果第一个数据不是最小（即标记变量不等于第一个数的下标）时，将最小值（下标为标记变量的数据）和第一个数据进行交换。

（4）下一趟排序时待排序范围为除了第一个数据以外的其他数据，按照第一趟方法排好第二个数据。

（5）以此类推，直到所有数据排好序。

问题描述：已知整型数组s中包含N个数组元素，应用选择排序算法，将数组中的数据按照升序排序。

算法分析：N个数排序时的排序趟数和排序次数与比较交换排序方法完全相同[5]。应用C语言编写的完整排序算法程序代码如下：

#include"stdio.h"

#define N 10

void main()

{int s[N],i,j,t,loc;/*loc为记录最小值下标的标记变量*/

for(i=0;i

for(i=1;i

{loc=i-1;/*假设待排序范围内的第一数据最小*/

for(j=i;j

if(s[loc]>s[j])/*如果loc记录的不是最小值下标*/

loc=j;/*修改假设*/

if(loc!=i-1)/*如果最小值不是待排序范围内的第一个数*/

/*将最小值置于待排序范围内第一个数的位置*/

{t=s[loc];s[loc]=s[i-1];s[i-1]=t;}

}

for(i=0;i

}

算法解析：

（1）通过分析该算法可知，在最坏的情况下（原数据降序时），每次比较的数据对虽然都不满足排序要求，但不需要进行交换，当该趟比较结束后进行一次交换即可，大大提高了算法的效率。

（2）在程序中变量i的作用只是控制排序的趟数，取值可以从1到N-1，也可以从0到N-2，相应的需要修改程序的其他部分。

4 结语

选择排序算法是《C语言程序设计》课程中较难掌握的内容之一，很多学生无法掌握甚至不能理解选择排序算法，不仅阻碍了计算思维能力的培养，而且使得解决实际问题的能力受到了限制。通过介绍交换算法和比较交换排序思想，然后结合假设思想，使学生最终掌握选择排序算法。通过选择排序算法的学习，掌握由浅入深、循序渐进和举一反三的学习方法，并倡导学生在学习过程中重视思考，注重创新的探究精神。

[1]耿国华.数据结构-C语言描述[M].西安:西安电子科技大学出版社,2006.

[2]梁文忠.一种基于直接选择算法的改进[J].广西师范学院学报:自然科学版,2004,21(4):93-96.

[3]张忆文,谭霁.简单选择排序算法改进及分析[J].硅谷,2009(18):77,94.

[4]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,2000.

[5]何洪英.两种排序算法的改进[J].绵阳师范学院学报,2007,26(11):98-99.