幾種典型內(nèi)部排序算法性能分析

陶圣哲

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

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

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

1緒論

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

2排序算法

排序算法數(shù)據(jù)處理規(guī)模的不同導(dǎo)致算法使用處理器的不同，一般將排序算法分為內(nèi)部排序和外部排序。內(nèi)部排序是指算法的整個(gè)處理過程完全在計(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)對整個(gè)文件的排序[2]。

2.1冒泡排序

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

具體排序過程如下：

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

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

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

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

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

2.2選擇排序

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

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

1）在第一次排序過程中，從所有的m個(gè)數(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í)行過程是兩個(gè)for循環(huán)的查找過程，第一個(gè)過程是查找最小元素，第二個(gè)過程是m次循環(huán)過程，所以時(shí)間復(fù)雜度是O（n2），所需進(jìn)行的關(guān)鍵字間的比較次數(shù)是n（n-1）/2，移動(dòng)記錄的次數(shù)，最小值為0，最大值為3（n-1） 。選擇排序的空間復(fù)雜度并不隨著處理數(shù)據(jù)量n的大小而改變，為O（1）。

2.3插入排序

這里以希爾插入排序?yàn)槔?，希爾插入排序是對線性插入排序的一種改進(jìn)，又稱為縮小增量排序。希爾排序的基本思想是：對于一個(gè)記錄數(shù)是m的待排序數(shù)據(jù)，首先選擇一個(gè)增量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，此時(shí)相當(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í)是最好的情況，移動(dòng)的次數(shù)為0，比較的次數(shù)在n～ n2之間；如果初始的數(shù)據(jù)所有的記錄按照關(guān)鍵字逆序的序列的話此時(shí)是最壞的情況，移動(dòng)次數(shù)和比較次數(shù)接近n2，但是在平均情況下希爾排序的比較次數(shù)和移動(dòng)次數(shù)好于直接插入排序，為O（n1.3）左右。選擇排序的空間復(fù)雜度并不隨著處理數(shù)據(jù)量n的大小而改變，為O（1）。

2.4歸并排序

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

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

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

2）對所有有序子序列進(jìn)行兩兩歸并，得到n/2個(gè)長度為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個(gè)待排序記錄的歸并次數(shù)是㏒2n，而一趟歸并的時(shí)間復(fù)雜度為O（n），則整個(gè)歸并排序的時(shí)間復(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)了一個(gè)驗(yàn)證程序。通過對比排序算法的交換次數(shù)、比較次數(shù)、移動(dòng)次數(shù)以及排序時(shí)間來進(jìn)一步分析算法性能。通過rand（）函數(shù)模擬產(chǎn)生1000、4000、7000、10000、15000、30000不同規(guī)模的數(shù)據(jù)。

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

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

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

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

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

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

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

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

4性能分析

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

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

5結(jié)論

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

由于本文只對冒泡排序、選擇排序、插入排序以及歸并排序四種典型的排序算法進(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.