幾種常見排序算法思想及比較分析

段曉忠

[摘要]排序算法是算法的入門知識(shí)，即如何使得記錄按照要求排列的方法，其經(jīng)典思想可以用于很多算法當(dāng)中。因?yàn)槠鋵?shí)現(xiàn)代碼較短，應(yīng)用較常見。在面試中經(jīng)常會(huì)問到排序算法及其相關(guān)的問題。但萬變不離其宗，只要熟悉了思想，靈活運(yùn)用也不是難事。文章分析了常見的排序算法及其使用場(chǎng)景。

[關(guān)鍵詞]排序算法；經(jīng)典思想；使用場(chǎng)景

[DOI]1013939/jcnkizgsc201619189

1常見排序算法思想分析

11冒泡排序

冒泡排序是最簡單的排序之一，其大體思想就是通過與相鄰元素的比較和交換來把小的數(shù)交換到最前面。這個(gè)過程類似于水泡向上升一樣，因此而得名。對(duì)剩下的序列依次冒泡就會(huì)得到一個(gè)有序序列。冒泡排序的時(shí)間復(fù)雜度為O（n^2）。

12插入排序

插入排序不是通過交換位置而是通過比較找到合適的位置插入元素來達(dá)到排序的目的。相信大家都有過打撲克牌的經(jīng)歷，特別是牌數(shù)較大的。在分牌時(shí)可能要整理自己的牌，牌多的時(shí)候怎么整理呢？就是拿到一張牌，找到一個(gè)合適的位置插入。這個(gè)原理其實(shí)和插入排序是一樣的。注意在插入一個(gè)數(shù)的時(shí)候要保證這個(gè)數(shù)前面的數(shù)已經(jīng)有序。簡單插入排序的時(shí)間復(fù)雜度也是O（n^2）。

13快速排序

在實(shí)際應(yīng)用當(dāng)中快速排序確實(shí)是表現(xiàn)最好的排序算法。冒泡排序雖然高端，但其思想是來自冒泡排序，冒泡排序是通過相鄰元素的比較和交換把最小的冒泡到最頂端，而快速排序是比較和交換小數(shù)和大數(shù)，這樣一來不僅把小數(shù)冒泡到上面，同時(shí)也把大數(shù)沉到下面?？焖倥判蚴遣环€(wěn)定的，其時(shí)間平均時(shí)間復(fù)雜度是O（nlgn）。

14堆排序

堆排序是借助堆來實(shí)現(xiàn)的選擇排序，思想同簡單的選擇排序，以下以大頂堆為例。注意，如果想升序排序就使用大頂堆，反之使用小頂堆。原因是堆頂元素需要交換到序列尾部。首先，實(shí)現(xiàn)堆排序需要解決兩個(gè)問題：①如何由一個(gè)無序序列鍵成一個(gè)堆？②如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個(gè)新的堆？

第一個(gè)問題，可以直接使用線性數(shù)組來表示一個(gè)堆，由初始的無序序列建成一個(gè)堆就需要自底向上從第一個(gè)非葉元素開始挨個(gè)調(diào)整成一個(gè)堆。

第二個(gè)問題，怎么調(diào)整成堆？首先是將堆頂元素和最后一個(gè)元素交換。然后比較當(dāng)前堆頂元素的左右孩子節(jié)點(diǎn)，因?yàn)槌水?dāng)前的堆頂元素，左右孩子堆均滿足條件，這時(shí)需要選擇當(dāng)前堆頂元素與左右孩子節(jié)點(diǎn)的較大者（大頂堆）交換，直至葉子節(jié)點(diǎn)。我們稱這個(gè)自堆頂自葉子的調(diào)整為篩選。

從一個(gè)無序序列建堆的過程就是一個(gè)反復(fù)篩選的過程。若將此序列看成是一個(gè)完全二叉樹，則最后一個(gè)非終端節(jié)點(diǎn)是n/2取底個(gè)元素，由此篩選即可。

15希爾排序

希爾排序是插入排序的一種高效率的實(shí)現(xiàn)，也叫縮小增量排序。簡單的插入排序中，如果待排序列是正序時(shí)，時(shí)間復(fù)雜度是O（n），如果序列是基本有序的，使用直接插入排序效率就非常高。其基本思想是：先將整個(gè)待排記錄序列分割成為若干子序列，分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)再對(duì)全體記錄進(jìn)行一次直接插入排序。希爾排序的特點(diǎn)是，子序列的構(gòu)成不是簡單的逐段分割，而是將某個(gè)相隔某個(gè)增量的記錄組成一個(gè)子序列。由于前兩趟的插入排序中記錄的關(guān)鍵字是和同一子序列中的前一個(gè)記錄的關(guān)鍵字進(jìn)行比較，因此關(guān)鍵字較小的記錄就不是一步一步地向前挪動(dòng)，而是跳躍式地往前移，從而使得進(jìn)行最后一趟排序時(shí)，整個(gè)序列已經(jīng)做到基本有序，只要作記錄的少量比較和移動(dòng)即可，因此希爾排序的效率要比直接插入排序高。

希爾排序的分析是復(fù)雜的，時(shí)間復(fù)雜度是所取增量的函數(shù)，在大量實(shí)驗(yàn)的基礎(chǔ)上推出當(dāng)n在某個(gè)范圍內(nèi)時(shí)，時(shí)間復(fù)雜度可以達(dá)到O（n^13）。

16歸并排序

