陶圣哲

摘要：目前排序算法的應(yīng)用越來越廣泛，其目的是方便記錄的查找、插入及刪除。本文從算法時間復(fù)雜度、空間復(fù)雜度及穩(wěn)定性方面對冒泡排序、選擇排序、插入排序以及歸并排序進(jìn)行了分析，并通過對比實(shí)驗(yàn)，對比了四種算法在不同數(shù)據(jù)規(guī)模時的對比次數(shù)、移動次數(shù)、交換次數(shù)以及時間，通過分析得出在數(shù)據(jù)量較大時選擇歸并排序，數(shù)據(jù)量較小時可以選擇選擇排序，數(shù)據(jù)大部分有序時可以選擇插入排序的結(jié)論。

關(guān)鍵詞：排序算法；性能；復(fù)雜度

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）26-0026-04

1緒論

近幾年互聯(lián)網(wǎng)的發(fā)展速度越來越快，涉及的領(lǐng)域越來越廣，同時對計(jì)算機(jī)的性能要求也越來越高，基于目前硬件存儲性能的限制，科研人員一直致力于計(jì)算機(jī)性能的優(yōu)化，在目前的眾多方法中，排序算法的優(yōu)化及選擇是研究的重點(diǎn)，排序算法的性能優(yōu)劣直接影響到程序執(zhí)行的性能。排序算法目前廣泛應(yīng)用于各個行業(yè)領(lǐng)域，例如網(wǎng)站搜索的排序，推薦的先后等等，重要性不言而喻。排序算法是依照一種規(guī)則對數(shù)據(jù)位置進(jìn)行確定的算法，正是由于排序算法的重要性，人們對排序算法的研究從未停止，先后發(fā)明了適合于各種情況的排序算法。本文主要通過對幾種典型的排序算法進(jìn)行算法性能分析，通過算法執(zhí)行的時間效率、空間效率以及算法穩(wěn)定性對幾種算法進(jìn)行比較[1]。

2排序算法

排序算法數(shù)據(jù)處理規(guī)模的不同導(dǎo)致算法使用處理器的不同，一般將排序算法分為內(nèi)部排序和外部排序。內(nèi)部排序是指算法的整個處理過程完全在計(jì)算機(jī)內(nèi)存中進(jìn)行的排序算法，這是基于算法的數(shù)據(jù)估摸相對比較小，計(jì)算機(jī)內(nèi)存能夠滿足計(jì)算機(jī)讀取存儲的需求，本文重點(diǎn)討論的是內(nèi)部排序中的冒泡排序、選擇排序、插入排序、歸并排序四種排序算法。外部排序一般需要處理的數(shù)據(jù)比較大，計(jì)算機(jī)內(nèi)存無法滿足待排序?qū)ο蟮囊淮未鎯?，待排序記錄需要在?jì)算機(jī)內(nèi)部存儲器以及外部存儲器之間進(jìn)行切換來滿足數(shù)據(jù)量的要求，進(jìn)而實(shí)現(xiàn)對整個文件的排序[2]。

2.1冒泡排序

冒泡排序的基本思想是：通過不斷比較相鄰兩個數(shù)的大小，并進(jìn)行相應(yīng)的調(diào)整使得最后所有數(shù)據(jù)達(dá)到有序，之所以稱為冒泡排序是由于每一趟排序只比較出一個最大或最小的數(shù)出來，類似于冒泡。

具體排序過程如下：

1）在進(jìn)行首次排序過程時將第一個數(shù)與第二個數(shù)比較，小數(shù)在前大數(shù)在后，之后是第二個數(shù)據(jù)和第三個數(shù)據(jù)按照相同的方式進(jìn)行比較，同時按照小數(shù)在前大數(shù)在后的規(guī)則進(jìn)行調(diào)整次序，不斷進(jìn)行比較交換調(diào)整直至最后兩個數(shù)比較完畢最大的數(shù)據(jù)在最后一個，此時第一趟比較結(jié)束。

