【基礎演算法·基本功】-1常用排序演算法小節

內容提要：

＊排序常用術語介紹

＊冒泡排序

＊選擇排序

＊插入排序

＊希爾排序

＊歸併排序

＊快速 排序

排序基礎知識

?排序的定義

將雜亂無章的數據元素，通過一定的方法按關鍵字順序排列的過程叫做排序。說得再通俗點，比如將一個班的人（數據元素）按照身高（關鍵字）站位，高的站前面，矮的站後面咯。

? 排序的分類

排序可分為內排序和外排序。

所謂內排序就是所有的數據和操作都在內存中完成。

而外排序就是說需要排序的數據太大，無法全部塞進內存，需要在內存和外存之間多次數據交換才能完成的排序。

?演算法優劣的術語說明

?穩定：如果Ai=Aj，開始Ai在Aj前面，排完序之後Ai依然在Aj前面。

?不穩定：

如果Ai=Aj，開始Ai在Aj前面，而排完序以後Ai有可能跑到Aj後面去了。

?時間複雜度：一個演算法執行完所消耗的時間。

?空間複雜度：執行一個演算法需要消耗的內存空間大小。

?常見演算法的複雜度及穩定性

好了看完上面一堆頭疼的術語介紹，接下來將為大家介紹幾種常用的內部排序演算法。

1

冒泡排序(Bubble Sort)

?常規冒泡排序

冒泡排序算是比較好理解的了。想小編當年入門的時候，就是仰仗著冒泡大法，從此踏入紅塵，一去不返……呃這個扯遠了，為什麼叫冒泡呢？這個後面再解釋。為了更好的說明問題，還是用一個數組A[n]，以升序（降序方法一樣）為例，來給大家一一講解。

?基本原理：

1）從序列的最左邊開始，將兩兩相鄰的兩個元素（例如A[0]和A[1],

2） 對剩下的元素A[0]~A[n-1]也進行上述操作。完成後A[n-1]裡面存的就是A[0]~A[n-1]中的最大值。

3） 不斷對剩下的元素進行上述操作，直到剩下元素只有A[0]時，排序完成。

看不懂嘛？那來試試圖片吧：

好了，講完了基本原理，來看看具體代碼是如何實現的吧。

可以看到，在冒泡後，相等元素的位置並不會改變。因此，冒泡演算法是穩定的。

? 冒泡排序改進版

此方法可稱為定向冒泡排序，它和冒泡排序的不同之處在於，定向冒泡從左到右把最大數搬到最後面的時候，再反向從右往左把最小值搬到最左邊。這種方法稍微比傳統冒泡好上那麼一丟丟。具體實施看代碼。

不理解嘛？沒關係，小編還為大家準備了動態圖。

