循序漸進學習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.