? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

程磊，某手機大廠系統開發工程師，閱碼場榮譽總編輯，最大的愛好是鉆研Linux內核基本原理。

目錄：

一、排序算法的基本邏輯

? ? ?1.1 什么是排序

? ? ?1.2 排序算法分類

? ? ?1.3 比較排序

? ? ?1.4 非比較排序

? ? ?1.5 排序算法評價維度

? ? ?1.6 比較排序的高級算法

? ? ?1.7 遞歸性與原地性

? ? ?1.8 排序算法概覽

二、排序算法實現與分析

? ? ?2.1 如何分析排序算法

? ? ?2.2 簡單選擇排序

? ? ?2.3 堆排序

? ? ?2.4 簡單插入排序

? ? ?2.5 希爾排序

? ? ?2.6 冒泡排序

? ? ?2.7 快速排序

? ? ?2.8 歸并排序

? ? ?2.9 計數排序

? ? ?2.10 桶排序

? ? ?2.11 基數排序

三、總結回顧

一、排序算法的基本邏輯?

排序是數據結構與算法里面最基礎最入門的內容，雖然簡單，但是深入研究的話里面還是有很多內容的，今天我們來全面詳細的講一講各種排序算法的分類、原理、復雜度、穩定性和實現方法。

1.1 什么是排序

我們先來說一說什么是排序、為什么要排序。什么是排序，這個很簡單，就是把無序的東西按照一定的規則順序排列成升序或者降序。為什么要排序，有兩個原因，一是為了方便后面的查找，如果沒有排序的話只能進行線性查找，時間復雜度是O(n)，如果排序了就可以進行二分查找，時間復雜度是O(logn)，復雜度一下子就大大降低了。我們來說明一下這兩種復雜度的差別有多么懸殊(雖然用詞錯誤，但是這么用確實很符合氣氛)，假設n是10億的話，O(n)還是10億，而O(logn)是30多(以2為底，假設系數是1)，30多和10億比都可以忽略不計了。二是為了顯示的時候按照順序顯示，人類的習慣就是喜歡看有序的東西。

1.2 排序算法分類

那么該怎么進行排序的呢，最基本的方法是什么呢，最基本的方法那當然是比較了，不比較怎么排序呢，只有比較了才能知道該誰前誰后。可是當我看到很多算法書上都說排序有比較排序和非比較排序，我第一眼看到的時候都驚呆了，不可能，絕對不可能。非比較還能排序，排序還能不比較，這怎么可能，絕對是瞎扯。當我繼續看下去的時候發現確實能。后來我仔細思考了一下發現，非比較排序本質上還是在比較，只不過它們不是在和別人比較，而是在和自己比較，在和自己的本位比較 (突然想起了上學時老師經常說的話，不要老是和別人比，要多和自己比，非比較排序做到了)。什么是和自己的本位比較呢，比如說有1到9共9個數順序是亂的，1本來就該在1的位置，2本來就該在2的位置，……，9本來就該在9的位置，它們不用去和別人比，只需要去站到自己本來應該站的位置，順序就自然就排好了。所以比較排序、非比較排序也可以叫做顯式比較排序、隱式比較排序。

1.3 比較排序

光比較還不行，誰給誰比較呢，比較了之后怎么做呢，這些做法的不同又產生了很多不同類型的比較排序方法。同樣，隱式比較也存在這些問題，怎么找到它們的本位呢，它們站到本位之后又該怎么辦呢，這些做法的不同又把非比較排序分為了很多的類別。我們先說比較排序，我們最容易想到的做法就是選擇排序，先選一個最高的站在第一位，在從剩下的選擇一個最高的站在第二位，以此類推，到最后一個的時候就已經從高到低排好序了，我們上學時排隊也會經常用到這種方法。還比較容易想到的另一個方法就是插入排序，先隨便過來一個人，再過來一個，比他高就站到他前面，比他低就站在他后面，再過來一個人，如果比前面的高就一直往前面走，直到不比前面的高就不走了，就在這個位置插入，這種排序方式上學排隊的時候也有用到過。還有一種比較常見的排序方式是交換排序，在軍訓的時候很常用，教官突然叫集合，大家匆匆忙忙的站成一排，教官說從左往右從高到低排列，大家左右互看，你看看我我看看你，比左邊的人高就和左邊的人交換，比右邊的人低就和右邊的人交換，不一會就排好序了。比較排序中，我們已經說了選擇排序、插入排序、交換排序三種方法，這三種排序都是很直觀很容易想到的，生活中也很是很常用的。比如我們打牌的時候會把手里的牌排成一定的順序，有人習慣用插入排序法，有人喜歡用選擇排序，也有人喜歡用交換排序。還有一種排序方法，是不容易想到的，生活中很少有用到，叫做歸并排序。它的大概邏輯是先兩個人一對兩個人一對的，兩個人之間先排好序，然后兩對人再合并成一隊并排好序，以此類推，直至所有人都排成一隊，也就排好序了。我們后面講到歸并排序的時候會再具體講它的邏輯。

1.4 非比較排序

我們舉例說明了比較排序的幾類操作邏輯，那么非比較排序是怎么操作的呢。我們前面說了可以讓數據直到站到它們的本位去就排好序了，但是這里面有一個條件，就是數據要是不重不漏的。很多時候數據都是有重有漏的，怎么辦呢，這時候我們有一種方法叫做計數排序。我們舉例說明一下什么是計數排序，比如1,5,9,6,5,2,6,7,5這個數列有9個數，能不能它們直接站到本位去呢，不能，因為5這個數有3個，6這個數有兩個，讓所有的5都站到第5位上是站不下的，同時3,4這些位上是沒有數的，因此要先對這些數進行計數，如果有一個1，就站到1位上，如果有兩個1就站到1,2位上，如果沒有1,1位就空著留給下一個數。假設有兩個1，再看2，如果有一個2,2就要站在3位上，如果有兩個2，2就站到3和4位上，如果沒有2，3位就空著留給下一個數。以此類推排序3,4,5…9，整個數列就排好序了。

計數排序適合那些數據分布比較集中的情況，如果數據比較分散，再用計數排序就比較繁瑣了，比如有10個數15,23,78,56,3,67,52,23,99,11，它們的范圍大小是0–99，此時用計數排序的話是需要統計1出現的次數，2出現的次數，……，98出現的次數，99出現的次數，這就很費事了。對于這種情況，我們想出了一個辦法，就是桶排序，先準備10個桶，0-9放到第一個桶里面，10-19放到第二桶里面，……，90-99放到第十個桶里面，然后每個桶里面進行排序，具體排序可以選擇插入排序、選擇排序或者其他排序方法都可以，然后再從10個桶里面依次把數收回來，這樣整體上就排序了。如果數據特別多還可以采取多級桶排序，比如要是有100個數，范圍是0-999，就可以采取二級桶排序，先用大桶，0-99一個桶，100-199一個桶，……，900-999一個桶，一共10個大桶，大桶里面再用小桶，10個數的范圍為一個小桶。先在小桶里面排序，然后把一個大桶里面的所有小桶的數收起來，再把所有大桶的數收起來，這樣就排好序了。

