原文：http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/

經(jīng)典排序算法在面試中占有很大的比重，也是基礎(chǔ)，為了未雨綢繆，在寒假里整理并用Python實(shí)現(xiàn)了七大經(jīng)典排序算法，包括冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序。希望能幫助到有需要的同學(xué)。之所以用Python實(shí)現(xiàn)，主要是因?yàn)樗咏鼈未a，能用更少的代碼實(shí)現(xiàn)算法，更利于理解。

本篇博客所有排序?qū)崿F(xiàn)均默認(rèn)從小到大。

一、冒泡排序 BubbleSort

介紹：

冒泡排序的原理非常簡(jiǎn)單，它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。

步驟：

1、比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

2、對(duì)第0個(gè)到第n-1個(gè)數(shù)據(jù)做同樣的工作。這時(shí)，最大的數(shù)就“浮”到了數(shù)組最后的位置上。

3、針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

4、持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

源代碼：(python實(shí)現(xiàn))

運(yùn)行上面的代碼有錯(cuò)誤，

下面是自己寫(xiě)的，經(jīng)過(guò)驗(yàn)證：

不過(guò)針對(duì)上述代碼還有兩種優(yōu)化方案。

優(yōu)化1：某一趟遍歷如果沒(méi)有數(shù)據(jù)交換，則說(shuō)明已經(jīng)排好序了，因此不用再進(jìn)行迭代了。用一個(gè)標(biāo)記記錄這個(gè)狀態(tài)即可。

優(yōu)化2：記錄某次遍歷時(shí)最后發(fā)生數(shù)據(jù)交換的位置，這個(gè)位置之后的數(shù)據(jù)顯然已經(jīng)有序，不用再排序了。因此通過(guò)記錄最后發(fā)生數(shù)據(jù)交換的位置就可以確定下次循環(huán)的范圍了。

這兩種優(yōu)化方案的實(shí)現(xiàn)可以詳見(jiàn)這里。

二、選擇排序 SelectionSort

介紹：

選擇排序無(wú)疑是最簡(jiǎn)單直觀的排序。它的工作原理如下。

步驟：

1、在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置。

2、再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。

3、以此類(lèi)推，直到所有元素均排序完畢。

源代碼：(python實(shí)現(xiàn))

三、?插入排序 InsertionSort

介紹：

插入排序的工作原理是，對(duì)于每個(gè)未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

步驟：

1、從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序

2、取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描

3、如果被掃描的元素（已排序）大于新元素，將該元素后移一位

4、重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置

5、將新元素插入到該位置后

6、重復(fù)步驟2~5

排序演示：

源代碼：(python實(shí)現(xiàn))

四、希爾排序 ShellSort

介紹：

希爾排序，也稱(chēng)遞減增量排序算法，實(shí)質(zhì)是分組插入排序。由 Donald Shell 于1959年提出。希爾排序是非穩(wěn)定排序算法。

希爾排序的基本思想是：將數(shù)組列在一個(gè)表中并對(duì)列分別進(jìn)行插入排序，重復(fù)這過(guò)程，不過(guò)每次用更長(zhǎng)的列（步長(zhǎng)更長(zhǎng)了，列數(shù)更少了）來(lái)進(jìn)行。最后整個(gè)表就只有一列了。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法，算法本身還是使用數(shù)組進(jìn)行排序。

例如，假設(shè)有這樣一組數(shù)[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長(zhǎng)為5開(kāi)始進(jìn)行排序，我們可以通過(guò)將這列表放在有5列的表中來(lái)更好地描述算法，這樣他們就應(yīng)該看起來(lái)是這樣：

13 14 94 33 82

25 59 94 65 23

45 27 73 25 39

10

然后我們對(duì)每列進(jìn)行排序：

10 14 73 25 23

13 27 94 33 39

25 59 94 65 82

45

將上述四行數(shù)字，依序接在一起時(shí)我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。這時(shí)10已經(jīng)移至正確位置了，然后再以3為步長(zhǎng)進(jìn)行排序：

10 14 73

25 23 13

27 94 33

39 25 59

94 65 82

45

排序之后變?yōu)椋?/p>

10 14 13

25 23 33

27 25 59

39 65 73

45 94 82

94

最后以1步長(zhǎng)進(jìn)行排序（此時(shí)就是簡(jiǎn)單的插入排序了）。

