常用排序算法的分析與比較

謝小玲，李山

（1.重慶市商務高級技工學校，重慶400067；2.林同棪（重慶）國際工程技術有限公司，重慶401123）

0 引言

當前正處于數據爆炸時代，云計算、大數據等熱門領域都離不開數據分析，然而高效地數據分析是建立在有序序列的基礎之上，因此研究排序方法具有重要意義。排序是指將一組數據按指定關鍵字的順序進行排列的過程。按照排序過程是否需要將全部數據加載到內存中進行排序，可分為內部排序和外部排序[1]：其中內部排序是指將所有數據都加載到內存中進行排序；而外部排序是內外存結合的排序方法。由于內排序算法比較常用，所以本文選擇研究主流的內排序算法。目前，許多研究者主要從理論去分析各種排序算法的執行效率[2-5]，其推導過程抽象難懂，得出的結論都是的漸進時間復雜度，相當于就是一個估算值，沒有給出量化指標來指導選擇何種排序算法。為此，本文選擇了理論與編程試驗相結合方式展開了研究，首先闡述了8 種排序算法的基本思路，定性地分析了它們的漸近時間復雜度，然后通過編程實驗，定量地驗算了不同的排序的時間效率。

1 排序算法簡介

常用的內部排序算法可分為以下5 類（如圖1 所示）：交換排序、插入排序、選擇排序、歸并排序和基數排序。

圖1 常用排序算法分類

為了便于讀者理解算法的思想，筆者采用舉例說明：給定n 個數，要求按照遞增排序。

1.1 交換排序

交換排序包括冒泡排序和快速排序。

（1）冒泡排序

冒泡排序的基本思想是對序列多趟從前往后依次比較相鄰元素，如果發現逆序則交換它們的位置，其大概過程是：第1 趟遍歷a1到an-1，依次比較ai和ai+1，若ai＞ai+1就交換ai和ai+1的位置；然后進入第2 趟遍歷a1到an-2，仍依次比較ai和ai+1，若ai＞ai+1就交換ai和ai+1的位置；以此類推，當經過n-1 次遍歷后，排序完成。該過程的每趟遍歷都會得到一個較大值，就像水底冒泡一樣，所以稱之為冒泡排序。

（2）快速排序

快速排序算法是一種劃分交換排序，其基本思想是：先從原序列中任選一個數ai，讓ai與剩余的數相比較，把小于ai的數移到ai的左邊，把大于ai大的數移到ai的右邊，于是得到兩個新的子序列，然后又對新的兩個子序列采用上述步驟，直到新的子序列長度為1 時截止，此時整體序列排序完成。

1.2 插入排序

插入排序包括直接插入排序和希爾排序。

（1）直接插入排序

直接插入排序是對待排序列以插入方式找到適合位置的排序方法，其基本思路是：先把原序列分為有序子序列{a1}和無序子序列{a2，a3，…，an}，然后每輪循環從無序序列取出一個數ai插入到有序子序列合適的位置使之仍有序，經過n-1 輪循環后，排序完成。

（2）希爾排序

希爾排序是對直接插入排序算法的改進，它將待排序列中的元素下標按一定的步長進行分組，然后對每組數列按直接插入排序算法進行排序。其基本思路是：首輪排序設步長為h 且h＜n，把原序列分為多個子序列{a1，a1+h，a1+2h，…}，{a2，a2+h，a2+2h，…}，…，{ah-1，a2h-1，a3h-1，…}，然后分別對每一個子序列進行排序；接著進入第2 輪，把步長設為[h/2]，重新劃分子序列并對其排序，以此類推，直到h=1 時，整體排序完成。

1.3 選擇排序

選擇排序包括簡單選擇排序和堆排序。

（1）簡單選擇排序

簡單選擇排序的基本思路是從原序列中選出最大元素ai，并交換ai和an的位置，此時an就是序列的最大值。接著從a1到an-1中選出新的最大值ai，再交換ai和an-1的位置，此an-1變為序列的次最大值，以此類推，經過n-1 次挑選，整體排序完成。

（2）堆排序

堆排序是一種利用完全二叉樹進行排序的算法，假定使用大頂堆來排序，它的基本思路是先將原序列構成一個大頂堆，再把大頂堆的根結點ai和無序序列末尾元素an交換位置，由于交換位置后可能違反堆的性質，因此需要重新把a1到an-1構建一個大頂堆，再把堆頂元素ai與an-1交換；重復上述步驟，只需n-1 輪排序，便能得到一個有序序列。

1.4 歸并排序

歸并排序是采用經典的“分治策略”思想來進行排序，該算法的“分”很簡單，就是把原序列看成n 個長度為1 的子序列，而“治”是先把n 個長度為1 的子序列合并為n/2 個長度2 為子序列，再把n/2 個長度為2 的子序列合并為n/4 個長度4 為子序列，重復上述步驟，直到所有數據合并1 個長度為n 的有序序列。

1.5 基數排序

基數排序的基本思想是將原序列的整數數位分割成不同的數字，數位較短的補零，從低位向高位進行排序，其大概過程是：先按個位上數字的大小進行第1 輪排序，得到一個新序列，再按十位上的數字大小對新的序列進行排序，以此類推，直到最高位排序完成后，整個序列就有序了。

