4.3　選擇排序算法

選擇排序（Selection Sort）算法也是比較簡(jiǎn)單的排序算法，其思路比較直觀。選擇排序算法在每一步中選取最小值來(lái)重新排列，從而達(dá)到排序的目的。

4.3.1　選擇排序算法

選擇排序算法通過選擇和交換來(lái)實(shí)現(xiàn)排序，其排序流程如下：

（1）首先從原始數(shù)組中選擇最小的1個(gè)數(shù)據(jù)，將其和位于第1個(gè)位置的數(shù)據(jù)交換。

（2）接著從剩下的n-1個(gè)數(shù)據(jù)中選擇次小的1個(gè)數(shù)據(jù)，將其和第2個(gè)位置的數(shù)據(jù)交換。

（3）然后不斷重復(fù)上述過程，直到最后兩個(gè)數(shù)據(jù)完成交換。至此，便完成了對(duì)原始數(shù)組的從小到大的排序。

為了更好地理解選擇排序算法的執(zhí)行過程，下面舉一個(gè)實(shí)際數(shù)據(jù)的例子來(lái)一步一步地執(zhí)行選擇排序算法。5個(gè)整型數(shù)據(jù)118、101、105、127、112是一組無(wú)序的數(shù)據(jù)。對(duì)其執(zhí)行選擇排序過程，如圖4-4所示。

選擇排序算法的執(zhí)行步驟如下：

（1）第1次排序，從原始數(shù)組中選擇最小的數(shù)據(jù)，這個(gè)數(shù)據(jù)便是101，將其與第1個(gè)數(shù)據(jù)118進(jìn)行交換。此時(shí)排序后的數(shù)據(jù)為101、118、105、127、112。

（2）第2次排序，從剩余的數(shù)組中選擇最小的數(shù)據(jù)，這個(gè)數(shù)據(jù)便是105，將其與第2個(gè)數(shù)據(jù)118進(jìn)行交換。此時(shí)排序后的數(shù)據(jù)為101、105、118、127、112。

（3）第3次排序，從剩余的數(shù)組中選擇最小的數(shù)據(jù)，這個(gè)數(shù)據(jù)便是112，將其與第3個(gè)數(shù)據(jù)118進(jìn)行交換。此時(shí)排序后的數(shù)據(jù)為101、105、112、127、118。

（4）第4次排序，從剩余的數(shù)組中選擇最小的數(shù)據(jù)，這個(gè)數(shù)據(jù)便是118，將其與第4個(gè)數(shù)據(jù)127進(jìn)行交換。此時(shí)排序后的數(shù)據(jù)為101、105、112、118、127。

從上面的例子可以非常直觀地了解到選擇排序算法的執(zhí)行過程。選擇排序算法在對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序時(shí)，無(wú)論原數(shù)據(jù)有無(wú)順序，都需要進(jìn)行n-1步的中間排序。這種排序方法思路很簡(jiǎn)單直觀，但是缺點(diǎn)是執(zhí)行的步驟稍長(zhǎng)，效率不高。

選擇排序算法的示例代碼如下：

在上述代碼中，輸入?yún)?shù)a一般為一個(gè)數(shù)組的首地址。待排序的原數(shù)據(jù)便保存在數(shù)組a中，程序中通過兩層循環(huán)來(lái)對(duì)數(shù)據(jù)進(jìn)行選擇排序。讀者可以結(jié)合前面的選擇排序算法來(lái)加深理解。這里，為了讓讀者清楚排序算法的執(zhí)行過程，在排序的每一步都輸出了當(dāng)前的排序結(jié)果。

4.3.2　選擇排序算法實(shí)例

學(xué)習(xí)了前面的選擇排序算法的基本思想和算法之后，下面通過一個(gè)完整的例子來(lái)說(shuō)明選擇排序法在整型數(shù)組排序中的應(yīng)用，程序示例如下：

【程序4-2】

在上述代碼中，程序定義了符號(hào)常量SIZE，用于表征需要排序整型數(shù)組的大小。在主方法中，首先聲明一個(gè)整型數(shù)組，然后對(duì)數(shù)組進(jìn)行隨機(jī)初始化，并輸出排序前的數(shù)組內(nèi)容。接著，調(diào)用選擇排序算法方法來(lái)對(duì)數(shù)組進(jìn)行排序。最后，輸出排序后的數(shù)組。

該程序的執(zhí)行結(jié)果，如圖4-5所示。圖中顯示了每一步排序的中間結(jié)果。