選擇排序算法的改進與應用

黃逸

摘 要：選擇排序是內部排序算法中的一種，在每一輪目標元素（最大值或最小值）的確定過程中，有關的比較運算結果并沒有得到很好的利用。針對上述問題，文章提出了一種改進的選擇排序算法，新算法利用臨時數組儲存比較運算中的有價值信息，在此基礎上，提前完成有關的元素交換。實驗表明，改進的選擇排序算法計算效能有了一定的提升。

關鍵詞：選擇排序；內部排序；數組

排序就是將一個數據元素集合或序列重新排列成一個按某項值有序的序列，通常是按照某種規則把數據的順序重新整理，排序在計算機的信息處理過程中有著極為重要的應用。一般地說，根據待排序元素能否一次性地在內存中完成所有的排序任務，可以把排序算法分為內部排序和外部排序。內部排序無需對外存進行訪問，根據不同的原則對內部排序進行分類，大致可分為插入排序、交換排序、選擇排序、歸并排序和計數排序共五大類[1]。為了改善現有的選擇排序算法的計算效能，設計實現了一種改進的選擇排序算法，理論分析和實驗過程均表明了改進算法的正確性和有效性。

1 改進的選擇排序算法的設計與實現

1.1 選擇排序算法的效率分析

與冒泡排序一樣，選擇排序的核心工作也是元素之間的比較和交換。冒泡排序與選擇排序的元素比較次數是相同的，但由于選擇排序的元素交換次數比冒泡排序少，所以選擇排序的執行效率更為高效[2]。

利用C語言描述選擇排序算法（從大至小）的程序代碼如下：

#include

int main（）

{

int i， j， k， N；

printf（"請輸入待排序序列的元素個數＼n"）；

scanf（"%d"， &N;）；

float a[N] ，temp；

for（ i=0； i

for（i=0； i

{ k=i；

for（ j=i+1； j

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

if（ i ！= k）

{ temp=a[i]； a[i]=a[k]； a[k]=temp；}

}

for（ i=0； i

}

如上述程序所示，選擇排序算法的工作原理是：第一輪從所有N個數中選出最大的數，即先將a[0]與后面的各個元素a[j]進行比較，凡是遇到比a[0]大的數就記下它的位置j，經過一輪比較（共N-1次）后，最大的數就能被挑選出來，最后可將它與a[0]交換位置。于是，經過第一輪的比較之后，最大數就存放在a[0]中；第二輪從余下的N-1個數中選出最大的數存放在a[1]中，即將a[1]與后面的各個元素a[j]進行比較，凡是遇到比a[1]大的數就記下它的位置j，經過這一輪比較（共N-2次）后，次大的數就能被挑選出來，將它與a[1]進行交換；以此類推，到N-1輪時，可把所剩余兩個數中的較大數存放在a[N-2]、而較小數則存放在a[N-1]中。

下面結合某一序列的排序過程，說明選擇排序算法所存在的效率問題。如表1所示，待排序序列的元素共有10個，因此，第一輪需進行9次比較，而記錄最大數位置的j變量共發生了3次變更，最終的結果是完成了a[0]與a[8]的數據交換操作。根據選擇排序算法的工作原理可以得知：除了完成最終的數據交換操作之外，一些有價值的比較信息（如記錄最大數位置的變更信息“j=0→j=1”和“j=1→j=4”）卻被丟棄掉。

1.2 選擇排序算法的改進設計

如前所述，對某一排序任務而言，冒泡排序與選擇排序所執行的比較運算次數是相同的，但由于在排序過程中后者對元素的交換次數遠小于前者，故選擇排序具有更高的效率。受這一思想的啟發，可以利用各輪次已掌握的最大數位置變更信息對有關的元素進行交換，以便提前完成各元素的數據交換[3]。仍然以表1的第一輪排序任務為例，首先利用臨時數組儲存有關最大數發生變更的位置信息（如j={1，4}），在完成a[0]=a[8]old的基礎上，依次地對發生位置變更的元素進行相應的元素交換，即a[1]=a[4]old、a[4]=a[1]old。依照上述改進思路對表1的排序任務重新排序，得到如表2所示的結果。

對比表1和表2，不難發現，改進的選擇排序算法在第一輪次中便完成了a[1]元素的排序。由于改進的選擇排序算法能提前完成各元素的數據交換，于是為提前結束輪次排序提供了可能。

利用C語言描述改進的選擇排序算法（從大至小）的程序代碼如下：

#include

int main（）

{

int i， j， k， p，q，u，v，N，sum；

printf（"請輸入待排序序列的元素個數＼n"）；

scanf（"%d"， &N;）；

float a[N]，b[N] ，temp；

for（ i=0； i

sum=0；/*用于儲存元素交換的次數*/

for（i=0； i

{ k=i；

p=0；/*用于儲存最大數位置變更的次數*/

for（ j=i+1； j

if（ a[j] < a[k]）

{

b[p]=k；/*儲存上一次的最大數位置變更位置*/

p=p+1；/*最大數位置變更的次數增1*/

k=j；

}

if（ i ！= k）；/*記錄最大數的位置信息發生變更*/

{

for（q=0；q

{

sum=sum+1；

if （q！=p）

{ u=b[q]；v=b[p-q-1]；

temp=a[u]； a[u]=a[v]； a[v]=temp；

}

else

{temp=a[i]； a[i]=a[k]； a[k]=temp；}

}

}

else

{

if（sum>N）/*提前結束選擇排序*/

{

for（ j=i+1； j

{

if（ a[j] < a[j+1]） break；

}

if（j=N） break；

}

}

}

for（ i=0； i

}

2 并行排序的實驗及分析

實驗的硬件環境是：Intel core i5-6600K四核CPU、DDR4 2133 MHz 16 GB RAM、金士頓SUV400S37/240G固態硬盤；軟件環境為：Windows 7專業版64位、Microsoft visual studio 2015 C++；實驗中需要進行對比的算法有冒泡排序算法、選擇排序算法和改進的選擇排序算法。實驗過程中，用rand（）函數隨機產生一個長度為100的實數序列，然后分別用上述3種算法對該序列中的元素進行排序；實驗重復1 000次，取平均計算耗時作為度量各種算法的效能。具體的實驗結果如圖1所示。

從圖1可以發現，冒泡排序算法所需的計算耗時最多、選擇排序算法次之，而改進的選擇排序算法為最小。事實上，由于改進的選擇排序算法充分利用了各輪次的既有比較信息，為提前結束選擇排序提供了條件，因而較選擇排序算法而言，減少了近22.53%計算耗時的開銷。

3 結語

排序算法在信息處理的過程中有著重要的地位，一些經典的排序算法存在結構簡單和易于使用的優點，但在執行效率上仍然需要改進。以選擇排序算法為例，通過對各輪次的記錄最大數位置的變更信息進行處理，設計實現了一種改進的選擇排序算法，實驗驗證了改進算法的正確性和有效性。

[參考文獻]

[1]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，2007.

[2]譚浩強.C語言程序設計[M].4版.北京：清華大學出版社，2010.

[3]彭軍，向毅.數據結構與算法[M].北京：人民郵電出版社，2013.

Abstract：Selection sort is a kind of internal sorting algorithm. In the process of determining the target element（maximum or minimum）in each round， the results of comparison operation are not well utilized. In order to solve the above problems， an improved selection sorting algorithm is proposed in this paper， which uses a temporary array to store valuable information in the comparison operation. Experimental results show that the computational efficiency of the improved algorithm has been improved.

Key words：selection sort； internal sorting； array