非比較排序中還有一種排序，叫基數排序，基數排序比較復雜，也不太好理解，我們先簡單地講講。基數排序只能用于非負整數的排序，基數排序是按位數進行多輪排序的，按照個位十位百位千位的次序進行多輪排序，先按照個位進行排序，再按照十位上的數字進行排序，……，直至到最高位，每一輪的排序方法都要選擇穩定排序方法，最后順序就排好了。大家可能有兩個疑問，為什么要從個位進行排序，不從高位往下進行排序，為啥從低位開始排序結果會是正確的呢。先說第一個疑問，為啥不從高位開始，如果從高位開始排序的話，那么這么排下去，最后的結果就是亂序的，比如說有四個數501,312,457,562，降序排序，先排百位，501,562,457,312，再排十位，562,457,312,501，再排個位，457,562,312,501，結果完全錯了。為啥錯了呢，這是因為十位會打亂百位的排序，個位會打亂十位的排序。如果想要結果正確的話，就需要我們進行局部排序，不是所有的十位在一起排序，而是百位相同的數十位一起排序，百位不同的數它們之間十位就不排序了。所以你還要添加數據記錄這些情況，這樣這個排序就變成了2級桶排序了，就不是基數排序了。而桶排序的麻煩點就在于，桶的操作是比較復雜的，因為每個桶放入多少個數據是不確定的，所以桶排序一般都要使用鏈表結構。基數排序就是要避免桶的操作。我們再來說第二個疑問，為啥從低位到高位排序是正確的，501,312,457,562，先排個位，457,312,562,501，再排十位，562,457,312,501，再排百位，562,501,457,312，最終結果是正確的，為什么是正確的呢，個位排好之后，排十位，十位不同的，把值大的排到前面，這沒有問題，不用考慮個位的問題。如果十位相同，十位相同的數會集中到一起，由于這是穩定排序，個位的相對位置還會保留著，所以個位大的還在前面，十位相同個位大的在前面，排序是正確的。再排百位，也是同理，百位大的排到前面，不用看十位個位的大小如何，百位相同的數會集中排在一起，它們的十位個位就很關鍵了，由于上一輪它們的十位個位的順序就排好了，這一輪也是穩定排序，所以十位的相對位置不變，所以最終排序就是正確的。

我們再來看一下計數排序、桶排序、基數排序，這三者之間的關系，計數排序可以看做是特殊的桶排序，相當于是桶數特別大的桶排序，桶數大到一個數值一個桶。基數排序其實和其他兩者沒有啥關系，但是如果基數排序每輪的排序方法都用計數排序的話，并且只有一輪的話，那么基數排序在這種情況下就是計數排序了。基數排序和桶排序之間就沒有啥關系了，如果非要硬扯上關系，只能說它們在一些特定的情況下都可以看成是計數排序，注意這僅僅是邏輯上能看成，并不是，因為計數排序沒有桶的概念，也沒有輪的概念，而桶排序必須要有桶，基數排序必要從從低位到高位進行多輪穩定排序。（有的書上把按位數進行多輪排序都叫做基數排序，把從高位往低位排序叫做MSD基數排序，這種排序要分桶，實際上就是桶排序，把從低位往高位排序叫做LSD排序，也就是狹義上的基數排序。這種分類方法并不好，MSD和LSD并沒有相似性，前者需要分桶，后者需要內層排序是穩定排序，這樣叫只會導致概念的混亂性，讓人更難以理解。所以我們采取更普遍的叫法，桶排序就是桶排序，基數排序就只能從低位開始排序）

1.5 排序算法評價維度

一個排序算法的好壞，我們該怎么去評價呢，有哪些評價維度呢。我們可以從算法復雜度、位置穩定性、適用性三個維度來評價。

算法復雜度可以分為時間復雜度和空間復雜度，時間復雜度又分為最好時間復雜度、最壞時間復雜度和平均時間復雜度。復雜度是算法輸入規模與執行規模之間的函數，復雜度的表示方法是大O表示法，常見的復雜度有O(1) 常量復雜度, O(logn) 對數復雜度, O(n) 線性復雜度, O(nlogn) 對數線性復雜度, O(n²) 平方復雜度, O(n³) 立方復雜度,O(2ⁿ) 指數復雜度, O(n!) 階乘復雜度。關于復雜度理論，大家可以去看一些專業的書籍來學習，比如《算法導論》，這里就不多講了。空間復雜度是指排序算法為了排序而額外分配的輔助內存有多少，大部分排序算法額外分配的內存并不多，多數為O(1)，而且現在的計算機內存都非常多，所以一般情況空間復雜度不太重要。時間復雜度是評價一個算法的重要標準，最好時間復雜度是在最好的情況下算法的時間復雜度，比如數組已經排好序了，最壞時間復雜度是最壞的情況下算法的時間復雜度，比如數組完全逆序的情況下。最好最壞都是極端情況下的特殊情況，一般不太重要，重要是平均時間復雜度，它是所有情況下的平均值，也是一般情況下的復雜度，所以平均時間復雜度是評價算法的一個重要維度。

我們所說的排序算法的穩定性是指位置穩定性，不是程序的穩定性(程序有沒有BUG會不會崩潰啥的)，而是兩個數值相等的元素在排序前后的相對位置會不會改變，這對于整數來說可能看不出來，也沒啥意義，但是對于結構體來說就能看的出來，而且很有意義。比如我們要對struct student 進行排序，要求按照年齡排序，年齡相同的按照身高排序，我們就可以先進行身高排序，再進行年齡排序(穩定排序)，這樣就能達到目的了。如果年齡排序的方法不是穩定排序，就會把身高的相對性打亂，就沒有達到我們的要求。

算法的適用性也很重要，比如非比較排序的時間復雜度都很好，都是線性復雜度或者接近線性復雜度，但是非比較排序的適用條件比較苛刻，很多情況下不太適用。

1.6 比較排序的高級算法

講完了排序算法的評價維度，我們知道時間復雜度是一個很重要的維度，那么比較排序算法的最好的時間復雜度是多少呢，能不能小于O(nlogn)呢，我們是不是還有啥新的排序算法沒有發現呢？根據決策樹模型我們可以計算出來比較排序算法最好的時間復雜度是O(nlogn)，不可能比這個再好了，具體原因大家可以去看《算法導論》8.1節。我們前面講的選擇排序、插入排序、交換排序的時間復雜度都是O(n2) ，歸并排序的時間復雜度是O(nlogn)，對于前三種，其時間復雜度大于O(nlogn)，我們有沒有辦法優化算法，使其達到O(nlogn)或者接近O(nlogn)呢，有，對于選擇排序，我們優化后的算法叫做堆排序，相應的把之前的算法叫做簡單選擇排序。堆排序也是每次都選擇一個最大值放到最后一位，但是它選擇最大值的方法和簡單選擇排序不同，它利用了堆這個數據結構，堆能保留之前比較的結果，所以可以減少比較次數，從而達到優化性能的目的。對于交換排序，我們優化后的算法叫做快速排序，之前的算法可以叫做簡單交換排序，業界都叫做冒泡排序。冒泡的問題在于只能相鄰的元素做比較并交換，一個數據每次移動的位置只有一位，效率很低。快速排序采取的方法是選取一個元素作為key，每個人都和它進行比較，比它小的都移動到它左邊，比它大的都移動到它右邊，這樣就大大的提高了移動的效率。對于插入排序，優化之后的算法叫做希爾排序，之前的算法叫做簡單插入排序。插入排序的特點是它對接近排序的序列效率特別高，對于比較雜亂的序列效率就要低很多。希爾排序利用了插入排序的這個特點，它先對整個數組進行分組插入排序，當分組數比較多的時候，一輪分組插入排序的效率是接近O(n)的，然后逐步降低分組的數量進行插入排序，最后當分組數為1的時候，也就是整個序列就分為一個組，就是直接插入排序了，此時整個數組比較接近排序狀態，插入排序的效率很高。這幾個算法的邏輯都非常復雜，這里只是簡單介紹一下，第二章里會進行詳細的講解。