2）之后進(jìn)行第二次排序，從第一個數(shù)據(jù)按照第一趟排序的規(guī)則依次比較排序直至倒數(shù)第二個數(shù)比較完畢，此時第二大的數(shù)據(jù)在倒數(shù)第二的位置。

3）之后按照相同的規(guī)則進(jìn)行比較直到最后只剩下一個數(shù)據(jù)，此時排序完成。

冒泡排序算法的程序如下所示：

void paixu：：bubblesort（int r[]，long m，long n）

{for（i=m；i<=n-1；i++）

{for（j=n；j>=i+1；j--）

{if（r[j]

{temp=r[j]；

r[j]=r[j-1]； //交換

r[j-1]=temp；

exchanges=1；

exchange++；}}

if（exchanges==0） //本趟無交換發(fā)生，則結(jié)束

return；}}

如果冒泡排序初始的數(shù)據(jù)所有的記錄按照關(guān)鍵字有序的序列的話此時是最好的情況，只需進(jìn)行一次冒泡，進(jìn)行n-1次比較便可完成排序，由于所有記錄均是關(guān)鍵字有序所以不需要進(jìn)行移動，時間復(fù)雜度O（n）；如果初始的正好相反所有的記錄按照關(guān)鍵字有序的序列的話此時是最壞的情況需進(jìn)行n-1趟冒泡，比較的次數(shù)n（n-1）/2，移動的次數(shù)是3n（n-1）/2，時間復(fù)雜度O（n2）。冒泡排序的空間復(fù)雜度并不隨著處理數(shù)據(jù)量n的大小而改變，為O（1）。

2.2選擇排序

選擇排序的基本思想是：選擇排序的主要排序方式是通過選擇進(jìn)行完成的。在初始待排序的數(shù)據(jù)中找到最小的數(shù)據(jù)，并把它和初始數(shù)據(jù)中第一個位置的數(shù)據(jù)進(jìn)行交換，同時在剩余的所有數(shù)據(jù)中按照相同的方法找到最小的數(shù)據(jù)與初始數(shù)據(jù)中第二個位置的數(shù)據(jù)進(jìn)行比較，按照這種方式對余下的數(shù)據(jù)進(jìn)行排序直到所有的數(shù)據(jù)排序完成，算法結(jié)束。

具體的排序過程如下所示：

1）在第一次排序過程中，從所有的m個數(shù)sort[0]-sort[m-1]中找到最小的數(shù)sort[i]，并將sort[i]于sort[1]進(jìn)行交換。

2）在第二次排序過程中，從剩余的sort[1]-sort[m-1]中再次找到最小的數(shù)sort[i]，并將sort[i]于sort[2]進(jìn)行交換。

3）在第j次排序過程中，從剩余的sort[j-1]-sort[m-1]中再次找到最小的數(shù)sort[i]，并將sort[i]于sort[j-1]進(jìn)行交換。

4）直到所有數(shù)據(jù)均有序，算法結(jié)束。

選擇排序算法的程序如下所示：

void paixu：：selectsort（int r[]，long m，long n）

{for（i=m；i<=n-1；i++）

{k=i；

for（j=i+1；j<=n；j++）

{if（r[j]

temp=r[i]； //將r[k]和r[i]交換

r[i]=r[k]；

r[k]=temp；}}

通過選擇排序的代碼可以看出，選擇排序的執(zhí)行過程是兩個for循環(huán)的查找過程，第一個過程是查找最小元素，第二個過程是m次循環(huán)過程，所以時間復(fù)雜度是O（n2），所需進(jìn)行的關(guān)鍵字間的比較次數(shù)是n（n-1）/2，移動記錄的次數(shù)，最小值為0，最大值為3（n-1） 。選擇排序的空間復(fù)雜度并不隨著處理數(shù)據(jù)量n的大小而改變，為O（1）。

2.3插入排序

這里以希爾插入排序?yàn)槔柌迦肱判蚴菍€性插入排序的一種改進(jìn)，又稱為縮小增量排序。希爾排序的基本思想是：對于一個記錄數(shù)是m的待排序數(shù)據(jù)，首先選擇一個增量dis1