歸并排序是另一種不同的排序方法，因?yàn)闅w并排序使用了遞歸分治的思想，所以理解起來比較容易。其基本思想是，先遞歸劃分子問題，然后合并結(jié)果。把待排序列看成由兩個(gè)有序的子序列，然后合并兩個(gè)子序列，然后把子序列看成由兩個(gè)有序序列……倒著來看，其實(shí)就是先兩兩合并，然后四四合并……最終形成有序序列?？臻g復(fù)雜度為O（n），時(shí)間復(fù)雜度為O（nlogn）。

17桶排序

假設(shè)有一組長度為N的待排關(guān)鍵字序列K[1，…，n]。首先將這個(gè)序列劃分成M個(gè)的子區(qū)間（桶）。然后基于某種映射函數(shù)，將待排序列的關(guān)鍵字k映射到第i個(gè)桶中（即桶數(shù)組B的下標(biāo) i），那么該關(guān)鍵字k就作為B[i]中的元素（每個(gè)桶B[i]都是一組大小為N/M的序列）。接著對(duì)每個(gè)桶B[i]中的所有元素進(jìn)行比較排序（可以使用快排）。然后依次枚舉輸出B[0]，…，B[M]中的全部內(nèi)容即是一個(gè)有序序列。

bindex=f（key）

其中，bindex 為桶數(shù)組B的下標(biāo)（即第bindex個(gè)桶），k為待排序列的關(guān)鍵字。桶排序之所以能夠高效，其關(guān)鍵在于這個(gè)映射函數(shù)，它必須做到：如果關(guān)鍵字k1

18基數(shù)排序

基數(shù)排序又是一種和前面排序方式不同的排序方式，基數(shù)排序不需要進(jìn)行記錄關(guān)鍵字之間的比較。基數(shù)排序是一種借助多關(guān)鍵字排序思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序的方法。所謂的多關(guān)鍵字排序就是有多個(gè)優(yōu)先級(jí)不同的關(guān)鍵字。比如說成績的排序，如果兩個(gè)人總分相同，則語文高的排在前面，語文成績也相同則數(shù)學(xué)高的排在前面……如果對(duì)數(shù)字進(jìn)行排序，那么個(gè)位、十位、百位就是不同優(yōu)先級(jí)的關(guān)鍵字，如果要進(jìn)行升序排序，那么個(gè)位、十位、百位優(yōu)先級(jí)一次增加。基數(shù)排序是通過多次的收分配和收集來實(shí)現(xiàn)的，關(guān)鍵字優(yōu)先級(jí)低的先進(jìn)行分配和收集。

2結(jié)論

在前面的介紹和分析中文章提到了冒泡排序、選擇排序、插入排序三種簡單的排序及其變種快速排序、堆排序、希爾排序三種比較高效的排序。后面又分析了基于分治遞歸思想的歸并排序還有計(jì)數(shù)排序、桶排序、基數(shù)排序三種線性排序。其實(shí)排序算法要么簡單有效，要么是利用簡單排序的特點(diǎn)加以改進(jìn)，要么是以空間換取時(shí)間在特定情況下的高效排序。但是這些排序方法都不是固定不變的，需要結(jié)合具體的需求和場(chǎng)景來選擇甚至組合使用，才能達(dá)到高效穩(wěn)定的目的。沒有最好的排序，只有最適合的排序。

下面就總結(jié)一下排序算法的各自的使用場(chǎng)景和適用場(chǎng)合：

（1）從平均時(shí)間來看，快速排序是效率最高的，但快速排序在最壞情況下的時(shí)間性能不如堆排序和歸并排序。而后者相比較的結(jié)果是，在n較大時(shí)歸并排序使用時(shí)間較少，但使用輔助空間較多。

（2）上面說的簡單排序包括除希爾排序之外的所有冒泡排序、插入排序、簡單選擇排序。其中直接插入排序最簡單，但序列基本有序或者n較小時(shí)，直接插入排序是好的方法，因此常將它和其他的排序方法，如快速排序、歸并排序等結(jié)合在一起使用。

（3）基數(shù)排序的時(shí)間復(fù)雜度也可以寫成O（d*n）。因此它最適用于n值很大而關(guān)鍵字較小的序列。若關(guān)鍵字也很大，而序列中大多數(shù)記錄的最高關(guān)鍵字均不同，則亦可先按最高關(guān)鍵字不同，將序列分成若干小的子序列，而后進(jìn)行直接插入排序。

（4）從方法的穩(wěn)定性來比較，基數(shù)排序是穩(wěn)定的內(nèi)排方法，所有時(shí)間復(fù)雜度為O（n^2）的簡單排序也是穩(wěn)定的。但是快速排序、堆排序、希爾排序等時(shí)間性能較好的排序方法都是不穩(wěn)定的。穩(wěn)定性需要根據(jù)具體需求選擇。

（5）上面的算法實(shí)現(xiàn)大多數(shù)是使用線性存儲(chǔ)結(jié)構(gòu)，像插入排序這種算法用鏈表實(shí)現(xiàn)更好，省去了移動(dòng)元素的時(shí)間。具體的存儲(chǔ)結(jié)構(gòu)在具體的實(shí)現(xiàn)版本中也是不同的。

參考文獻(xiàn)：

[1]李寶艷，馬英紅排序算法研究[J].電腦知識(shí)與技術(shù)：學(xué)術(shù)交流，2007（8）.

[2]梁利剛，易超，楊繡丞，等靜態(tài)排序算法設(shè)計(jì)與分析[J].計(jì)算機(jī)應(yīng)用與軟件，2012（3）.