1.7 遞歸性與原地性

排序算法的實現還有兩個特征，遞歸性和原地性。遞歸性，一個算法實現是否是遞歸實現。原地性，算法是否在原地排序，還是分配了臨時空間把原數據騰挪過去進行排序。這兩個特點為什么不放到算法評價里面去說呢，因為我們對算法進行評價時并不太在意一個算法是否是遞歸的，是否是原地排序，這兩點是算法的屬性，是算法自身的實現邏輯所決定的。算法的評價維度是我們比較在乎的點，我們比較在乎的是算法的效率，包括時間效率和空間效率，也就是算法的時間復雜度和空間復雜度，我們有時候也在乎算法的穩定性，因為我們有時候需要算法穩定，算法的適用性我們也在乎，因為如果你的算法不適用于我們的數據，我們也用不了這個算法啊。但是我們很少會說我們需要一個排序算法它必須是遞歸的或者原地的，這聽起來有點莫名其妙。所以遞歸性和原地性我們不放入算法的評價維度中，我們把它叫做算法的實現特征。

1.8 排序算法概覽

現在我們對排序算法的分類、操作邏輯、評價維度都有了基本的了解，下面我們畫個簡單的圖，先對本文要講的所有排序算法有個大概的認識。

大家此時不必想著要對這個圖進行完全的理解，有個大概的印象簡單的理解就行。下一章我們會用C語言對每一個算法進行實現，并會具體分析它的實現邏輯以及它的復雜度和穩定性等，到本文結束的時候你對這個圖可能就理解比較深刻了。

二、排序算法實現與分析

本章用C語言實現每個排序算法，一個算法一個小節，每個小節的內容依次是算法簡介、算法描述、C語言實現、代碼分析、算法總結、時間復雜度、空間復雜度、穩定性、遞歸性、原地性。

2.1 如何分析排序算法

如何計算一個算法的時間復雜度和空間復雜度呢，這里面有嚴謹的數學和嚴密的邏輯，想要學習的同學可以去研究相關的專業書籍，本文會使用比較直觀好理解的，但是不太嚴謹的方法進行分析。

我們先說時間復雜度，對于大部分算法來說，一般都是內外雙重循環結構，外循環的復雜度一般都是O(n)，內循環復雜度和外循環復雜度的乘積就是整個算法的復雜度。內循環復雜度有幾種情況，如果內循環復雜度每輪都是個固定值，那就很簡單，比如內循環總是循環n次，那么內循環復雜度就是O(n)，算法的復雜度就是O(n²)。如果內循環的復雜度是O(logn)，那么算法的復雜度就是O(nlogn)。但是很多時候內循環的執行次數往往是變化的，有的是遞增序列從1到n，有的是遞減序列從n到1，此時我們可以算一下內循環的平均執行次數，(n+1)*n/2/n = 0.5n+0.5，忽略常量和系數，內循環的復雜度就是O(n)，此時算法的復雜度就是O(n²)，這種情況比較常見。還有一些特殊情況，對于有些特殊數列，內循環的條件執行一次就結束了，內循環的復雜度就是O(1)，所以算法的復雜度是O(n)。還有一種情況是內循環第一輪執行了n次，外循環一次就結束了，此時算法復雜度也是O(n)。

對于遞歸算法來說，要看它的遞歸樹層數和每層的時間復雜度，我們畫個圖看一下。

我們可以看到每一層的數據規模之和都是n，而樹的高度一般是logn，所以遞歸算法的時間復雜度一般都是O(nlogn)，只要樹別退化成線性結構。如果退化了，樹的高度就是n，那么算法復雜度就變成了O(n²)了。

我們再來看空間復雜度，如果我們分配的變量是簡單變量，與輸入規模n無關，那么這個變量本身的空間復雜度就是O(1)，如果它分配在外層循環里，它的復雜度并不會乘以n，因為循環的每一輪它都銷毀重建了，它并不會累積。如果它出現在內循環里，它的復雜度既不會乘以n，更不會乘以n²，這點可能難以理解。我們先只看內循環，和剛才講的道理一樣，它一直在銷毀重建，所以復雜度還是O(1)，再把內循環當成一個整體，它在外循環里也是不斷地銷毀重建，所以復雜度還是O(1)。所以對于雙重循環結構來說，只要定義都是簡單變量，空間復雜度就一定是O(1)，推廣一下對于任意n層循環也是如此。

遞歸調用的空間復雜度最好的情況也至少是O(logn)，這是因為遞歸調用是要傳遞參數的，參數會不停地壓棧一直到遞歸樹的最深處，所以空間復雜度至少是O(logn)。如果在遞歸前定義了簡單變量，效果和參數是一樣的，空間復雜度還是O(logn)。如果在遞歸調用后面定了簡單變量，則這個變量不會累積，空間復雜度是O(1)，如果定義的不是簡單變量，而是和輸入長度n相關的數組變量，則其空間復雜度是O(n)。

如何判斷一個算法是不是穩定的呢？非原地算法一般都是穩定的，或者可以實現成穩定的。而原地算法要想實現排序就必須交換元素，如果算法只交換相鄰的元素，那么算法一定是穩定的，假設一個數列里面有兩個5，把前面的叫做A5后面的叫做B5吧，B5要想跑到A5前面就必須先不停地交換到緊挨著A5，然后再和A5進行交換，但是排序算法都是在數據大于或者小于的時候才可能進行交換，A5等于B5，是不會執行交換的，所以B5不可能跑到A5前面，所以只交換相鄰元素的算法一定是穩定算法。如果算法可能交換不相鄰的元素，比如B5和A5前面的3交換了，那么A5和B5的順序就交換了。注意必須在任何情況下都穩定才能叫做穩定排序，只要有一種情況下不穩定那就是不穩定排序。交換不相鄰元素不一定能導致這個數列的排序結果不穩定，但是一定存在一個數列它的排列結果是不穩定的。所以，交換不相鄰元素的排序是不穩定排序。

2.2 簡單選擇排序

