利用c語言中兩種排序方法巧解排序難題

摘要：在c語言編程中，起泡排序和選擇排序是兩種常見的排序編程，教師應認識到這兩種排序編程的重要性、編程過程、特征和應用。

關鍵詞：起泡法；選擇法；排序

一、重要性分析

在c語言的教學中，起泡排序和選擇排序是教學重點，在c語言編程考核中，對這兩種排序的考核，也往往用來作為測量學習者水平高低的標準。

二、起泡法

用起泡法對10個數排序（由小到大）

1.算法分析

將相鄰兩個數比較，將小的調到前頭，大的調到后頭。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放后。然后比較第2個數和第3個數，將小數放前，大數放后，如此類推，直至比較最后兩個數，將小數放前，大數放后。至此第一趟結束，將最大的數放到了最后。在第二趟：仍從第一對數開始比較（因為可能由于第2個數和第3個數的交換，使得第1個數不再小于第2個數），將小數放前，大數放后，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數（其實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。

若有6個數：26 25 17 58 49 13

第一趟排序后結果：25 17 26 49 13 58

第二趟排序后結果：17 25 26 13 49 58

第三趟排序后結果：17 25 13 26 49 58

第四趟排序后結果：17 13 25 26 49 58

第五趟排序后結果：13 17 25 26 49 58

2.編程分析

#include

void main（ ）

{int a[10]；

int i，j，t；

printf（“input 10 numbers： ＼n”）；

for （i=0；i<10；i++）

scanf（“%d”，a[i]）；

printf（“＼n”）；

for （j=0；j<9；j++）

for （i=0；i<9-j；i++）

if （a[i]>a[i+1]）

{ t=a[i]；

a[i]=a[i+1]；

a[i+1]=t；

}

printf（“the sorted numbers： ＼n”）；

for （i=0；i<10；i++）

printf（“%d”，a[i]）；

printf（“＼n”）；

}

雙重循環部分是本程序的重點，要理清變量i，j，t的關系，其中i用來控制內循環的次數，并通過外循環變量j的增加，決定每趟循環的次數及最后一次交換后數組內的最大元素。

三、選擇法

用選擇法對10個數排序（由小到大）：

1.算法分析

n個記錄的文件的選擇排序，第1趟通過n-1次比較，從n個數中選擇出一個最小結果。

第i趟簡單選擇排序是指通過n-i次關鍵字的比較，從n-i+1個記錄中選出關鍵字最小的紀錄，并和第i個記錄進行交換。共需進行i-1趟比較，直到所有記錄排序完成為止。

若有6個數：26 25 17 58 49 13

第一趟排序后結果：[13] 26 25 58 49 17

第二趟排序后結果：[13] [17] 26 58 49 25

第三趟排序后結果：[13] [17] [25] 58 49 26

第四趟排序后結果：[13] [17] [25] [26] 58 49

第五趟排序后結果：[13] [17] [25] [26] [49] [58]

2.編程分析

#include

void main（ ）

{int a[10]；

int i，j，t；

printf（“input 10 numbers： ＼n”）；

for （i=0；i<10；i++）

scanf（“%d”，a[i]）；

printf（“＼n”）；

for （j=0；j<9；j++）

for （i=j+1；i<10；i++）

I if （a[j]>a[i]）

{t=a[i]；

a[i]=a[j]；

a[j]=t；

}

printf（“the sorted numbers： ＼n”）；

for （i=0；i<10；i++）

printf（“%d”，a[i]）；

printf（“＼n”）；

}

雙重循環部分是本程序的重點，要理清變量i，j，t的關系，其中i用來控制內循環的次數，通過外循環變量j的增加，決定每趟循環的次數，用j作為每趟選擇后最小值的存放。

四、起泡法和選擇法在實際問題中的應用

1.利用兩種排序法可以解決排序問題

起泡法和選擇法都可以對數據進行排序，兩種方法都應熟練掌握。

2.利用兩種排序方法的思想，可以解決最大值和最小值問題。來看兩個編程題：

（1）從鍵盤上任意輸入10個不相同的整數，請自動輸出最小值。

（2）從鍵盤上任意輸入10個不相同的整數，請自動輸出最大值。

問題1求最小值，我們只需使用選擇法，經過一趟比較就可以求出最小結果；問題2求最大值，使用上面起泡程序，略作修改便可完成編程。

參考文獻：

[1]譚浩強.c程序設計[M].清華大學出版社，2005.

[2]林東，陳林.編程語言基礎c語言[M].高等教育出版社，2007（12）.

（作者單位 江蘇省邳州市車輻中等專業學校）