幾種典型內部排序算法性能分析

陶圣哲

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

關鍵詞：排序算法；性能；復雜度

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）26-0026-04

1緒論

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

2排序算法

排序算法數據處理規模的不同導致算法使用處理器的不同，一般將排序算法分為內部排序和外部排序。內部排序是指算法的整個處理過程完全在計算機內存中進行的排序算法，這是基于算法的數據估摸相對比較小，計算機內存能夠滿足計算機讀取存儲的需求，本文重點討論的是內部排序中的冒泡排序、選擇排序、插入排序、歸并排序四種排序算法。外部排序一般需要處理的數據比較大，計算機內存無法滿足待排序對象的一次存儲，待排序記錄需要在計算機內部存儲器以及外部存儲器之間進行切換來滿足數據量的要求，進而實現對整個文件的排序[2]。

2.1冒泡排序

冒泡排序的基本思想是：通過不斷比較相鄰兩個數的大小，并進行相應的調整使得最后所有數據達到有序，之所以稱為冒泡排序是由于每一趟排序只比較出一個最大或最小的數出來，類似于冒泡。

具體排序過程如下：

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

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

3）之后按照相同的規則進行比較直到最后只剩下一個數據，此時排序完成。

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

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） //本趟無交換發生，則結束

return；}}

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

2.2選擇排序

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

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

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

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

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

4）直到所有數據均有序，算法結束。

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

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；}}

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

2.3插入排序

這里以希爾插入排序為例，希爾插入排序是對線性插入排序的一種改進，又稱為縮小增量排序。希爾排序的基本思想是：對于一個記錄數是m的待排序數據，首先選擇一個增量dis1

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

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

2）在上面排序結果的基礎之后選擇距離增量dis2，dis2增量的選取可以參照經典的二分法，向下取整二分dis1，按照步驟1的方式進行組內插入排序。

3）按照相同的距離增量選擇原則進行排序直到距離增量為取值為1，此時相當于對一組數據進行直接插入排序，排序完成數據有序，算法結束。

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

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循環}}

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

}}

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

2.4歸并排序

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

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

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

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

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

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

{//二路歸并排序，將a[p1]～a[p2]中的元素排序，結果在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個待排序記錄的歸并次數是㏒2n，而一趟歸并的時間復雜度為O（n），則整個歸并排序的時間復雜度無論是最好還是最壞情況均為O（n㏒2n）。在排序過程中，使用了輔助向量DR，大小與待排序記錄空間相同，則空間復雜度為O（n）。歸并排序是穩定的，歸并排序的排序的空間復雜度和處理數據的規模n相關，為O（n）。

3實驗驗證

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

待排序數量是1K，4K，7K，10K，15K，30K時四種算法執行過程對應的交換次數如表1所示。

從表中可以看出插入排序以及歸并排序并不進行交換，冒泡排序的交換次數規模是最大的，選擇排序交換次數和算法數據規?；鞠喈?。

待排序數量是1K，4K，7K，10K，15K，30K時四種算法執行過程進行的比較次數如表2所示。

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

待排序數量是1K，4K，7K，10K，15K，30K時四種算法執行過程進行的移動次數如表3所示。

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

待排序數量是1K，4K，7K，10K，15K，30K時四種算法執行過程進行的時間對比如表4所示。

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

4性能分析

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

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

5結論

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

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

參考文獻：

[1] 嚴蔚敏，吳偉民.數據結構[M].北京：清華大學出版社，1997：263-289.

[2] 王曉東.計算機算法設計與分析[M].北京：電子工業出版社，2007：21-25.