簡單選擇排序是最簡單最直接的排序方法，先通過全員比較找到最小的那個值放在首位，然后排除首位，在剩余的數里面全員比較放到剩余的首位，以此類推，直到所有元素都排好序。

算法描述： 遍歷整個數組[0-n)，通過比較找到最小的數，放在第0位，再遍歷[1–n)，找到最小的數，放在第1位，再遍歷[2-n)，找到最小的數，放到第2位，……，直到遍歷[n-2,n)，找到最小的數，放到第n-2位，排序完成。

C語言實現：

void select_sort(int arr[], int nr){  for(int i = 0; i < nr-1; i++){    int min= i;    for(int j = i+1; j < nr; j++){      if(arr[min] > arr[j])        min= j;    }    int tmp = arr[i];    arr[i] = arr[min];    arr[min] = tmp;  }}

代碼分析： 通過雙重循環，外循環從0遍歷到nr-2，外循環確定內循環的起點，內循環從外循環的i+1遍歷到nr-1，外循環中定義 min = i，先假定內循環的起點就是最小值，內循環中，不斷去與之前記錄的最小值的下標所對應的值進行比較，如果發現有更小的值，則更新最小值下標為j，內循環結束后，min代表當前輪中最小值的下標，通過tmp變量交換arr[i]與arr[min]，把最小值交換到當前輪的首位。外循環結束，整個序列就是升序排序了。

算法總結： 雙重循環，同向而行，外循環右缺，內循環左缺。(同向而行指的是內外循環的index都是++或者–，右缺指的是index值到nr-2，左缺指的是內循環的index是外循環的index+1，下同，不再贅述)

時間復雜度： 外循環是O(n)，內循環是遞減序列是O(n)，所以算法復雜度是O(n²)，內外循環的執行都是必然的，不存在特例，所以最好最壞平均時間復雜度都是O(n²)。

空間復雜度： 雙重循環，只定義了一個簡單變量，所以空間復雜度是O(1)。

穩定性： 每次交換元素時都很大可能交換的是不相鄰元素，所以簡單選擇排序是不穩定的。

遞歸性： 非遞歸。

2.3 堆排序

堆排序是利用堆這種數據結構進行排序的一種算法。堆是一個近似完全二叉樹，并且對于大頂堆來說每個子節點的值都小于等于它的父節點，對于小頂堆來說每個子節點的值都大于等于它的父節點。堆排序是對簡單選擇排序的一種優化，簡單選擇排序的問題在于它的比較次數太多，因為它每次比較完一遍之后只留下了最小值下標信息，其他比較信息都丟了，導致比較次數是O(n²)。堆排序利用堆的數據結構，每次選擇出來一個最大值之后，之前的很多比較數據還保留在堆結構中，從而減少了比較次數。堆排序的總體邏輯和簡單選擇排序差不多，我們以大頂堆升序排序為例說明，先把數組建立為大頂堆，然后把堆頂也就是0號元素和最后一位元素交換，然后把[0 – nr-2]看做一個堆重新建立大頂堆，此時0號元素又是最大值，和nr-2位置交換，然后再縮小堆的范圍，再重建大頂堆，再把堆頂和nr-3交換，以此類推，直到堆頂和位置1交換，整個數組就排序完成了。堆排序的難點在于理解堆的數據結構，在于理解是如何建堆和調堆的。

堆是一個樹狀結構，但是卻是用數組表示的，它的節點連接是隱含在下標中的。每個節點(根節點除外)的父節點都等于自己的(index-1)/2，每個節點的左子節點(如果存在的話)等于自己的 index2 + 1，右子節點(如果存在的話)等于 index2 + 2。如下圖所示，可以幫助我們理解堆的結構，把堆的數組結構轉化拆分為樹形結構，可以很清楚地看到堆的父子節點之間的下標的關系。

算法描述： 算法的第一步是要建立大頂堆，我們接著上圖講述如何建立大頂堆。堆的建立是從最后一個非葉子節點開始調堆，一直往前調，直到最后對根節點進行調堆，然后大頂堆就建成了。最后一個非葉子節點就是最后一個葉子節點的parent，也就是 (nr-1)/2 == nr/2 - 1，對于圖中來說就是index 4，也就是說對index 4, index 3, index 2, index 1, index 0，依次調堆，這個大頂堆就建成了。為什么要從下往上調堆呢，因為只有子樹是合格堆了再對自己調堆，才能保證自己和子樹都是合格堆。如果子樹不是合格堆而堆自己進行調堆的話，是不能把自己調成合格堆的。調堆的邏輯是，先看自己的左子和右子誰大，誰大就和誰交換值，這樣自己就是三者之間的最大值了，同時又因為左子和右子都是合格堆，所以左子是左子樹的最大值，右子是右子數的最大值，所以自己現在是自己樹上的最大值，自己就是個合格堆了，被交換的左子或者右子此時就不一定是合格堆了，所以再對其進行遞歸調堆。整個調堆過程如下圖所示：
?調堆完成之后，把堆頂和最后一個元素互換，最后一個元素就是最大值了。再把[0 – nr-2] 看成一個堆，此時index 1 和 index 2 都是一個合格的大頂堆，只有index 0 不是，因此只對 index 0 進行一次調堆就可以了。如下圖所示：
至此我們已經把最后兩個元素排列好了，以此類推，不停地對index 0調堆，與當前尾元素互換，直至最后就能把整個數組排列好。

C語言實現：

static void heap_adjust(int arr[], int length, int node){  int key = arr[node];  while(1){    int child = node*2 + 1;    if(child >= length)      break;
    if(child+1 < length && arr[child+1] > arr[child])      child++;    if(arr[child] <= key)      break;
    arr[node] = arr[child];    node = child;   }  arr[node] = key;}
void heap_sort(int arr[], int nr){  for(int node = nr/2 - 1; node >= 0; node--)    heap_adjust(arr, nr, node);
  for(int length = nr-1; length > 0; length--){    int tmp = arr[0];    arr[0] = arr[length];    arr[length] = tmp;    heap_adjust(arr, length, 0);  }  }

代碼分析： 首先有個輔助函數heap_adjust就是用來調堆的，它的操作邏輯就是上圖中所說的調堆邏輯。主函數heap_sort，第一個for循環建立大頂堆，從最后一個非葉子節點開始依次調堆，直至對index 0進行調堆，整個大頂堆就建立完成了。第二個for循環，先把堆頂也就是index 0和當前的堆尾進行交換，然后對index 0進行調堆，此時傳遞堆大小是length，也就是堆尾是length-1，也即是把剛才的堆尾排除在外了。第二次循環，先把length–，此時index 0是個合格的大頂堆，再把index 0 和堆尾交換，然后再對index 0 進行調堆。循環執行完之后，整個數組就是升序排序了。

算法總結： 兩個for循環，第一個for循環建立大頂堆，循環范圍是[nr/2-1 – 0]，第二個for循環不斷地交換堆頂和尾元素，并重建大頂堆，循環范圍是[nr-1 – 1]。

