循序漸進(jìn)學(xué)習(xí)C語(yǔ)言選擇排序算法

閆鑫,王琴竹

（1.山西財(cái)經(jīng)大學(xué)信息管理學(xué)院，太原 030006；2.運(yùn)城學(xué)院公共計(jì)算機(jī)教學(xué)部，運(yùn)城 044000）

0 引言

《C語(yǔ)言程序設(shè)計(jì)》課程不僅是計(jì)算機(jī)專業(yè)必修的一門專業(yè)基礎(chǔ)課，而且是非計(jì)算機(jī)理工類各專業(yè)計(jì)算機(jī)基礎(chǔ)教育的重要組成部分。學(xué)生學(xué)習(xí)《C語(yǔ)言程序設(shè)計(jì)》課程的主要目的是鍛煉思維能力，并能應(yīng)用所學(xué)知識(shí)解決實(shí)際問題。

在《C語(yǔ)言程序設(shè)計(jì)》課程的學(xué)習(xí)內(nèi)容中，算法是非常重要的組成部分，在培養(yǎng)學(xué)生的思維能力方面起著至關(guān)重要的作用[1]。在要求掌握的各個(gè)典型算法中，排序算法尤其是選擇排序算法是最難掌握的算法之一。

本文首先介紹順序結(jié)構(gòu)程序設(shè)計(jì)中的交換算法，這是選擇排序算法的基礎(chǔ)。其次，應(yīng)用選擇結(jié)構(gòu)程序設(shè)計(jì)中的單分支if語(yǔ)句和比較交換排序思想，實(shí)現(xiàn)了三個(gè)數(shù)、四個(gè)數(shù)的排序；應(yīng)用循環(huán)結(jié)構(gòu)程序設(shè)計(jì)中的for語(yǔ)句、數(shù)組數(shù)據(jù)結(jié)構(gòu)和比較交換排序思想，實(shí)現(xiàn)了N個(gè)數(shù)的排序。針對(duì)比較交換排序算法效率低的問題，在其中結(jié)合假設(shè)思想，應(yīng)用選擇排序算法實(shí)現(xiàn)N個(gè)數(shù)的排序。

1 交換算法

問題描述：已知變量x的值是2，y的值是1，編寫程序使x和y中的數(shù)據(jù)按升序排序。

算法分析：借助第三個(gè)變量，交換變量x和y的值即可。

應(yīng)用C語(yǔ)言編寫的交換算法代碼如下：t=x；x=y；y=t；

可見，應(yīng)用交換算法實(shí)現(xiàn)了x和y兩個(gè)數(shù)據(jù)的升序排序。

2 比較交換排序

在程序設(shè)計(jì)中，一般要求所設(shè)計(jì)的算法具有通用性[2]。因此，假設(shè)x和y的值是在程序運(yùn)行過程中輸入的，則需要對(duì)x和y的值進(jìn)行比較。實(shí)現(xiàn)升序排序的代碼如下：

if(x>y){t=x；x=y；y=t；}/*x中存放 x和 y中較小的數(shù)*/

這種排序方法就是比較交換的方法。下面應(yīng)用比較交換的方法分別對(duì)三個(gè)數(shù)、四個(gè)數(shù)進(jìn)行排序，總結(jié)這種排序的思想，然后應(yīng)用該方法對(duì)N個(gè)數(shù)進(jìn)行排序。

2.1 三個(gè)數(shù)的排序

問題描述：已知三個(gè)變量x、y和z，編寫程序使x、y和z中的數(shù)據(jù)按升序排序。

算法分析：先通過比較交換，使x中存放三個(gè)數(shù)中的最小數(shù)，然后應(yīng)用兩個(gè)數(shù)的排序方法使y和z中的數(shù)據(jù)按升序排序。

應(yīng)用C語(yǔ)言編寫的排序算法代碼如下：

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

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

/*經(jīng)過第一趟比較交換，最小數(shù)存放在x中，下一趟x不參與排序*/

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

/*經(jīng)過第二趟比較交換，y和z中的數(shù)據(jù)按升序排序，排序結(jié)束*/

2.2 四個(gè)數(shù)的排序

問題描述：編寫程序使四個(gè)變量w、x、y和z中的數(shù)組按升序排序。