具體的排序過程如下所示：

1）首先選取距離增量dis1，距離增量的初值小于記錄數(shù)，之后以距離增量作為數(shù)據(jù)之間的距離，使得相同距離增量的數(shù)據(jù)分為同一組，并進(jìn)行直接插入排序。

2）在上面排序結(jié)果的基礎(chǔ)之后選擇距離增量dis2，dis2增量的選取可以參照經(jīng)典的二分法，向下取整二分dis1，按照步驟1的方式進(jìn)行組內(nèi)插入排序。

3）按照相同的距離增量選擇原則進(jìn)行排序直到距離增量為取值為1，此時相當(dāng)于對一組數(shù)據(jù)進(jìn)行直接插入排序，排序完成數(shù)據(jù)有序，算法結(jié)束。

希爾排序算法的程序如下所示：

void paixu：：shellsort（int r[]，long m，long n）

{gap=（n-m+1）/2； //增量的初值為n/2

while（gap>0）

{for（i=gap+1；i<=n；i++）

{j=i-gap；

while（j>m-1）

{ if（r[j]>r[j+gap]） //交換r[j]和r[j+gap]

{temp=r[j]；

r[j]=r[j+gap]；

r[j+gap]=temp；

j=j-gap；}

else j=m-1； //通過給j賦值而退出while循環(huán)}}

gap=gap/2； //減小增量

}}

希爾排序是直接插入排序的改進(jìn)，在性能上要優(yōu)于直接插入排序。在希爾排序算法中如果初始的數(shù)據(jù)所有的記錄按照關(guān)鍵字有序的序列的話此時是最好的情況，移動的次數(shù)為0，比較的次數(shù)在n～ n2之間；如果初始的數(shù)據(jù)所有的記錄按照關(guān)鍵字逆序的序列的話此時是最壞的情況，移動次數(shù)和比較次數(shù)接近n2，但是在平均情況下希爾排序的比較次數(shù)和移動次數(shù)好于直接插入排序，為O（n1.3）左右。選擇排序的空間復(fù)雜度并不隨著處理數(shù)據(jù)量n的大小而改變，為O（1）。

2.4歸并排序

歸并排序采用的是分治思想，是將兩個或多個有序序列合并成一個有序序列的過程。

具體的排序過程如下所示：

1）初始時，將每個記錄看成一個單獨(dú)的有序序列，則n個待排序記錄就是n個長度為1的有序子序列；

2）對所有有序子序列進(jìn)行兩兩歸并，得到n/2個長度為2或1的有序子序列；

3）重復(fù)步驟2，直到得到長度為n的有序序列為止。

void paixu：：sortmerge（int a[]，long p1，long p2，int b[]）

{//二路歸并排序，將a[p1]～a[p2]中的元素排序，結(jié)果在b[0]～b[p2-p1]中

while（len

{mmergesort（a，p1，p2，len，b）；

len=len*2；

mmergesort（b，0，p2-p1，len，a+p1）；}}

void paixu：：merge（int a[]，long s，long m，long n，int b[]）

{while（i<=m&&j<=n）

{ if（a[i]<=a[j]）b[k++]=a[i++]；

else b[k++]=a[j++]；}

while（i<=m）{b[k++]=a[i++]； }

while（j<=n）{b[k++]=a[j++]；}

return；}

具有n個待排序記錄的歸并次數(shù)是㏒2n，而一趟歸并的時間復(fù)雜度為O（n），則整個歸并排序的時間復(fù)雜度無論是最好還是最壞情況均為O（n㏒2n）。在排序過程中，使用了輔助向量DR，大小與待排序記錄空間相同，則空間復(fù)雜度為O（n）。歸并排序是穩(wěn)定的，歸并排序的排序的空間復(fù)雜度和處理數(shù)據(jù)的規(guī)模n相關(guān)，為O（n）。

3實(shí)驗(yàn)驗(yàn)證

為了對比四種排序算法的性能，論文通過C++實(shí)現(xiàn)了一個驗(yàn)證程序。通過對比排序算法的交換次數(shù)、比較次數(shù)、移動次數(shù)以及排序時間來進(jìn)一步分析算法性能。通過rand（）函數(shù)模擬產(chǎn)生1000、4000、7000、10000、15000、30000不同規(guī)模的數(shù)據(jù)。

待排序數(shù)量是1K，4K，7K，10K，15K，30K時四種算法執(zhí)行過程對應(yīng)的交換次數(shù)如表1所示。

從表中可以看出插入排序以及歸并排序并不進(jìn)行交換，冒泡排序的交換次數(shù)規(guī)模是最大的，選擇排序交換次數(shù)和算法數(shù)據(jù)規(guī)模基本相當(dāng)。

待排序數(shù)量是1K，4K，7K，10K，15K，30K時四種算法執(zhí)行過程進(jìn)行的比較次數(shù)如表2所示。

從表2中可以看出冒泡排序以及選擇排序的比較次數(shù)基本相同，插入排序以及歸并排序的比較次數(shù)基本是比較少的。

待排序數(shù)量是1K，4K，7K，10K，15K，30K時四種算法執(zhí)行過程進(jìn)行的移動次數(shù)如表3所示。

從表3中可以看出冒泡排序以及選擇排序并不進(jìn)行移動，插入排序的移動次數(shù)規(guī)模是最大的，并且隨著數(shù)據(jù)規(guī)模的增大增長速度也在變快，歸并排序的移動次數(shù)相對較小。

待排序數(shù)量是1K，4K，7K，10K，15K，30K時四種算法執(zhí)行過程進(jìn)行的時間對比如表4所示。

從表4中可以看出當(dāng)數(shù)據(jù)規(guī)模小于15K的時候，四種算法的耗時相對比較平穩(wěn)，選擇排序與插入排序耗時差別不大，冒泡排序相對較多，歸并排序耗時相對其他三種算法不是一個數(shù)量級，數(shù)據(jù)規(guī)模大于15K時，歸并排序的耗時基本變化不大，冒泡排序、選擇排序以及插入排序的耗時成指數(shù)增長。

4性能分析

通過上述對冒泡排序、選擇排序、插入排序以及歸并排序算法的實(shí)驗(yàn)性能對比，并通過分析，列出表4.1中的性能對比。

其中整體來說在數(shù)據(jù)量比較大時歸并算法的時間復(fù)雜度最低，但是以犧牲空間復(fù)雜度為代價的，插入排序和冒泡排序在數(shù)據(jù)初始正序時的時間復(fù)雜度較小，平均情況下插入排序和歸并排序的時間復(fù)雜度較小，綜上分析可以看出選擇排序不穩(wěn)定，冒泡排序、插入排序以及歸并排序是穩(wěn)定的。冒泡排序以及選擇排序適合于數(shù)據(jù)量比較小的情況，歸并排序適合數(shù)據(jù)量比較大的情況。

5結(jié)論

不同排序算法性能各有優(yōu)劣，在選擇排序算法時要綜合排序算法的時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性、適合的數(shù)據(jù)規(guī)模等各種因素。通過本文可以得出在數(shù)據(jù)量較大時選擇歸并排序，數(shù)據(jù)量較小時可以選擇選擇排序，數(shù)據(jù)大部分有序時可以選擇插入排序。

由于本文只對冒泡排序、選擇排序、插入排序以及歸并排序四種典型的排序算法進(jìn)行分析討論，從而有一定的局限性，后續(xù)應(yīng)對更多排序算法的性能進(jìn)行分析比較。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1997：263-289.

[2] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2007：21-25.