時間復雜度： 先看heap_adjust的時間復雜度，它的操作次數就是樹的高度，所以復雜度是O(logn)，第一個for循環執行了nr/2 個 heap_adjust，所以時間復雜度是O(nlogn)。第二個for循環是nr個heap_adjust，時間復雜度也是O(nlogn)，兩個O(nlogn)加起來還是O(nlogn)，所以堆排序的時間復雜度是O(nlogn)，沒有什么特殊情況，所以最好最壞平均時間復雜度都是O(nlogn)。

空間復雜度： 兩個雙重循環，只定義了幾個簡單變量，所以空間復雜度是O(1)。

穩定性： 大部分操作都是非相鄰元素交換，所以堆排序是不穩定的。

遞歸性： 非遞歸。

原地性： 原地。

我們可以發現，簡單選擇排序和堆排序有幾個共同點：
1.最好最壞平均時間復雜度都是相同的，不存在特殊的排序情況
2. 空間復雜度都是O(1)
3.兩者都是不穩定排序

2.4 簡單插入排序

簡單插入排序的方法是逐步構建已排序序列，把未排序區的元素一個一個地往排序區插入，在排序區里面從后往前搜索，找到自己的位置并插入，它之后的元素各往后移動一位，當未排序區的元素清空時，排序就完成了。簡單插入排序在元素數量少時是一種非常高效的排序。

算法描述： [0 – 0] 是已排序區，[1 – n-1] 是未排序區，把1號元素插入已排序區，根據大小插在0號元素之前或者之后，形成新的排序區[0 – 1]和未排序區[2 – n-1]，再把2號元素根據大小插入排序區，可能在0之前，在0和1之間，或者1之后，形成新的排序區[0 – 2]和未排序區[3 – n-1]。一直如此操作，直到未排序區變為空集，排序完成。

C語言實現：

void insert_sort(int arr[], int nr){  for(int i = 1; i < nr; i++){    int j, key = arr[i];    for(j = i; j > 0 && arr[j-1] > key; j--)      arr[j] = arr[j-1];    arr[j] = key;  }}

代碼分析： 外層循環表達的是未排序區，index從1開始，到nr-1結束，初始排序區是[0 – 0]，就一個元素，肯定是已排序的。取未排序區的第一個數作為待插入數，保存在局部變量key中，未排序的首位空間轉換為已排序區的空間，根據key掃描已排序空間，比key大的都右移一位，直到遇到不比key大的數值為止。內循環結束后，j的值就是key要插入的位置，這個位置之前的值都小于等于key，之后的位置都大于key。執行arr[j] = key，完成插入。外循環結束后，未排序區為空，排序成功。

算法總結： 雙重循環，背道而行，數據不斷右移為key騰挪位置，直到找到key應該在的位置，最后插入。

時間復雜度： 外循環復雜度是O(n)，內循環的執行次數是有條件的，假設條件總成立，也就是數列是逆序的情況，內循環的復雜度是O(n)，所以最壞時間復雜度都是O(n²)。假設內循環的條件總是不成立，也就是數列已排序的情況，內循環的復雜度是O(1)，所以最好時間復雜度都是O(n)。平均情況也就是一般情況，內循環里面的操作有一半的概率會執行，也就是最壞情況的一半，所以平均時間復雜度還是O(n²)。

空間復雜度： 雙重循環，定義了兩個簡單變量，所以空間復雜度是O(1)。

穩定性： 邏輯上可以看成是key不斷地和前面的元素進行交換，也是屬于只交換相鄰元素，所以簡單插入排序是穩定的。

遞歸性： 非遞歸。

原地性： 原地。

簡單插入排序和簡單選擇排序對比一下，最好時間復雜度，前者是O(n)，后者是O(n²)，平均時間復雜度雖然都是O(n²)，但是前者的系數是1/4，后者的系數是1/2，穩定性，前者穩定，后者不穩定，所以簡單插入排序完勝簡單選擇排序。

2.5 希爾排序

希爾排序是對簡單插入排序的一種改進，又叫做縮小增量排序，也叫分組插入排序。它對插入排序的改進是基于插入排序的兩個特點，1是插入排序對于越接近排好序的數列效率越高，2是插入排序一般情況下是低效的，因為內循環一次只能把數據移動一位。針對插入排序的特點和缺點，我們可以這樣改進它。對數列進行分組插入排序，比如先分5組分別進行插入排序，再分3組分別進行插入排序，再分1組也就是不分組進行插入排序。也就是說希爾排序最后要進行一次插入排序，你也許會覺得之前就進行了很多次操作，最后還要進行一次插入排序，效率肯定比插入排序差。但是這是不對的，因為插入排序的效率受它的輸入數據的有序性影響很大，如果輸入數據是已經排序的，那么插入排序的效率就是O(n)，輸入數據越接近已排序，插入排序的效率就越接近O(n)。前面的分組插入排序就是為了使整個數組更接近排序狀態。它是第一個突破O(n²)的算法。

算法描述： 增量d是一個遞減序列，最后遞減為1，d序列的選擇并不是一個絕對的事情，一般會選擇為初始值為nr/2，并不停地除以2。d序列應該盡量使同一組的數不再分配到同一組，也就是d序列要盡量避免16,8,4，2,1，這種序列，因此我們每次都 d |= 1，把d變為奇數。假設nr是10，d第一次是5，進行5組插入排序，0,5一組，1,6一組，2,7一組，3,8一組，4,9一組，分別進行插入排序。第二次d是3，0,3,6,9一組，1,4,7一組，2,5,8一組，分別進行插入排序。第三次d是1，進行簡單插入排序。

C語言實現：

void shell_sort(int arr[], int nr){  for(int d = nr/2; d > 0; d /= 2){    d |= 1;    for(int i = d; i < nr; i++){      int j, key = arr[i];      for(j = i; j >=d && arr[j-d] > key; j -= d)        arr[j] = arr[j-d];      arr[j] = key;    }  }}

代碼分析： 三重循環，最外層循環，是d增量循環，從nr/2開始，每次減半，到1停止。內層兩層for循環是標準的簡單插入排序算法，加入了分組考慮。

算法總結： 三重循環，外層循環是d增量每次減半，內兩層循環是簡單插入排序。

時間復雜度： 希爾排序的時間復雜度是和增量序列有著密切的關系的，最好時間復雜度可以達到O(n)，最壞時間復雜度可以到O(n2)，如果按照Sedgewick提出的增量序列，最壞時間復雜度和平均時間復雜度可以達到O(n^1.3)。目前數學上還沒有證明希爾排序的最壞時間復雜度的下限是多少，因為不太好證明哪個增量序列是最優的，不太好計算平均情況。

空間復雜度： 三重循環，只定義了兩個簡單變量，顯然空間復雜度是O(1)。

穩定性： d不為1的時候發生了不相鄰元素交換的情況，所以希爾排序是不穩定的。

遞歸性： 非遞歸。

2.6 冒泡排序

冒泡算法的邏輯是從一端走向另一端的過程中，不斷地比較相鄰的元素，把較小的或者較大放到前面，這樣一遍下來之后，最小值或者最大值就到了數組的某一端，把這個值扣除，剩下的數組元素再按這個邏輯走一遍，次大的數又浮動到一端了，一直這樣下去，數列就排序好了。

