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

謝小玲，李山

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

0 引言

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

1 排序算法簡介

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

圖1 常用排序算法分類

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

1.1 交換排序

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

（1）冒泡排序

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

（2）快速排序

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

1.2 插入排序

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

（1）直接插入排序

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

（2）希爾排序

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

1.3 選擇排序

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

（1）簡單選擇排序

簡單選擇排序的基本思路是從原序列中選出最大元素ai，并交換ai和an的位置，此時(shí)an就是序列的最大值。接著從a1到an-1中選出新的最大值ai，再交換ai和an-1的位置，此an-1變?yōu)樾蛄械拇巫畲笾担源祟愅?，?jīng)過n-1 次挑選，整體排序完成。

（2）堆排序

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

1.4 歸并排序

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

1.5 基數(shù)排序

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

2 排序算法復(fù)雜度分析

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

2.1 時(shí)間復(fù)雜度

（1）冒泡排序

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

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

（2）快速排序

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

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

（3）直接插入排序

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

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

（4）希爾排序

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

（5）簡單選擇排序

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

（6）堆排序

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

（7）歸并排序

歸并排序無論原序列狀態(tài)如何，都要進(jìn)行l(wèi)ogn 次兩路歸并，每次合并比較次數(shù)不超過n，所以它的最差時(shí)間復(fù)雜度都為O（nlogn）。

（8）基數(shù)排序

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

2.2 空間復(fù)雜度

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

3 編程實(shí)驗(yàn)及結(jié)果分析

本次編程實(shí)驗(yàn)環(huán)境是Windows 10+內(nèi)存16G，采用Java 語言分別對以上討論的8 種排序算法進(jìn)行了編程實(shí)現(xiàn)，并隨機(jī)模擬了長度為103、104、105、106、107的數(shù)組，分別對每種長度的數(shù)組采用這8 種排序算法進(jìn)行排序，其執(zhí)行時(shí)間見表1。

表1 不同排序算法的執(zhí)行時(shí)間

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

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

4 結(jié)語

本文研究了8 種常用的排序算法，概述了各種排序算法的基本思想，分析了不同排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度，并通過編程實(shí)驗(yàn)對各種排序算法的時(shí)間復(fù)雜度進(jìn)行驗(yàn)算，對比了不同數(shù)組規(guī)模下排序執(zhí)行時(shí)間，結(jié)果表明：算法的執(zhí)行效率與理論分析相符合，當(dāng)數(shù)組的規(guī)模小于104時(shí)，各種排序算法的執(zhí)行時(shí)間都小于1 秒；但當(dāng)數(shù)組的規(guī)模大于104時(shí)，應(yīng)該選擇執(zhí)行時(shí)間較短的希爾排序、快速排序、堆排序、歸并排序和基數(shù)排序，因?yàn)榧词箶?shù)組的規(guī)模達(dá)到107時(shí)，它們都能在2 秒左右完成。因此，這些量化的排序執(zhí)行時(shí)間有利于選擇合理的排序算法。