選擇排序算法的分析與改進

熊英++吳尚宇

摘 要 排序算法在商業數據處理及現代科學計算中扮演著十分重要的角色，其中選擇排序是其中最簡單的算法之一。傳統的選擇排序是進行n次選擇，每次選擇均從待排序部分選取最小（大）的元素與待排序部分的第一個元素交換。相比而言，改進后的算法盡可能減少了比較的次數，提高算法的效率，并降低了最好情況下的時間復雜度。

【關鍵詞】選擇排序 雙向排序 效率 時間復雜度

1 傳統的選擇排序算法

傳統的選擇排序算法有兩個很好的性質，即：

（1）運行時間對原始輸入數據不敏感：每一次選擇都是獨立的，不受前一次選擇的影響也不對后一次的選擇提供相關信息。

（2）數據的交換次數是所有排序算法中最小的：傳統算法的交換次數是線性的。

1.1 傳統選擇排序思路

以從小到大排序為例：

第一步：在1～n個數中找到最小數，與第1個數交換，前1個數已排好；

……

第k步：在k～n個數中找到最小數，與第k個數交換，前k個數已排好；

第n-1步：在n-1到n個數中找到最小數，然后與第n-1個數交換，排序結束。

1.2 算法分析

時間復雜度：通過對上面代碼的分析，研究排序的軌跡，可以知道對每一個i從0到n-1，都有1次交換和n-1-i次比較，所以總共有n次交換和（n-1）+（n-2）+（n-3）+…+2+1+0=n（n-1）/2～n2/2次比較，因此時間復雜度為O（n2）。

2 改進的選擇排序算法

針對傳統排序算法中的每一次選擇，可以發現每一次選擇只能確定一個優先級最高的元素的位置，而實際上在一次選擇的循環中，不僅僅可以確定優先級最高的元素位置，同時也可以確定優先級最低的元素位置。

由此可得出改進后的選擇排序算法：數組的中間部分為待排序部分，兩邊均為已排序部分，每一次選擇從待排序部分選擇優先級最高和最低的兩個元素的位置，分別將該兩個元素與待排序部分的首部和尾部進行交換（交換的順序需要特別考慮），由此即實現了雙向排序。這樣與傳統的選擇排序相比，比較次數減少了近1/2。

2.1 算法思路

第一步：從1～n個數中同時找到最小數和最大數，將它們分別與第1個數和第n個數交換；

……

第k步：從k～n-k+1個數中同時找到最小數和最大數，將它們分別與第k個數和第n-k+1個數交換；

第n/2步：從n/2～（n/2）+1個數中同時找到最小數和最大數，將它們分別與第n/2個數和第（n/2）+1個數交換，排序結束。

例如對實驗數據[10 3 4 7 1 2]的排序過程如下：

第一步：1[3472]10：6個數中1最小，10最大，分別與第1個數和第6個數交換。

第二步：1 2 [4 3] 7 10：4個數中2最小，7最大，分別與第2個數和第5個數交換。

第三步：1 2 3 4 7 10：2個數中3最小，4最大，分別與第3個數和第4個數交換。

2.2 算法分析

時間復雜度：從改進后的算法中，仍研究排序的軌跡，可知交換次數沒有改變，仍為n，但比較的次數減少了一半，為n（n-1）/4，提高了效率，但是由于在同一個數量級，時間復雜度仍為O（n2）。

3 算法之再改進

在算法2的基礎上再對算法進行改進：由傳統的選擇排序算法的兩個性質可得，可以對算法進行改進，增強其對原始輸入數據敏感性。在最優的情況下，即輸入數據有序，選擇排序仍需要進行相同數量級的比較，這大大降低了選擇排序的效率。再改進的選擇排序算法結合冒泡排序的思路，在每一次選擇交換之前，對待排序部分進行預判：若待排序部分已有序，則結束排序。

預判操作為：比較前一個元素和后一個元素的優先級，如果待排序部分中前一個元素的優先級均高（低）于后一個元素，則認為待排序部分有序。由此分析可知，改進后的選擇排序最優時間復雜度為O（n）。

例如對實驗數據[9 3 5 6 8 1]進行排序的過程：

第一步：1 [3 5 6 8] 9：預判待排序部分為亂序，進行選擇排序。6個數中1最小，9最大，分別與第1個數和第6個數交換。

第二步：預判待排序部分為有序，排序結束。

由此可見，再改進的選擇排序算法對原始輸入數據的敏感性已得到大幅提升。

3.1 算法分析

時間復雜度：該算法與改進后的算法相比，最好情況下的時間復雜度為O（n），最壞情況下為O（n2）。

4 代碼實現

本文中就不再實現傳統的選擇排序算法代碼，以下為再改進后的選擇排序算法代碼實現：

voidNewSelectSort（）{

for（inti=0；i

boolisordered=true；

for（int j=i；j<=n-i-1；j++）{//預判

if（a[j]>a[j+1]）{

isordered=false；

break；

}

}

if（isordered）break；

int min=i，max=n-i–1；

if（a[min]>a[max]）swap（a[min]，a[max]）；

for（int j=i；j<=n-i-1；j++）//雙向選擇排序

if（a[min]>a[j]）min=j；

else if（a[max]

swap（a[i]，a[min]）；

swap（a[n–i–1]，a[max]）；

}

}

5 三種選擇排序的比較

對三種選擇排序的時間復雜度進行比較：

（1）傳統選擇排序：最好情況時間復雜度：O（n2），最壞情況時間復雜度：O（n2）。

（2）改進選擇排序：最好情況時間復雜度：O（n2），最壞情況時間復雜度：O（n2）。

（3）再改進選擇排序：最好情況時間復雜度：O（n2），最壞情況時間復雜度：O（n）。

6 結語

文章采用雙向排序的方法對傳統的選擇排序算法進行了效率上的提高，并且結合冒泡排序的思路，對選擇排序的最好的情況下的時間復雜度進行了優化，均c/c++語言實現了上述算法，通過大量的實驗數據證明上述算法的正確性和可行性。

參考文獻

[1]Robert，S，& Kevin，W（2013）. Algorithms[M].北京：人民郵電出版社出版發行，2010.

[2]嚴蔚敏，陳文博.數據結構及應用算法教程[M].北京：清華大學出版社，2011.

[3]何洪英.雙向選擇排序算法的實現及性能研究[J].成功（教育），2007.

作者單位

華中師范大學計算機學院 湖北省武漢市 430079