算法描述： 我們以升序排序向左浮動為例進行講解，不斷的進行(nr-1, nr-2),(nr-2, nr-3),……,(2, 1),(1, 0),比較并把較小值往前交換，這樣一輪下來，最小值就到了位置0了。然后下一輪進行(nr-1, nr-2),(nr-2, nr-3),……,(2, 1)比較并把較小值往前交換，把剩余的數中最小值交換到了位置1，然后再進行(nr-1, nr-2),(nr-2, nr-3),……,(3, 2)比較并交換，直到最后一輪進行(nr-1, nr-2)比較并交換，這樣整個數列就排序好了。這個過程很像氣泡往上冒泡的過程，所以就叫做冒泡排序。

C語言實現：

void bubble_sort(int arr[], int nr){  for(int i = 0; i < nr-1;){    int pos = nr-1;    for(int j = nr-1; j > i; j--){      if(arr[j] < arr[j-1]){        int tmp = arr[j];        arr[j] = arr[j-1];        arr[j-1] = tmp;        pos = j;      }    }    i = pos;  }}

代碼分析： 雙重循環，外層循環控制每次冒泡的頂端，從0往nr-1方向不斷地壓縮空間，內層循環從最低端往上冒泡，冒泡的頂端被外層循環的index控制。內層循環比較后面的值和前面的值，如果后面的值較小，就把它交換到前面去。這個算法采取了一個優化，就是外層循環index的遞進不再是++了，而是內層循環最后一次交換的下標值pos。pos是每輪最后一次發生交換的下標值，代表著剩余區間的所有元素都比這個pos之前的值要大，下一次冒泡的頂端就沒有必要超過這個pos了。

算法總結： 雙重循環，相向而行，相鄰比較，順序不對就交換。可以簡單總結為 鄰換對開 四個字，鄰換，只有相鄰的元素才會進行比較并有可能交換，對開，內外循環的index的增加方向是相反的。

時間復雜度： 我們這個冒泡排序是優化版的冒泡排序。最好的情況是已排序的情況，第一輪的時候，內循環執行了nr-1次，if語句一直不成立，pos=j一直不執行，外循環第二輪就不執行了，所以最好時間復雜度是O(n)。最壞的情況是完全逆序，內循環的if語句一直成立，pos=j一直執行，外循環的執行次數是O(n)，內循環的執行次數是遞減序列是O(n)，所以最壞時間復雜度是O(n²)。平均情況下內循環執行的概率是一半，所以平均時間復雜度是O(n²)。

空間復雜度： 雙重循環，只定義了一個簡單變量，所以空間復雜度是O(1)。

穩定性： 只有相鄰的元素才有可能交換，所以冒泡排序是穩定的。

遞歸性： 非遞歸。

2.7 快速排序

快速排序是對冒泡排序的一種改進，是屬于交換排序的一種，它的基本操作也是比較和交換，但是它比較的對象和交換的方式不同，冒泡排序是相鄰的元素比較并交換，快速排序是選擇一個key，所有的數都和這個key比較，比它小的移動到它左邊，比它大的移動到它右邊。然后再對左邊的區間和右邊的區間重復進行這種操作，一直遞歸下去，直到區間只有一個元素。所以遞歸完成并返回后，數組就排序好了。

算法描述： 選擇一個元素作為key，把所有小于這個key的都移動到左邊，大于這個key的都移動到右邊，這個key放在左區和右區的中間，這個操作叫做分割(partition)，然后分別對左區和右區遞歸這個操作。怎么選擇這個key有很多種方法，本文中是直接取中間index的值作為key。

C語言實現：

static void swap(int arr[], int i, int j){  int tmp = arr[i];  arr[i] = arr[j];  arr[j] = tmp;}
static void do_quick_sort(int arr[], int left, int right){  if(left >= right)    return;
  swap(arr, left, (left+right)/2);  int index = left;  for(int i = left+1; i <= right; i++)    if(arr[i] < arr[left])      swap(arr, ++index, i);  swap(arr, left, index);
  do_quick_sort(arr, left, index-1);  do_quick_sort(arr, index+1, right);}
void quick_sort(int arr[], int nr){  do_quick_sort(arr, 0, nr-1);}

代碼分析： 先寫個輔助函數swap用來交換元素。do_quick_sort函數，輸入參數是數組首地址、區間左index、區間右index，區間是左閉右閉區間。為什么函數的簽名是這樣的，和之前的排序算法的簽名不太一樣，之前參數都是arr和hr。這是因為快排是遞歸算法，所以它的參數要接收當前要處理的區間范圍。do_quick_sort函數里面，首先要做的是遞歸結束檢查，遞歸是什么時候結束呢，當區間只剩一個元素或者是空區間的時候直接返回。繼續走下去的話說明區間至少有兩個元素，可以做一輪分割。分割，我們選一個元素作為key，這里有很多種選法，我們選擇區間最中間的元素作為key，也就是 (left+right)/2處的值，然后把這個key交換到區間的最左側。然后我們以這個left處的值為key，對區間[left+1 – right]進行分割，使得最終這個區間以某個點為界，左部分的值都小于這個key，右部分都大于等于這個key。這是怎么做到的呢，這就是函數里面 for循環加 if 加 swap三個語句的神奇之處了。首先讓index = left，[left+1 – index]代表的是左區，是小于key的值，[index+1 – i-1]代表的是右區，是大于等于key的值，[i – right]代表的是還未處理的區域，開始的時候，左區是空集，右區也是空集，未處理區是全集。每次循環的時候，i++，未處理區減少一個元素，處理區增加一個元素，增加的這個元素是給左區還是右區呢，要判斷它是否小于key，小于key的話，++index，左區增加一個元素，右區由于i++了，所以右區的數量不變，swap交換的是待處理的位置i和之前右區的最左端，相當于是i增加了，右區先增加了一個元素，如果它不比key小的，就什么也不操作，i就留作右區了，右區增加一個元素，左區不變。如果它比key小的話，左區的最右端和最左端交換，index增加了1，把右區的一個位置劃給了左區，右區相當于往右平移了一位。當循環完成之后，未處理區為空，整個區域分成了三個部分，left，[left+1 – index], [index+1, right], 左區都是小于key的，右區都是大于等于key的，然后再做一個swap(arr, left, index)操作，這樣區域就變成了[left – index-1], index, [index+1, right], 很容易看出，左區都是小于key的，右區都是大于key，key自己在中間index的位置處，完美的完成了分割。下面就是遞歸調用了，分別對左區和右區進行遞歸調用。現在我們再來看一個問題，我們進來的時候整個區域的大小是大于等于2的，現在分割之后，左區或者右區有可能是空集的，所以left有可能大于index-1，index+1有可能大于right，所以函數開頭處的>=檢測是有必要的。為了讓快排算法和其他算法的接口兼容，我們把具體做算法的函數叫做do_quick_sort，再向外提供一個接口quick_sort。

