幾種常見(jiàn)排序算法思想及比較分析

段曉忠

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

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

[DOI]1013939/jcnkizgsc201619189

1常見(jiàn)排序算法思想分析

11冒泡排序

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

12插入排序

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

13快速排序

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

14堆排序

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

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

第二個(gè)問(wèn)題，怎么調(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è)無(wú)序序列建堆的過(guò)程就是一個(gè)反復(fù)篩選的過(guò)程。若將此序列看成是一個(gè)完全二叉樹(shù)，則最后一個(gè)非終端節(jié)點(diǎn)是n/2取底個(gè)元素，由此篩選即可。

15希爾排序

希爾排序是插入排序的一種高效率的實(shí)現(xiàn)，也叫縮小增量排序。簡(jiǎn)單的插入排序中，如果待排序列是正序時(shí)，時(shí)間復(fù)雜度是O（n），如果序列是基本有序的，使用直接插入排序效率就非常高。其基本思想是：先將整個(gè)待排記錄序列分割成為若干子序列，分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)再對(duì)全體記錄進(jìn)行一次直接插入排序。希爾排序的特點(diǎn)是，子序列的構(gòu)成不是簡(jiǎn)單的逐段分割，而是將某個(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并排序使用了遞歸分治的思想，所以理解起來(lái)比較容易。其基本思想是，先遞歸劃分子問(wèn)題，然后合并結(jié)果。把待排序列看成由兩個(gè)有序的子序列，然后合并兩個(gè)子序列，然后把子序列看成由兩個(gè)有序序列……倒著來(lái)看，其實(shí)就是先兩兩合并，然后四四合并……最終形成有序序列?？臻g復(fù)雜度為O（n），時(shí)間復(fù)雜度為O（nlogn）。

17桶排序

假設(shè)有一組長(zhǎng)度為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]中的全部?jī)?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)鍵字。比如說(shuō)成績(jī)的排序，如果兩個(gè)人總分相同，則語(yǔ)文高的排在前面，語(yǔ)文成績(jī)也相同則數(shù)學(xué)高的排在前面……如果對(duì)數(shù)字進(jìn)行排序，那么個(gè)位、十位、百位就是不同優(yōu)先級(jí)的關(guān)鍵字，如果要進(jìn)行升序排序，那么個(gè)位、十位、百位優(yōu)先級(jí)一次增加?；鶖?shù)排序是通過(guò)多次的收分配和收集來(lái)實(shí)現(xiàn)的，關(guān)鍵字優(yōu)先級(jí)低的先進(jìn)行分配和收集。

2結(jié)論

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

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

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

（2）上面說(shuō)的簡(jiǎn)單排序包括除希爾排序之外的所有冒泡排序、插入排序、簡(jiǎn)單選擇排序。其中直接插入排序最簡(jiǎn)單，但序列基本有序或者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)定性來(lái)比較，基數(shù)排序是穩(wěn)定的內(nèi)排方法，所有時(shí)間復(fù)雜度為O（n^2）的簡(jiǎn)單排序也是穩(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）.