源代碼：(python實(shí)現(xiàn))

上面源碼的步長(zhǎng)的選擇是從n/2開(kāi)始，每次再減半，直至為0。步長(zhǎng)的選擇直接決定了希爾排序的復(fù)雜度。在維基百科上有對(duì)于步長(zhǎng)串行的詳細(xì)介紹。

五、歸并排序 MergeSort

介紹：

歸并排序是采用分治法的一個(gè)非常典型的應(yīng)用。歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組。

先考慮合并兩個(gè)有序數(shù)組，基本思路是比較兩個(gè)數(shù)組的最前面的數(shù)，誰(shuí)小就先取誰(shuí)，取了后相應(yīng)的指針就往后移一位。然后再比較，直至一個(gè)數(shù)組為空，最后把另一個(gè)數(shù)組的剩余部分復(fù)制過(guò)來(lái)即可。

再考慮遞歸分解，基本思路是將數(shù)組分解成left和right，如果這兩個(gè)數(shù)組內(nèi)部數(shù)據(jù)是有序的，那么就可以用上面合并數(shù)組的方法將這兩個(gè)數(shù)組合并排序。如何讓這兩個(gè)數(shù)組內(nèi)部是有序的？可以再二分，直至分解出的小組只含有一個(gè)元素時(shí)為止，此時(shí)認(rèn)為該小組內(nèi)部已有序。然后合并排序相鄰二個(gè)小組即可。

排序演示：

源代碼：(python實(shí)現(xiàn))

六、快速排序 QuickSort

介紹：

快速排序通常明顯比同為Ο(n log n)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多筆試面試中能經(jīng)?？吹娇炫诺挠白印？梢?jiàn)掌握快排的重要性。

步驟：

從數(shù)列中挑出一個(gè)元素作為基準(zhǔn)數(shù)。

分區(qū)過(guò)程，將比基準(zhǔn)數(shù)大的放到右邊，小于或等于它的數(shù)都放到左邊。

再對(duì)左右區(qū)間遞歸執(zhí)行第二步，直至各區(qū)間只有一個(gè)數(shù)。

排序演示：

源代碼：(python實(shí)現(xiàn))

七、堆排序 HeapSort

介紹：

堆排序在 top K 問(wèn)題中使用比較頻繁。堆排序是采用二叉堆的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的，雖然實(shí)質(zhì)上還是一維數(shù)組。二叉堆是一個(gè)近似完全二叉樹(shù) 。

二叉堆具有以下性質(zhì)：

1、父節(jié)點(diǎn)的鍵值總是大于或等于（小于或等于）任何一個(gè)子節(jié)點(diǎn)的鍵值。

2、每個(gè)節(jié)點(diǎn)的左右子樹(shù)都是一個(gè)二叉堆（都是最大堆或最小堆）。

步驟：

1、構(gòu)造最大堆（Build_Max_Heap）：若數(shù)組下標(biāo)范圍為0~n，考慮到單獨(dú)一個(gè)元素是大根堆，則從下標(biāo)n/2開(kāi)始的元素均為大根堆。于是只要從n/2-1開(kāi)始，向前依次構(gòu)造大根堆，這樣就能保證，構(gòu)造到某個(gè)節(jié)點(diǎn)時(shí)，它的左右子樹(shù)都已經(jīng)是大根堆。

2、堆排序（HeapSort）：由于堆是用數(shù)組模擬的。得到一個(gè)大根堆后，數(shù)組內(nèi)部并不是有序的。因此需要將堆化數(shù)組有序化。思想是移除根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算。第一次將heap[0]與heap[n-1]交換，再對(duì)heap[0...n-2]做最大堆調(diào)整。第二次將heap[0]與heap[n-2]交換，再對(duì)heap[0...n-3]做最大堆調(diào)整。重復(fù)該操作直至heap[0]和heap[1]交換。由于每次都是將最大的數(shù)并入到后面的有序區(qū)間，故操作完后整個(gè)數(shù)組就是有序的了。

3、最大堆調(diào)整（Max_Heapify）：該方法是提供給上述兩個(gè)過(guò)程調(diào)用的。目的是將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn) 。

排序演示：

源代碼：(python實(shí)現(xiàn))

總結(jié)

下面為七種經(jīng)典排序算法指標(biāo)對(duì)比情況：