網上大部分的快排算法實現都是一個while循環內嵌兩個并列的while循環，代碼比較冗長。本文的快排實現是C語言之父Dennis Ritchie 在《The C Programming Language》書中所寫的，代碼非常簡潔精巧，但是理解起來非常費勁。因此我們畫個圖來輔助理解：
算法總結： 遞歸算法都有分治合的特點，快排是先分后治沒有和。分是把整個區間分成兩個區間，一個區間都小于key，一個區間都大于等于key，這個是快排的重點和難點。治就是遞歸調用，遞歸調用在函數的尾部，所以是后遞歸算法。分的特點是先把key交換到最左邊，然后進行分，最后再把key交換到臨界點。

時間復雜度： 快排是遞歸算法，時間復雜度主要看遞歸樹的深度，那么遞歸樹深度是多少呢，如果不巧的話，每次分割的區間都是小于某個常量長度的區間和另一個區間的話，那么遞歸樹的深度就是O(n)的，所以最壞時間復雜度是O(n²)，最好的情況是每次區間都是平分的，這樣遞歸樹的高度就是O(logn)的，所以最好時間復雜度是O(nlogn)。如果每次分割都是成比例的，就算是比例再小，達到1:9，甚至1:99，遞歸樹的高度也是O(logn)的，所以平均時間復雜度是O(nlogn)。

空間復雜度： 在遞歸前定義了一個簡單變量，遞歸后無變量定義，所以其空間復雜度就是遞歸樹的高度，遞歸樹高度最壞的情況是O(n)，最好的情況和平均情況是O(logn)，所以快排的空間復雜度最壞情況是O(n)，最好和平均是O(logn)，這是快排和其它排序算法一個顯著的不同，其他排序算法的空間復雜度在所有的情況下都是一樣的。

穩定性： 由于存在非相鄰元素交換的情況，所以快速排序是不穩定的。

遞歸性： 后遞歸，遞歸調用在函數的尾部叫后遞歸。

2.8 歸并排序

歸并排序是先把最小的子序列給排好序，然后不斷的合并子序列，最終達到排序的目的，歸并排序是一種遞歸排序，采用的是分治合的思想，分是簡單直接的分，直接平均分成兩份，治是遞歸調用自己，合是把已經排序好的兩個子序列合并成一個有序的序列。由于是遞歸調用在前，合在后，所以歸并排序會先遞歸到最小的子序列，也就是一個元素的序列，然后一個一個合成兩個元素的序列，兩個雙元素的序列合并成一個四元素序列，或者一個雙元素序列和一個單元素序列合并成一個三元素序列，就這樣一直合并下去，直至底層函數返回，整個序列就排序好了。

算法描述： 先取序列的中點把序列分成兩個區間，分別對左右兩個區間進行遞歸調用，調用返回之后得到的是兩個已排序的序列，然后把這兩個序列合并成一個序列，合并采取的是非原地操作，把兩個區間復制到一個臨時數組中，然后左右兩個區間依次選擇最小的值復制回原區間中。由于是分成兩個區間進行遞歸，所以這個算法實現是兩路遞歸排序。

C語言實現：

static void do_merge_sort(int arr[], int left, int right){  if(left >= right)    return;  int mid = (left+right)/2;  do_merge_sort(arr, left, mid);  do_merge_sort(arr, mid+1, right);
  int count = right - left + 1;  int tmp[count];  for(int i = 0; i < count; i++)    tmp[i] = arr[left+i];
  int j = 0, jmax = mid-left+1;  int k = jmax, kmax = count;  for(int i = left; i <= right; i++)    arr[i] = j >= jmax || (k < kmax && tmp[k] < tmp[j]) ? tmp[k++] : tmp[j++];}
void merge_sort(int arr[], int nr){  do_merge_sort(arr, 0, nr-1);}

代碼分析： 入口先進行遞歸結束檢測，當區間的長度小于等于1時結束遞歸直接返回，如果區間長度大于2，繼續往下走。以中間index為分界把區間平分成兩份，分別遞歸調用，調用返回后，得到的是兩個已經排好序的序列，定義一個和區間總長度相同的臨時數組，把整個區間都復制過去，然后同時遍歷左區和右區，依次把更小的元素復制回原區間，如果某個區間先復制完了，就把另一個區間的值直接復制完。代碼使用了一定的編程技巧，使得代碼非常精巧，但是不太好理解，但是邏輯是非常簡單的，就是直接比較左區和右區的當前元素哪個小，把小的復制回原數組，并把當前元素index++。

算法總結： 先遞歸調用，再進行整合。

時間復雜度： 和快速排序的原理是一樣的，時間復雜度的關鍵點在于遞歸樹的深度，由于我們是按index分區的，所以總是能平分一個區，不存在分配不均勻的情況，所以遞歸樹的深度總是O(logn)，所以最好最壞平均時間復雜度都是O(nlogn)。

空間復雜度： 遞歸前定義了一個簡單變量，其空間復雜度是O(logn)，遞歸后定義了和n相關的數組變量，其空間復雜度是O(n)，所以空間復雜度是O(n)。

穩定性： 沒有交換操作，合并時并不會改變元素的相對位置，所以歸并排序是穩定的。

遞歸性： 前遞歸，先進行遞歸，遞歸返回后再進行合并操作。

原地性： 非原地，定義了臨時數組來存放被排序的值。

2.9 計數排序

計數排序是非比較排序中最簡單的算法，它適用于范圍比較集中的整數進行排序，我們第一章講了非比較排序的基本原理，這里就不再贅述了。

算法描述： 先把原數組clone一份叫做arr2，再計算出數列中的最大值和最小值，創建一個長度為max-min+1的counts數組，先統計數列中每個整數出現的次數，然后累加計數數組，此時counts[i]代表在原數組中小于等于i的元素的個數，然后逆序遍歷arr2，把arr2按照正確的順序放到原數列中。

C語言實現：

void count_sort(int arr[], int nr){  int arr2[nr];  int max = arr[0];  int min = arr[0];  for(int i = 0; i < nr; i++){    arr2[i] = arr[i];    if(max < arr[i])      max = arr[i];    if(min > arr[i])      min = arr[i];  }
  int length = max - min + 1;  int counts[length];  for(int i = 0; i < length; i++)    counts[i] = 0;
  for(int i = 0; i < nr; i++)    counts[arr2[i] - min]++;
  for(int i = 1; i < length; i++)    counts[i] += counts[i-1];
  for(int i = nr-1; i >= 0; i--)    arr[--counts[arr2[i]-min]] = arr2[i];}

代碼分析： 先遍歷原數組，把原數組clone一份arr2，找到原數組的最大值和最小值，然后建立一個計數數組counts用來計數，長度是max-min+1，再遍歷原數組，用元素的值減去min作為下標在counts數組中尋址，對應的counts元素++，代表這個數值的元素的個數又增加了一個，遍歷完成后，counts[i]代表在原數組中等于i的元素的個數。再累加counts，累加完成后，counts[i]代表在原數組中小于等于i的元素的個數。然后逆序遍歷arr2，把arr2按照正確的順序放到原數列中。為什么要逆序呢，這是因為counts[i]代表的是小于等于i的元素的個數，逆序的話能讓最后一個i值放到最后一個位置中去，這樣就不會顛倒值相等的元素的順序，能保存排序的穩定性。

