選擇排序算法的改進與應(yīng)用

黃逸

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

關(guān)鍵詞：選擇排序；內(nèi)部排序；數(shù)組

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

1 改進的選擇排序算法的設(shè)計與實現(xiàn)

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

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

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

#include

int main（）

{

int i， j， k， N；

printf（"請輸入待排序序列的元素個數(shù)＼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個數(shù)中選出最大的數(shù)，即先將a[0]與后面的各個元素a[j]進行比較，凡是遇到比a[0]大的數(shù)就記下它的位置j，經(jīng)過一輪比較（共N-1次）后，最大的數(shù)就能被挑選出來，最后可將它與a[0]交換位置。于是，經(jīng)過第一輪的比較之后，最大數(shù)就存放在a[0]中；第二輪從余下的N-1個數(shù)中選出最大的數(shù)存放在a[1]中，即將a[1]與后面的各個元素a[j]進行比較，凡是遇到比a[1]大的數(shù)就記下它的位置j，經(jīng)過這一輪比較（共N-2次）后，次大的數(shù)就能被挑選出來，將它與a[1]進行交換；以此類推，到N-1輪時，可把所剩余兩個數(shù)中的較大數(shù)存放在a[N-2]、而較小數(shù)則存放在a[N-1]中。

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

1.2 選擇排序算法的改進設(shè)計

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

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

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

#include

int main（）

{

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

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

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

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

for（ i=0； i

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

for（i=0； i

{ k=i；

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

for（ j=i+1； j

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

{

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

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

k=j；

}

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

{

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）/*提前結(jié)束選擇排序*/

{

for（ j=i+1； j

{

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

}

if（j=N） break；

}

}

}

for（ i=0； i

}

2 并行排序的實驗及分析

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

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

3 結(jié)語

排序算法在信息處理的過程中有著重要的地位，一些經(jīng)典的排序算法存在結(jié)構(gòu)簡單和易于使用的優(yōu)點，但在執(zhí)行效率上仍然需要改進。以選擇排序算法為例，通過對各輪次的記錄最大數(shù)位置的變更信息進行處理，設(shè)計實現(xiàn)了一種改進的選擇排序算法，實驗驗證了改進算法的正確性和有效性。

[參考文獻]

[1]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學出版社，2007.

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

[3]彭軍，向毅.數(shù)據(jù)結(jié)構(gòu)與算法[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