算法分析：首先使w中存放四個(gè)數(shù)中的最小數(shù)，然后應(yīng)用三個(gè)數(shù)的排序方法使x、y和z中的數(shù)據(jù)按升序排序。

應(yīng)用C語(yǔ)言編寫的排序算法代碼如下：

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；}

/*經(jīng)過第一趟比較交換，最小數(shù)存放在變量w中，下一趟w不參與排序*/

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

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

/*經(jīng)過第二趟比較交換，次小的數(shù)存放在變量x中，下一趟x也不參與排序*/

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

/*經(jīng)過第三趟比較交換，y和z中的數(shù)據(jù)按升序排序，排序結(jié)束*/

分析以上的排序過程，可以總結(jié)出應(yīng)用比較交換的思想進(jìn)行排序的方法如下：

（1）用待排序范圍內(nèi)的第一個(gè)數(shù)據(jù)分別與其他數(shù)據(jù)進(jìn)行比較，并交換不滿足順序要求的那些數(shù)據(jù)對(duì)，第一趟排序后待排序范圍內(nèi)的第一個(gè)數(shù)據(jù)排好序。

（2）第二趟排序時(shí)待排序范圍為除了第一個(gè)數(shù)據(jù)以外的其他數(shù)據(jù)，按照第一趟比較交換方法排好第二個(gè)數(shù)據(jù)。

（3）以此類推，直到所有數(shù)據(jù)排好序。

2.3 N個(gè)數(shù)的排序

問題描述：已知整型數(shù)組s中包含N個(gè)數(shù)組元素，應(yīng)用比較交換的思想，將數(shù)組中的數(shù)據(jù)按照升序排序。算法分析：在比較交換排序過程中，需要解決兩個(gè)關(guān)鍵問題，一是排序的趟數(shù)，二是每趟排序過程中的比較次數(shù)[3]。表1列出了三個(gè)數(shù)和四個(gè)數(shù)排序時(shí)，排序趟數(shù)和每趟排序過程中的比較次數(shù)。

分析表1中的數(shù)據(jù)可知，排序趟數(shù)為待排序數(shù)據(jù)個(gè)數(shù)減1，某趟的比較次數(shù)與第幾趟有關(guān)，二者之和為待排序數(shù)據(jù)個(gè)數(shù)。因此，當(dāng)待排序數(shù)據(jù)個(gè)數(shù)為N時(shí)，排序趟數(shù)為 N-1，分別為第 1、2、…，N-1，即 i的取值范圍。在某趟排序時(shí)，比較次數(shù)為N-i,參與比較的數(shù)據(jù)對(duì)為下標(biāo)為i-1的數(shù)組元素和其后所有的數(shù)組元素。表2列出了N個(gè)數(shù)組元素排序時(shí)的排序趟數(shù)、比較次數(shù)和參與比較的數(shù)據(jù)對(duì)。

表2 排序趟數(shù)、比較次數(shù)和比較數(shù)據(jù)對(duì)

分析表2可見，當(dāng)i取某個(gè)值時(shí)，j需要取不同的值，需要用循環(huán)的嵌套來實(shí)現(xiàn)。

應(yīng)用C語(yǔ)言編寫的排序算法程序代碼如下：

for(i=1;i

for(j=1;j<=N-i;j++)/*變量j控制某趟排序的比較次數(shù)*/

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的作用是控制某趟排序時(shí)的比較次數(shù)，如果和數(shù)組元素的下標(biāo)相聯(lián)系可以使j的取值范圍從i到N-1。應(yīng)用C語(yǔ)言編寫的排序算法程序代碼如下：

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）通過分析該算法可知，在最壞的情況下（原數(shù)據(jù)降序時(shí)），每次比較的數(shù)據(jù)對(duì)都不滿足排序要求，即每次比較都需要交換，算法的效率較低。事實(shí)上，該排序算法的每趟排序結(jié)果都是將待排序范圍內(nèi)的最小數(shù)據(jù)置于第一個(gè)數(shù)據(jù)的位置，和選擇排序算法的思想相一致。

3 選擇排序算法

選擇排序算法結(jié)合了求極值算法中的假設(shè)思想和比較交換思想，需要用一個(gè)標(biāo)記變量記錄待排序范圍內(nèi)最?。ù螅?shù)據(jù)的下標(biāo)[4]。應(yīng)用選擇排序算法進(jìn)行升序排序的具體方法為：