算法總結： 先遍歷原數組，找到最大值最小值，再遍歷原數組，統計各個數值出現的次數，再累加計數數組，再逆序遍歷arr2數組回寫到原數組。

時間復雜度： 遍歷3次原數組，遍歷2次計數數組，原數組的長度是n，計數數組的長度是k，k = max-min+1，是一個與n無關的數，所以時間復雜度是O(n+k)，不存在什么特殊情況，所以最好最壞平均時間復雜度都O(n+k)。

空間復雜度： 定義了一個計數數組，長度是k，k = max-min+1，是一個與n無關的數，clone了原數組，長度是n，所以空間復雜度是O(n+k)。

穩定性： 計數排序是穩定的，代碼分析中講了保持排序穩定的原因。

遞歸性： 非遞歸。

2.10 桶排序

桶排序是也是一種非比較排序，它比較適合那些數據分布比較均勻的數據，其基本思想是根據數據的范圍，把其分為N個桶，然后把所有數據放入相應的桶中，每個桶內再進行排序，然后把所有的桶按順序收回數據，整個數據就排序好了。

算法描述： 把數據分到N個桶中，每個桶中再進行排序。

C語言實現：
暫無

代碼分析： 暫無。

算法總結： 暫無

時間復雜度： 最好最壞平均時間復雜度都是O(n+k)。

空間復雜度： 空間復雜度是O(n+k)。

穩定性： 桶排序是穩定的。

遞歸性： 非遞歸。

2.11 基數排序

基數排序也是一種非比較排序，它只適用于對非負整數進行排序，它的基本原理是先對個位進行排序，再對十位進行排序，再對百位進行排序，……，直至最高位，對每位進行排序的方法一定要選擇穩定排序，比如計數排序。基數排序不一定要把整數看成是10進制的，可以把它當成任意進制的數來處理都行。

算法描述： 從最低位開始進行穩定排序，……，直至最高位。

C語言實現：

void radix_sort(int arr[], int nr){  int max = arr[0];  for(int i = 1; i < nr; i++)    if(max < arr[i])      max = arr[i];
  int d = 1;  while((max = max >> 4) != 0 ) d++;
  for(int k = 0; k < d; k++){    int arr2[nr];    for(int i = 0; i < nr; i++)      arr2[i] = arr[i];
    int length = 1 << 4;    int counts[length];    for(int i = 0; i < length; i++)      counts[i] = 0;
    for(int i = 0; i < nr; i++)      counts[(arr2[i] >> 4*k) & 0x0F]++;
    for(int i = 1; i < length; i++)      counts[i] += counts[i-1];
    for(int i = nr-1; i >= 0; i--)      arr[--counts[(arr2[i] >> 4*k) & 0x0F]] = arr2[i];  }}

代碼分析： 先計算數列中的最大值，再計算出它的位數，本代碼是按照16進制來看待的，這樣方便運算。然后從低位到高位依次遍歷，每次遍歷都采取計數排序，這個計數排序它的n還是外部的n，但是它的k是常量16，因為它是按16進制來處理的，一位16進制數最大的值是15，最小是0。計數排序的邏輯我們就不再贅述了。

算法總結： 外層循環按照從低位到高位的順序進行循環，內層是計數排序。

時間復雜度： 外層循環的次數是位數k，內層循環是計數排序，由于此時計數排序的k是常量，所以內層循環的復雜度是O(n)，由于不存在特殊情況，所以最好最壞平均時間復雜度都是O(nk)。

空間復雜度： 內循環的空間復雜度是O(n)，外循環不會累積內循環的存儲空間，所以空間復雜度是O(n)。

穩定性： 每輪排序都是用的穩定排序，所以最終排序也是穩定的，所以基數排序是穩定的。

遞歸性： 非遞歸。

三、總結回顧?

至此，我們已經全面詳細講解了所有常見的排序算法，包括算法的原理、實現方法、以及各種性質的分析(桶排序除外)。下面我們先畫個圖回顧一下。

我們從上到下、從左到右再把這個圖看一遍，仔細回憶一下各個算法的基本原理、實現方法、和對它各種性質的分析。從左到右，排序算法先根據是否使用比較分為比較排序和非比較排序，比較排序根據其基本原理的不同分為選擇排序、插入排序、交換排序、歸并排序。歸并排序是遞歸排序，其時間復雜度是O(nlogn)，已經非常優秀了，沒有改進空間了，而選擇排序、插入排序、交換排序的時間復雜度都是O(n²)，還有改進空間，于是分別改進出了堆排序、希爾排序、快速排序。非比較排序中最簡單最直接的是計數排序，它為了處理數列中有重有漏的問題而采取計數方法。桶排序是對分布均勻的數據分桶進行排序。基數排序是一種比較巧妙的排序，一般人都想不到還能這樣排序。

圖中沒有寫它們的適用性，我們在這里說一下。比較排序的適用性非常強，可適用于任何數據。非比較排序的適用性比較窄，計數排序適用于對范圍比較集中的整數進行排序，桶排序適用于分布比較均勻的數據，基數排序適用于正整數。
我們再來看一看遞歸性、原地性與穩定性和空間復雜度之間的關系。可以看出非原地排序都是穩定排序，原地排序由于需要交換，所以相鄰交換的都是穩定排序，不相鄰交換的都是不穩定排序。非遞歸原地排序的空間復雜度都是O(1)，非遞歸非原地排序的空間復雜度都是線性的。遞歸排序的空間復雜度至少是O(logn)，因為原地排序不需要額外分配空間，所以遞歸原地排序的空間復雜度是O(logn)，而非原地排序的空間復雜度是O(n)，所以非遞歸非原地排序的空間復雜度是O(n)。

再來看時間復雜度，非比較排序中的計數排序和桶排序的平均時間復雜度都是O(n+k)，是線性的，計數排序中，如果把位數k看成是不大于15的常量，計數排序的平均時間復雜度也可以看成是線性的。比較排序中，所有的簡單排序的平均時間復雜度都是O(n²)，而復雜排序基本都是O(nlogn)，除了希爾是O(n^1.3)。選擇排序和歸并的時間復雜度不存在優化和惡化的情況。插入排序和冒泡排序存在優化的情況，當數列已經排好序時，其時間復雜度優化為O(n)。快排的時間復雜度存在惡化的情況，當區間分割總是極度不均勻時，其時間復雜度惡化為O(n²)。

所有算法中，邏輯上最難理解的是堆排序和基數排序，代碼上最難理解的是快速排序。一般情況下運行效率最高的是快排，所以快排才叫快排，很多庫的排序算法的默認實現就是快排。

參考文獻：
《Introduction to Algorithms》
《Algorithms》
《Algorithms in a Nutshell》
《An Introduction to the Analysis of Algorithms》

? ? ? ? ? ?

如需進程老師群溝通請添加

小馬微信：Linuxer2022