選擇排序算法的分析與改進(jìn)

熊英++吳尚宇

摘 要 排序算法在商業(yè)數(shù)據(jù)處理及現(xiàn)代科學(xué)計算中扮演著十分重要的角色，其中選擇排序是其中最簡單的算法之一。傳統(tǒng)的選擇排序是進(jìn)行n次選擇，每次選擇均從待排序部分選取最?。ù螅┑脑嘏c待排序部分的第一個元素交換。相比而言，改進(jìn)后的算法盡可能減少了比較的次數(shù)，提高算法的效率，并降低了最好情況下的時間復(fù)雜度。

【關(guān)鍵詞】選擇排序 雙向排序 效率 時間復(fù)雜度

1 傳統(tǒng)的選擇排序算法

傳統(tǒng)的選擇排序算法有兩個很好的性質(zhì)，即：

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

（2）數(shù)據(jù)的交換次數(shù)是所有排序算法中最小的：傳統(tǒng)算法的交換次數(shù)是線性的。

1.1 傳統(tǒng)選擇排序思路

以從小到大排序為例：

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

……

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

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

1.2 算法分析

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

2 改進(jìn)的選擇排序算法

針對傳統(tǒng)排序算法中的每一次選擇，可以發(fā)現(xiàn)每一次選擇只能確定一個優(yōu)先級最高的元素的位置，而實際上在一次選擇的循環(huán)中，不僅僅可以確定優(yōu)先級最高的元素位置，同時也可以確定優(yōu)先級最低的元素位置。

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

2.1 算法思路

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

……

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

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

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

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

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

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

2.2 算法分析

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

3 算法之再改進(jìn)

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

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

例如對實驗數(shù)據(jù)[9 3 5 6 8 1]進(jìn)行排序的過程：

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

第二步：預(yù)判待排序部分為有序，排序結(jié)束。

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

3.1 算法分析

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

4 代碼實現(xiàn)

本文中就不再實現(xiàn)傳統(tǒng)的選擇排序算法代碼，以下為再改進(jìn)后的選擇排序算法代碼實現(xiàn)：

voidNewSelectSort（）{

for（inti=0；i

boolisordered=true；

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

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 三種選擇排序的比較

對三種選擇排序的時間復(fù)雜度進(jìn)行比較：

（1）傳統(tǒng)選擇排序：最好情況時間復(fù)雜度：O（n2），最壞情況時間復(fù)雜度：O（n2）。

（2）改進(jìn)選擇排序：最好情況時間復(fù)雜度：O（n2），最壞情況時間復(fù)雜度：O（n2）。

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

6 結(jié)語

文章采用雙向排序的方法對傳統(tǒng)的選擇排序算法進(jìn)行了效率上的提高，并且結(jié)合冒泡排序的思路，對選擇排序的最好的情況下的時間復(fù)雜度進(jìn)行了優(yōu)化，均c/c++語言實現(xiàn)了上述算法，通過大量的實驗數(shù)據(jù)證明上述算法的正確性和可行性。

參考文獻(xiàn)

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

[2]嚴(yán)蔚敏，陳文博.數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程[M].北京：清華大學(xué)出版社，2011.

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

作者單位

華中師范大學(xué)計算機(jī)學(xué)院 湖北省武漢市 430079