定向冒泡的優勢，比如對序列{4, 5, 6, 7, 8,

2

選擇排序(Selection Sort)

說到選擇排序，這個也是灰常易於理解的。相信大家看一眼基本原理就懂了。還是以數組A[n]與升序排列為例說明問題。

基本原理：

1）先從A[0]~A[n]中找最小的元素A[i]，交換A[0]和A[i]的位置。

2）再從剩下的元素A[1]~A[n]中找最小的元素A[j]，交換A[1]和A[j]的位置。

3）不斷在剩下的元素中找最小的元素丟到開頭，直到剩下最後一個元素。

還不懂？再來看看個圖片：

代碼哪能少？

選擇排序每次將最小值丟到開頭的時候，有可能會打亂相等元素的位置。因此，它是不穩定的。也注意區分其和冒泡排序的區別：冒泡排序通過依次交換相鄰兩個順序不合法的元素位置，從而將當前最小（大）元素放到合適的位置；而選擇排序每遍歷一次都記住了當前最小（大）元素的位置，最後僅需一次交換操作即可將其放到合適的位置。

3

插入排序(Insertion Sort)

大家打過撲克牌嘛？我們在對手上的撲克牌進行排序的時候，是不是將右手上的牌插到左手上已經排序好的牌之間？這跟我們的插入排序是有點類似的。

還是以A[n]為例說明問題。

基本原理：

1）從A[0]開始，則A[0]可認為是已排序列。

2）取出下一個元素(比如A[1])，在已排序列中從右往左掃描，如果已排序列中的元素大於取出的元素，那麼就將該元素（已排序列中的）往後挪一個位置。

3）直到在已排序列中找到一個小於等於取出元素的元素。將取出元素插入該元素（已排序列中的）後一個位置。

4）不斷重複步驟2-3.直到所有元素都插入到已排序列。

還不明白？看看圖片

請問代碼在哪裡？？？

親，這麼詳細的注釋，

別跟我說你看不懂

可以看出，關於相等元素，排序前後並不會改變他們的位置。因此，插入排序又是穩定的。

4

希爾排序(Shell Sort)

希爾排序，也叫遞減增量排序，是插入排序的一種更高效的改進版本。其中希爾排序是基於以下幾點做出改進的：

1）直接插入排序對於幾乎排好的數據有著極高的效率。基本可以達到線性排序時的效率。

2）但是對於一般的亂序數據來說，直接插入排序由於每次只能將數據往後搬一位，從這點上來說它效率又是及其低下的。

基本原理：

1）將無序數據分割為若干個子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，對各個子序列進行直接插入排序；

2）然後再選擇一個更小的增量，再將數據分割為多個子序列進行直接插入排序......

3）不斷重複步驟2，直到最後增量變為1，即對所有數據使用直接插入排序（此時所有數據幾乎都排好了，直接插入效率較高），最終排序完成。

還是來看看圖片吧。

關於不同增量的選取對於希爾排序性能的影響，有不同的觀點。這裡就不過多贅述。

代碼！代碼！代碼在哪裡！！！？？？

值得一提的是，由於數據劃分為多個區域，在每個區域中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂。因此希爾排序是不穩定的排序。

5

歸併排序(Merge Sort)

歸併排序（MERGE-SORT）是建立在歸併操作上的一種有效的排序演算法,該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。效率為O(nlogn)，1945年由馮·諾伊曼首次提出。歸併排序的實現分為遞歸實現與非遞歸(迭代)實現。這裡我們討論遞歸實現。歸併排序依賴于歸並操作。歸併操作(merge)，也叫歸併演算法，指的是將兩個順序序列合併成一個順序序列的方法。

基本原理：

1）申請內存空間A，大小為兩個已排序列之和。

2）設定兩個指針，分別指向兩個已排序列的首元素。

3）比較兩個指針指向的元素大小，將小的那個元素丟進內存空間A。同時指向該元素的指針向前移動一位。

4）不斷重複步驟3），直到任何一個序列的元素全被丟進空間A。那麼就把另外一個序列剩下的所有元素丟進空間A。

Understand？別說了，看圖吧。

兄弟，來，幹了這段代碼。

歸併排序是穩定的演算法。

6

快速排序(Quick Sort)

終於說到這個大boss了。為什麼叫快速排序呢？額，這個倒不是因為它很快。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：開始選取一個基準數，通過一趟排序將基準數移到序列的合適位置，使得，左邊的這部分都小於等於基準數，右邊的部分都大於等於基準數，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

那麼，對於一個序列，怎樣才能使基準數移動到正確位置，以便能使左邊的數都小於等於它，右邊的數都大於等於它呢？還是以數組A[N]為例，為大家慢慢道來：

1）設置兩個變數i、j，排序開始的時候：i=0，j=N；

2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；

3）從j開始向前搜索，即由後開始向前搜索(j--)，找到第一個小於key的值A[j]，將A[j]和A[i]互換；

4）從i開始向後搜索，即由前開始向後搜索(i++)，找到第一個大於key的A[i]，將A[i]和A[j]互換；

5）重複第3、4步，直到i=j；

6）3,4步中，沒找到符合條件的值，即3中A[j]不小於key,4中A[i]不大於key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束。

還是來看看圖吧：

大家已經發現了，當序列中的每個元素都歸位的時候，整個序列也就都變得有序了。

看完了圖解是不是感覺賊得勁兒了呢？？

看代碼：

快速排序是不穩定的排序演算法。

OK。自此，常用的排序演算法已經介紹完畢，今天的表演到此結束，謝謝大家。

-END-

編輯：鄧發珩（華中科技大學管理學院本科一年級，2638512393@qq.com，個人公眾號:程序猿聲）

代碼: 鄧發珩

指導老師：秦時明岳（professor.qin@qq.com）

如有疑問，歡迎諮詢~

更多最新數據分析相關原創文章，請關注微信公眾號：數據魔術師