2 排序算法復雜度分析

刻畫算法的好壞主要是看它的時間復雜度T（n）和空間復雜度S（n），排序算法也不例外。時間復雜度是指算法執行時所耗費的總時長，空間復雜度是指算法執行時占用的內存空間單元長度，二者都是數據規模n 的函數。下面主要討論常用排序算法的時間復雜度和空間復雜度。

2.1 時間復雜度

（1）冒泡排序

最壞情況下，若原序列是逆序，則需要n-1 輪遍歷，第i 輪遍歷需要比較n-i 次和交換n-i 次，此時最差時間復雜度為

最好的情況下，若原序列本身有序，則只需要1 輪遍歷就可以完成排序，該輪遍歷只需比較n-1 次和交換0 次，所以最好時間復雜度為：

（2）快速排序

選取恰當的序列分割基準是快速排序的關鍵。最壞的情況下，如果每次選取的分割基準是當前無序序列的最大值（或最小值），將會得到空的左子序列（或右子序列），這時共需劃分n-1 次才能排好序。在這遞歸過程中，第i 次劃分需要比較n-i 次、交換n-i 次，所以最差時間復雜度為：

最好的情況下，每次選取的分割基準是當前區間的中值元素，劃分結果是左右區間長度大致相等，此時只需logn 次遞歸，每次遞歸比較次數總和不超過n 次，所以最好的時間復雜度為O（nlogn）。

（3）直接插入排序

若原序列是正序時，則經過1 輪遍歷便可完成排序，該次遍歷的需比較n-1 次、交換0 次，最好的時間復雜度為：

若原始序列是逆序，則需要n-1 輪遍歷，其中第i輪需比較n-i 次、交換n-i 次，所以最差時間復雜為：

（4）希爾排序

希爾排序的執行時間依賴于增量h 的選擇，但目前h 的確定尚無較好的確定性理論，但Shell 建議較好的增量劃分為hi=[n/2]，hi+1=[hi/2]，對應的最差時間復雜度為O（n2），最好時間復雜度為O（n）。

（5）簡單選擇排序

無論原序列的狀態如何，簡單選擇排序都要進行n-1 輪遍歷，且第i 輪遍歷需n-i 次比較。另外，還要考慮每輪遍歷的交換次數，當原序列是逆序時，則需要交換n-1 次；當原序列是正序時，需交換0 次，所以最差的時間復雜度為

（6）堆排序

堆排序的時間主要耗費在構建初始堆和反復的重建堆上面，第一階段構建初始堆最多比較2n 次，第二階段需要重建堆n-1 次，第i 次最多比較logi 次，所以它的最壞時間復雜為O（nlogn）。

（7）歸并排序

歸并排序無論原序列狀態如何，都要進行logn 次兩路歸并，每次合并比較次數不超過n，所以它的最差時間復雜度都為O（nlogn）。

（8）基數排序

設原序列中最大元素的數位為k，則基數排序需要k 趟排序，每趟排序最多需要比較n-1 次，所以它的最差時間復雜度為O（n*k）。

2.2 空間復雜度

上面討論的8 種排序算法的空間復雜度都不超過O（nlogn）[5-6]：其中復雜度為O（1）的有冒泡排序、直接插入排序、希爾排序、簡單選擇排序、堆排序；復雜度為O（n）是歸并排序；復雜度為O（n+k）是基數排序；復雜度為O（nlogn）是快速排序。

3 編程實驗及結果分析

本次編程實驗環境是Windows 10+內存16G，采用Java 語言分別對以上討論的8 種排序算法進行了編程實現，并隨機模擬了長度為103、104、105、106、107的數組，分別對每種長度的數組采用這8 種排序算法進行排序，其執行時間見表1。

表1 不同排序算法的執行時間

從表1 可以看出，當待排數組的規模小于104時，各種排序算法的執行時間相差不大，都小于1 秒。但是待排數組的規模大于104時，冒泡排序、直接插入排序和簡單選擇排序隨之耗費時間增加迅猛，特別是當數組的規模超過105時，它們的算法的執行時間讓人難以等待，所以表1 中數組的規模達到107時，排序執行時間太長了，就沒有列舉出來了。

另外，讓人驚喜的是即使數組的規模達到106時，希爾排序、快速排序、堆排序、歸并排序和基數排序的執行時間不超過1 秒就完成了，甚至數組的規模達到107時，都在2 秒左右完成了，所以建議編程人員選擇這幾種排序方法。

4 結語

本文研究了8 種常用的排序算法，概述了各種排序算法的基本思想，分析了不同排序算法的時間復雜度和空間復雜度，并通過編程實驗對各種排序算法的時間復雜度進行驗算，對比了不同數組規模下排序執行時間，結果表明：算法的執行效率與理論分析相符合，當數組的規模小于104時，各種排序算法的執行時間都小于1 秒；但當數組的規模大于104時，應該選擇執行時間較短的希爾排序、快速排序、堆排序、歸并排序和基數排序，因為即使數組的規模達到107時，它們都能在2 秒左右完成。因此，這些量化的排序執行時間有利于選擇合理的排序算法。