（1）假設(shè)第一個(gè)數(shù)據(jù)最小，用一個(gè)標(biāo)記變量記錄其下標(biāo)。

（2）用下標(biāo)為該標(biāo)記變量的數(shù)據(jù)分別與其他數(shù)據(jù)進(jìn)行比較，如果標(biāo)記變量記錄的不是較小值，則修改標(biāo)記變量的值為較小數(shù)據(jù)的下標(biāo)，第一趟比較結(jié)束后標(biāo)記變量記錄的是所有數(shù)據(jù)中最小值的下標(biāo)。

（3）如果第一個(gè)數(shù)據(jù)不是最?。礃?biāo)記變量不等于第一個(gè)數(shù)的下標(biāo)）時(shí)，將最小值（下標(biāo)為標(biāo)記變量的數(shù)據(jù)）和第一個(gè)數(shù)據(jù)進(jìn)行交換。

（4）下一趟排序時(shí)待排序范圍為除了第一個(gè)數(shù)據(jù)以外的其他數(shù)據(jù)，按照第一趟方法排好第二個(gè)數(shù)據(jù)。

（5）以此類推，直到所有數(shù)據(jù)排好序。

問題描述：已知整型數(shù)組s中包含N個(gè)數(shù)組元素，應(yīng)用選擇排序算法，將數(shù)組中的數(shù)據(jù)按照升序排序。

算法分析：N個(gè)數(shù)排序時(shí)的排序趟數(shù)和排序次數(shù)與比較交換排序方法完全相同[5]。應(yīng)用C語(yǔ)言編寫的完整排序算法程序代碼如下：

#include"stdio.h"

#define N 10

void main()

{int s[N],i,j,t,loc;/*loc為記錄最小值下標(biāo)的標(biāo)記變量*/

for(i=0;i

for(i=1;i

{loc=i-1;/*假設(shè)待排序范圍內(nèi)的第一數(shù)據(jù)最小*/

for(j=i;j

if(s[loc]>s[j])/*如果loc記錄的不是最小值下標(biāo)*/

loc=j;/*修改假設(shè)*/

if(loc!=i-1)/*如果最小值不是待排序范圍內(nèi)的第一個(gè)數(shù)*/

/*將最小值置于待排序范圍內(nèi)第一個(gè)數(shù)的位置*/

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

}

for(i=0;i

}

算法解析：

（1）通過分析該算法可知，在最壞的情況下（原數(shù)據(jù)降序時(shí)），每次比較的數(shù)據(jù)對(duì)雖然都不滿足排序要求，但不需要進(jìn)行交換，當(dāng)該趟比較結(jié)束后進(jìn)行一次交換即可，大大提高了算法的效率。

（2）在程序中變量i的作用只是控制排序的趟數(shù)，取值可以從1到N-1，也可以從0到N-2，相應(yīng)的需要修改程序的其他部分。

4 結(jié)語(yǔ)

選擇排序算法是《C語(yǔ)言程序設(shè)計(jì)》課程中較難掌握的內(nèi)容之一，很多學(xué)生無法掌握甚至不能理解選擇排序算法，不僅阻礙了計(jì)算思維能力的培養(yǎng)，而且使得解決實(shí)際問題的能力受到了限制。通過介紹交換算法和比較交換排序思想，然后結(jié)合假設(shè)思想，使學(xué)生最終掌握選擇排序算法。通過選擇排序算法的學(xué)習(xí)，掌握由淺入深、循序漸進(jìn)和舉一反三的學(xué)習(xí)方法，并倡導(dǎo)學(xué)生在學(xué)習(xí)過程中重視思考，注重創(chuàng)新的探究精神。

[1]耿國(guó)華.數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述[M].西安:西安電子科技大學(xué)出版社,2006.

[2]梁文忠.一種基于直接選擇算法的改進(jìn)[J].廣西師范學(xué)院學(xué)報(bào):自然科學(xué)版,2004,21(4):93-96.

[3]張憶文,譚霽.簡(jiǎn)單選擇排序算法改進(jìn)及分析[J].硅谷,2009(18):77,94.

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

[5]何洪英.兩種排序算法的改進(jìn)[J].綿陽(yáng)師范學(xué)院學(xué)報(bào),2007,26(11):98-99.