黃逸

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

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

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

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

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

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

利用C語(yǔ)言描述選擇排序算法（從大至?。┑某绦虼a如下：

#include

int main（）

{

int i， j， k， N；

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

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

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

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

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

利用C語(yǔ)言描述改進(jìn)的選擇排序算法（從大至?。┑某绦虼a如下：

#include

int main（）

{

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

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

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

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

for（ i=0； i

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

for（i=0； i

{ k=i；

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

for（ j=i+1； j

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

{

b[p]=k；/*儲(chǔ)存上一次的最大數(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 并行排序的實(shí)驗(yàn)及分析

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

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

3 結(jié)語(yǔ)

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

[參考文獻(xiàn)]

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

[2]譚浩強(qiáng).C語(yǔ)言程序設(shè)計(jì)[M].4版.北京：清華大學(xué)出版社，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