目錄：

一、排序算法的基本邏輯

1.1 什么是排序

1.2 排序算法分類

1.3 比較排序

1.4 非比較排序

1.5 排序算法評(píng)價(jià)維度

1.6 比較排序的高級(jí)算法

1.7 遞歸性與原地性

1.8 排序算法概覽

二、排序算法實(shí)現(xiàn)與分析

2.1 如何分析排序算法

2.2 簡(jiǎn)單選擇排序

2.3 堆排序

2.4 簡(jiǎn)單插入排序

2.5 希爾排序

2.6 冒泡排序

2.7 快速排序

2.8 歸并排序

2.9 計(jì)數(shù)排序

2.10 桶排序

2.11 基數(shù)排序

三、總結(jié)回顧

一、排序算法的基本邏輯

排序是數(shù)據(jù)結(jié)構(gòu)與算法里面最基礎(chǔ)最入門(mén)的內(nèi)容，雖然簡(jiǎn)單，但是深入研究的話里面還是有很多內(nèi)容的，今天我們來(lái)全面詳細(xì)的講一講各種排序算法的分類、原理、復(fù)雜度、穩(wěn)定性和實(shí)現(xiàn)方法。

1.1 什么是排序

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

1.2 排序算法分類

那么該怎么進(jìn)行排序的呢，最基本的方法是什么呢，最基本的方法那當(dāng)然是比較了，不比較怎么排序呢，只有比較了才能知道該誰(shuí)前誰(shuí)后?？墒钱?dāng)我看到很多算法書(shū)上都說(shuō)排序有比較排序和非比較排序，我第一眼看到的時(shí)候都驚呆了，不可能，絕對(duì)不可能。非比較還能排序，排序還能不比較，這怎么可能，絕對(duì)是瞎扯。當(dāng)我繼續(xù)看下去的時(shí)候發(fā)現(xiàn)確實(shí)能。后來(lái)我仔細(xì)思考了一下發(fā)現(xiàn)，非比較排序本質(zhì)上還是在比較，只不過(guò)它們不是在和別人比較，而是在和自己比較，在和自己的本位比較 （突然想起了上學(xué)時(shí)老師經(jīng)常說(shuō)的話，不要老是和別人比，要多和自己比，非比較排序做到了）。什么是和自己的本位比較呢，比如說(shuō)有1到9共9個(gè)數(shù)順序是亂的，1本來(lái)就該在1的位置，2本來(lái)就該在2的位置，……，9本來(lái)就該在9的位置，它們不用去和別人比，只需要去站到自己本來(lái)應(yīng)該站的位置，順序就自然就排好了。所以比較排序、非比較排序也可以叫做顯式比較排序、隱式比較排序。

1.3 比較排序

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

1.4 非比較排序

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

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

非比較排序中還有一種排序，叫基數(shù)排序，基數(shù)排序比較復(fù)雜，也不太好理解，我們先簡(jiǎn)單地講講。基數(shù)排序只能用于非負(fù)整數(shù)的排序，基數(shù)排序是按位數(shù)進(jìn)行多輪排序的，按照個(gè)位十位百位千位的次序進(jìn)行多輪排序，先按照個(gè)位進(jìn)行排序，再按照十位上的數(shù)字進(jìn)行排序，……，直至到最高位，每一輪的排序方法都要選擇穩(wěn)定排序方法，最后順序就排好了。大家可能有兩個(gè)疑問(wèn)，為什么要從個(gè)位進(jìn)行排序，不從高位往下進(jìn)行排序，為啥從低位開(kāi)始排序結(jié)果會(huì)是正確的呢。先說(shuō)第一個(gè)疑問(wèn)，為啥不從高位開(kāi)始，如果從高位開(kāi)始排序的話，那么這么排下去，最后的結(jié)果就是亂序的，比如說(shuō)有四個(gè)數(shù)501，312，457，562，降序排序，先排百位，501，562，457，312，再排十位，562，457，312，501，再排個(gè)位，457，562，312，501，結(jié)果完全錯(cuò)了。為啥錯(cuò)了呢，這是因?yàn)槭粫?huì)打亂百位的排序，個(gè)位會(huì)打亂十位的排序。如果想要結(jié)果正確的話，就需要我們進(jìn)行局部排序，不是所有的十位在一起排序，而是百位相同的數(shù)十位一起排序，百位不同的數(shù)它們之間十位就不排序了。所以你還要添加數(shù)據(jù)記錄這些情況，這樣這個(gè)排序就變成了2級(jí)桶排序了，就不是基數(shù)排序了。而桶排序的麻煩點(diǎn)就在于，桶的操作是比較復(fù)雜的，因?yàn)槊總€(gè)桶放入多少個(gè)數(shù)據(jù)是不確定的，所以桶排序一般都要使用鏈表結(jié)構(gòu)?；鶖?shù)排序就是要避免桶的操作。我們?cè)賮?lái)說(shuō)第二個(gè)疑問(wèn)，為啥從低位到高位排序是正確的，501，312，457，562，先排個(gè)位，457，312，562，501，再排十位，562，457，312，501，再排百位，562，501，457，312，最終結(jié)果是正確的，為什么是正確的呢，個(gè)位排好之后，排十位，十位不同的，把值大的排到前面，這沒(méi)有問(wèn)題，不用考慮個(gè)位的問(wèn)題。如果十位相同，十位相同的數(shù)會(huì)集中到一起，由于這是穩(wěn)定排序，個(gè)位的相對(duì)位置還會(huì)保留著，所以個(gè)位大的還在前面，十位相同個(gè)位大的在前面，排序是正確的。再排百位，也是同理，百位大的排到前面，不用看十位個(gè)位的大小如何，百位相同的數(shù)會(huì)集中排在一起，它們的十位個(gè)位就很關(guān)鍵了，由于上一輪它們的十位個(gè)位的順序就排好了，這一輪也是穩(wěn)定排序，所以十位的相對(duì)位置不變，所以最終排序就是正確的。

我們?cè)賮?lái)看一下計(jì)數(shù)排序、桶排序、基數(shù)排序，這三者之間的關(guān)系，計(jì)數(shù)排序可以看做是特殊的桶排序，相當(dāng)于是桶數(shù)特別大的桶排序，桶數(shù)大到一個(gè)數(shù)值一個(gè)桶?；鶖?shù)排序其實(shí)和其他兩者沒(méi)有啥關(guān)系，但是如果基數(shù)排序每輪的排序方法都用計(jì)數(shù)排序的話，并且只有一輪的話，那么基數(shù)排序在這種情況下就是計(jì)數(shù)排序了?；鶖?shù)排序和桶排序之間就沒(méi)有啥關(guān)系了，如果非要硬扯上關(guān)系，只能說(shuō)它們?cè)谝恍┨囟ǖ那闆r下都可以看成是計(jì)數(shù)排序，注意這僅僅是邏輯上能看成，并不是，因?yàn)橛?jì)數(shù)排序沒(méi)有桶的概念，也沒(méi)有輪的概念，而桶排序必須要有桶，基數(shù)排序必要從從低位到高位進(jìn)行多輪穩(wěn)定排序。（有的書(shū)上把按位數(shù)進(jìn)行多輪排序都叫做基數(shù)排序，把從高位往低位排序叫做MSD基數(shù)排序，這種排序要分桶，實(shí)際上就是桶排序，把從低位往高位排序叫做LSD排序，也就是狹義上的基數(shù)排序。這種分類方法并不好，MSD和LSD并沒(méi)有相似性，前者需要分桶，后者需要內(nèi)層排序是穩(wěn)定排序，這樣叫只會(huì)導(dǎo)致概念的混亂性，讓人更難以理解。所以我們采取更普遍的叫法，桶排序就是桶排序，基數(shù)排序就只能從低位開(kāi)始排序）

1.5 排序算法評(píng)價(jià)維度

一個(gè)排序算法的好壞，我們?cè)撛趺慈ピu(píng)價(jià)呢，有哪些評(píng)價(jià)維度呢。我們可以從算法復(fù)雜度、位置穩(wěn)定性、適用性三個(gè)維度來(lái)評(píng)價(jià)。

算法復(fù)雜度可以分為時(shí)間復(fù)雜度和空間復(fù)雜度，時(shí)間復(fù)雜度又分為最好時(shí)間復(fù)雜度、最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度。復(fù)雜度是算法輸入規(guī)模與執(zhí)行規(guī)模之間的函數(shù)，復(fù)雜度的表示方法是大O表示法，常見(jiàn)的復(fù)雜度有O（1） 常量復(fù)雜度， O（logn） 對(duì)數(shù)復(fù)雜度， O（n） 線性復(fù)雜度， O（nlogn） 對(duì)數(shù)線性復(fù)雜度， O（n2） 平方復(fù)雜度， O（n3） 立方復(fù)雜度，O（2n） 指數(shù)復(fù)雜度， O（n！） 階乘復(fù)雜度。關(guān)于復(fù)雜度理論，大家可以去看一些專業(yè)的書(shū)籍來(lái)學(xué)習(xí)，比如《算法導(dǎo)論》，這里就不多講了?？臻g復(fù)雜度是指排序算法為了排序而額外分配的輔助內(nèi)存有多少，大部分排序算法額外分配的內(nèi)存并不多，多數(shù)為O（1），而且現(xiàn)在的計(jì)算機(jī)內(nèi)存都非常多，所以一般情況空間復(fù)雜度不太重要。時(shí)間復(fù)雜度是評(píng)價(jià)一個(gè)算法的重要標(biāo)準(zhǔn)，最好時(shí)間復(fù)雜度是在最好的情況下算法的時(shí)間復(fù)雜度，比如數(shù)組已經(jīng)排好序了，最壞時(shí)間復(fù)雜度是最壞的情況下算法的時(shí)間復(fù)雜度，比如數(shù)組完全逆序的情況下。最好最壞都是極端情況下的特殊情況，一般不太重要，重要是平均時(shí)間復(fù)雜度，它是所有情況下的平均值，也是一般情況下的復(fù)雜度，所以平均時(shí)間復(fù)雜度是評(píng)價(jià)算法的一個(gè)重要維度。

我們所說(shuō)的排序算法的穩(wěn)定性是指位置穩(wěn)定性，不是程序的穩(wěn)定性（程序有沒(méi)有BUG會(huì)不會(huì)崩潰啥的），而是兩個(gè)數(shù)值相等的元素在排序前后的相對(duì)位置會(huì)不會(huì)改變，這對(duì)于整數(shù)來(lái)說(shuō)可能看不出來(lái)，也沒(méi)啥意義，但是對(duì)于結(jié)構(gòu)體來(lái)說(shuō)就能看的出來(lái)，而且很有意義。比如我們要對(duì)struct student 進(jìn)行排序，要求按照年齡排序，年齡相同的按照身高排序，我們就可以先進(jìn)行身高排序，再進(jìn)行年齡排序（穩(wěn)定排序），這樣就能達(dá)到目的了。如果年齡排序的方法不是穩(wěn)定排序，就會(huì)把身高的相對(duì)性打亂，就沒(méi)有達(dá)到我們的要求。

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

1.6 比較排序的高級(jí)算法

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

1.7 遞歸性與原地性

排序算法的實(shí)現(xiàn)還有兩個(gè)特征，遞歸性和原地性。遞歸性，一個(gè)算法實(shí)現(xiàn)是否是遞歸實(shí)現(xiàn)。原地性，算法是否在原地排序，還是分配了臨時(shí)空間把原數(shù)據(jù)騰挪過(guò)去進(jìn)行排序。這兩個(gè)特點(diǎn)為什么不放到算法評(píng)價(jià)里面去說(shuō)呢，因?yàn)槲覀儗?duì)算法進(jìn)行評(píng)價(jià)時(shí)并不太在意一個(gè)算法是否是遞歸的，是否是原地排序，這兩點(diǎn)是算法的屬性，是算法自身的實(shí)現(xiàn)邏輯所決定的。算法的評(píng)價(jià)維度是我們比較在乎的點(diǎn)，我們比較在乎的是算法的效率，包括時(shí)間效率和空間效率，也就是算法的時(shí)間復(fù)雜度和空間復(fù)雜度，我們有時(shí)候也在乎算法的穩(wěn)定性，因?yàn)槲覀冇袝r(shí)候需要算法穩(wěn)定，算法的適用性我們也在乎，因?yàn)槿绻愕乃惴ú贿m用于我們的數(shù)據(jù)，我們也用不了這個(gè)算法啊。但是我們很少會(huì)說(shuō)我們需要一個(gè)排序算法它必須是遞歸的或者原地的，這聽(tīng)起來(lái)有點(diǎn)莫名其妙。所以遞歸性和原地性我們不放入算法的評(píng)價(jià)維度中，我們把它叫做算法的實(shí)現(xiàn)特征。

1.8 排序算法概覽

現(xiàn)在我們對(duì)排序算法的分類、操作邏輯、評(píng)價(jià)維度都有了基本的了解，下面我們畫(huà)個(gè)簡(jiǎn)單的圖，先對(duì)本文要講的所有排序算法有個(gè)大概的認(rèn)識(shí)。

大家此時(shí)不必想著要對(duì)這個(gè)圖進(jìn)行完全的理解，有個(gè)大概的印象簡(jiǎn)單的理解就行。下一章我們會(huì)用C語(yǔ)言對(duì)每一個(gè)算法進(jìn)行實(shí)現(xiàn)，并會(huì)具體分析它的實(shí)現(xiàn)邏輯以及它的復(fù)雜度和穩(wěn)定性等，到本文結(jié)束的時(shí)候你對(duì)這個(gè)圖可能就理解比較深刻了。

二、排序算法實(shí)現(xiàn)與分析

本章用C語(yǔ)言實(shí)現(xiàn)每個(gè)排序算法，一個(gè)算法一個(gè)小節(jié)，每個(gè)小節(jié)的內(nèi)容依次是算法簡(jiǎn)介、算法描述、C語(yǔ)言實(shí)現(xiàn)、代碼分析、算法總結(jié)、時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性、遞歸性、原地性。

2.1 如何分析排序算法

如何計(jì)算一個(gè)算法的時(shí)間復(fù)雜度和空間復(fù)雜度呢，這里面有嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)和嚴(yán)密的邏輯，想要學(xué)習(xí)的同學(xué)可以去研究相關(guān)的專業(yè)書(shū)籍，本文會(huì)使用比較直觀好理解的，但是不太嚴(yán)謹(jǐn)?shù)姆椒ㄟM(jìn)行分析。

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

對(duì)于遞歸算法來(lái)說(shuō)，要看它的遞歸樹(shù)層數(shù)和每層的時(shí)間復(fù)雜度，我們畫(huà)個(gè)圖看一下。

我們可以看到每一層的數(shù)據(jù)規(guī)模之和都是n，而樹(shù)的高度一般是logn，所以遞歸算法的時(shí)間復(fù)雜度一般都是O（nlogn），只要樹(shù)別退化成線性結(jié)構(gòu)。如果退化了，樹(shù)的高度就是n，那么算法復(fù)雜度就變成了O（n2）了。

我們?cè)賮?lái)看空間復(fù)雜度，如果我們分配的變量是簡(jiǎn)單變量，與輸入規(guī)模n無(wú)關(guān)，那么這個(gè)變量本身的空間復(fù)雜度就是O（1），如果它分配在外層循環(huán)里，它的復(fù)雜度并不會(huì)乘以n，因?yàn)檠h(huán)的每一輪它都銷毀重建了，它并不會(huì)累積。如果它出現(xiàn)在內(nèi)循環(huán)里，它的復(fù)雜度既不會(huì)乘以n，更不會(huì)乘以n2，這點(diǎn)可能難以理解。我們先只看內(nèi)循環(huán)，和剛才講的道理一樣，它一直在銷毀重建，所以復(fù)雜度還是O（1），再把內(nèi)循環(huán)當(dāng)成一個(gè)整體，它在外循環(huán)里也是不斷地銷毀重建，所以復(fù)雜度還是O（1）。所以對(duì)于雙重循環(huán)結(jié)構(gòu)來(lái)說(shuō)，只要定義都是簡(jiǎn)單變量，空間復(fù)雜度就一定是O（1），推廣一下對(duì)于任意n層循環(huán)也是如此。

遞歸調(diào)用的空間復(fù)雜度最好的情況也至少是O（logn），這是因?yàn)檫f歸調(diào)用是要傳遞參數(shù)的，參數(shù)會(huì)不停地壓棧一直到遞歸樹(shù)的最深處，所以空間復(fù)雜度至少是O（logn）。如果在遞歸前定義了簡(jiǎn)單變量，效果和參數(shù)是一樣的，空間復(fù)雜度還是O（logn）。如果在遞歸調(diào)用后面定了簡(jiǎn)單變量，則這個(gè)變量不會(huì)累積，空間復(fù)雜度是O（1），如果定義的不是簡(jiǎn)單變量，而是和輸入長(zhǎng)度n相關(guān)的數(shù)組變量，則其空間復(fù)雜度是O（n）。

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

2.2 簡(jiǎn)單選擇排序

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

算法描述： 遍歷整個(gè)數(shù)組［0-n），通過(guò)比較找到最小的數(shù)，放在第0位，再遍歷［1–n），找到最小的數(shù)，放在第1位，再遍歷［2-n），找到最小的數(shù)，放到第2位，……，直到遍歷［n-2，n），找到最小的數(shù)，放到第n-2位，排序完成。

C語(yǔ)言實(shí)現(xiàn)：

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; }}

代碼分析： 通過(guò)雙重循環(huán)，外循環(huán)從0遍歷到nr-2，外循環(huán)確定內(nèi)循環(huán)的起點(diǎn)，內(nèi)循環(huán)從外循環(huán)的i+1遍歷到nr-1，外循環(huán)中定義 min = i，先假定內(nèi)循環(huán)的起點(diǎn)就是最小值，內(nèi)循環(huán)中，不斷去與之前記錄的最小值的下標(biāo)所對(duì)應(yīng)的值進(jìn)行比較，如果發(fā)現(xiàn)有更小的值，則更新最小值下標(biāo)為j，內(nèi)循環(huán)結(jié)束后，min代表當(dāng)前輪中最小值的下標(biāo)，通過(guò)tmp變量交換arr［i］與arr［min］，把最小值交換到當(dāng)前輪的首位。外循環(huán)結(jié)束，整個(gè)序列就是升序排序了。

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

時(shí)間復(fù)雜度： 外循環(huán)是O（n），內(nèi)循環(huán)是遞減序列是O（n），所以算法復(fù)雜度是O（n2），內(nèi)外循環(huán)的執(zhí)行都是必然的，不存在特例，所以最好最壞平均時(shí)間復(fù)雜度都是O（n2）。

空間復(fù)雜度： 雙重循環(huán)，只定義了一個(gè)簡(jiǎn)單變量，所以空間復(fù)雜度是O（1）。

穩(wěn)定性： 每次交換元素時(shí)都很大可能交換的是不相鄰元素，所以簡(jiǎn)單選擇排序是不穩(wěn)定的。

遞歸性： 非遞歸。

2.3 堆排序

堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序的一種算法。堆是一個(gè)近似完全二叉樹(shù)，并且對(duì)于大頂堆來(lái)說(shuō)每個(gè)子節(jié)點(diǎn)的值都小于等于它的父節(jié)點(diǎn)，對(duì)于小頂堆來(lái)說(shuō)每個(gè)子節(jié)點(diǎn)的值都大于等于它的父節(jié)點(diǎn)。堆排序是對(duì)簡(jiǎn)單選擇排序的一種優(yōu)化，簡(jiǎn)單選擇排序的問(wèn)題在于它的比較次數(shù)太多，因?yàn)樗看伪容^完一遍之后只留下了最小值下標(biāo)信息，其他比較信息都丟了，導(dǎo)致比較次數(shù)是O（n2）。堆排序利用堆的數(shù)據(jù)結(jié)構(gòu)，每次選擇出來(lái)一個(gè)最大值之后，之前的很多比較數(shù)據(jù)還保留在堆結(jié)構(gòu)中，從而減少了比較次數(shù)。堆排序的總體邏輯和簡(jiǎn)單選擇排序差不多，我們以大頂堆升序排序?yàn)槔f(shuō)明，先把數(shù)組建立為大頂堆，然后把堆頂也就是0號(hào)元素和最后一位元素交換，然后把［0 – nr-2］看做一個(gè)堆重新建立大頂堆，此時(shí)0號(hào)元素又是最大值，和nr-2位置交換，然后再縮小堆的范圍，再重建大頂堆，再把堆頂和nr-3交換，以此類推，直到堆頂和位置1交換，整個(gè)數(shù)組就排序完成了。堆排序的難點(diǎn)在于理解堆的數(shù)據(jù)結(jié)構(gòu)，在于理解是如何建堆和調(diào)堆的。

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

算法描述： 算法的第一步是要建立大頂堆，我們接著上圖講述如何建立大頂堆。堆的建立是從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始調(diào)堆，一直往前調(diào)，直到最后對(duì)根節(jié)點(diǎn)進(jìn)行調(diào)堆，然后大頂堆就建成了。最后一個(gè)非葉子節(jié)點(diǎn)就是最后一個(gè)葉子節(jié)點(diǎn)的parent，也就是 （nr-1）/2 == nr/2 - 1，對(duì)于圖中來(lái)說(shuō)就是index 4，也就是說(shuō)對(duì)index 4， index 3， index 2， index 1， index 0，依次調(diào)堆，這個(gè)大頂堆就建成了。為什么要從下往上調(diào)堆呢，因?yàn)橹挥凶訕?shù)是合格堆了再對(duì)自己調(diào)堆，才能保證自己和子樹(shù)都是合格堆。如果子樹(shù)不是合格堆而堆自己進(jìn)行調(diào)堆的話，是不能把自己調(diào)成合格堆的。調(diào)堆的邏輯是，先看自己的左子和右子誰(shuí)大，誰(shuí)大就和誰(shuí)交換值，這樣自己就是三者之間的最大值了，同時(shí)又因?yàn)樽笞雍陀易佣际呛细穸?，所以左子是左子?shù)的最大值，右子是右子數(shù)的最大值，所以自己現(xiàn)在是自己樹(shù)上的最大值，自己就是個(gè)合格堆了，被交換的左子或者右子此時(shí)就不一定是合格堆了，所以再對(duì)其進(jìn)行遞歸調(diào)堆。整個(gè)調(diào)堆過(guò)程如下圖所示：

調(diào)堆完成之后，把堆頂和最后一個(gè)元素互換，最后一個(gè)元素就是最大值了。再把［0 – nr-2］ 看成一個(gè)堆，此時(shí)index 1 和 index 2 都是一個(gè)合格的大頂堆，只有index 0 不是，因此只對(duì) index 0 進(jìn)行一次調(diào)堆就可以了。如下圖所示：

至此我們已經(jīng)把最后兩個(gè)元素排列好了，以此類推，不停地對(duì)index 0調(diào)堆，與當(dāng)前尾元素互換，直至最后就能把整個(gè)數(shù)組排列好。

C語(yǔ)言實(shí)現(xiàn)：

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）; } }

代碼分析： 首先有個(gè)輔助函數(shù)heap_adjust就是用來(lái)調(diào)堆的，它的操作邏輯就是上圖中所說(shuō)的調(diào)堆邏輯。主函數(shù)heap_sort，第一個(gè)for循環(huán)建立大頂堆，從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始依次調(diào)堆，直至對(duì)index 0進(jìn)行調(diào)堆，整個(gè)大頂堆就建立完成了。第二個(gè)for循環(huán)，先把堆頂也就是index 0和當(dāng)前的堆尾進(jìn)行交換，然后對(duì)index 0進(jìn)行調(diào)堆，此時(shí)傳遞堆大小是length，也就是堆尾是length-1，也即是把剛才的堆尾排除在外了。第二次循環(huán)，先把length–，此時(shí)index 0是個(gè)合格的大頂堆，再把index 0 和堆尾交換，然后再對(duì)index 0 進(jìn)行調(diào)堆。循環(huán)執(zhí)行完之后，整個(gè)數(shù)組就是升序排序了。

算法總結(jié)： 兩個(gè)for循環(huán)，第一個(gè)for循環(huán)建立大頂堆，循環(huán)范圍是［nr/2-1 – 0］，第二個(gè)for循環(huán)不斷地交換堆頂和尾元素，并重建大頂堆，循環(huán)范圍是［nr-1 – 1］。

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

空間復(fù)雜度： 兩個(gè)雙重循環(huán)，只定義了幾個(gè)簡(jiǎn)單變量，所以空間復(fù)雜度是O（1）。

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

遞歸性： 非遞歸。

原地性： 原地。

我們可以發(fā)現(xiàn)，簡(jiǎn)單選擇排序和堆排序有幾個(gè)共同點(diǎn)：

1.最好最壞平均時(shí)間復(fù)雜度都是相同的，不存在特殊的排序情況

2. 空間復(fù)雜度都是O（1）

3.兩者都是不穩(wěn)定排序

2.4 簡(jiǎn)單插入排序

簡(jiǎn)單插入排序的方法是逐步構(gòu)建已排序序列，把未排序區(qū)的元素一個(gè)一個(gè)地往排序區(qū)插入，在排序區(qū)里面從后往前搜索，找到自己的位置并插入，它之后的元素各往后移動(dòng)一位，當(dāng)未排序區(qū)的元素清空時(shí)，排序就完成了。簡(jiǎn)單插入排序在元素?cái)?shù)量少時(shí)是一種非常高效的排序。

算法描述： ［0 – 0］ 是已排序區(qū)，［1 – n-1］ 是未排序區(qū)，把1號(hào)元素插入已排序區(qū)，根據(jù)大小插在0號(hào)元素之前或者之后，形成新的排序區(qū)［0 – 1］和未排序區(qū)［2 – n-1］，再把2號(hào)元素根據(jù)大小插入排序區(qū)，可能在0之前，在0和1之間，或者1之后，形成新的排序區(qū)［0 – 2］和未排序區(qū)［3 – n-1］。一直如此操作，直到未排序區(qū)變?yōu)榭占判蛲瓿伞?/p>

C語(yǔ)言實(shí)現(xiàn)：

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; }}

代碼分析： 外層循環(huán)表達(dá)的是未排序區(qū)，index從1開(kāi)始，到nr-1結(jié)束，初始排序區(qū)是［0 – 0］，就一個(gè)元素，肯定是已排序的。取未排序區(qū)的第一個(gè)數(shù)作為待插入數(shù)，保存在局部變量key中，未排序的首位空間轉(zhuǎn)換為已排序區(qū)的空間，根據(jù)key掃描已排序空間，比key大的都右移一位，直到遇到不比key大的數(shù)值為止。內(nèi)循環(huán)結(jié)束后，j的值就是key要插入的位置，這個(gè)位置之前的值都小于等于key，之后的位置都大于key。執(zhí)行arr［j］ = key，完成插入。外循環(huán)結(jié)束后，未排序區(qū)為空，排序成功。

算法總結(jié)： 雙重循環(huán)，背道而行，數(shù)據(jù)不斷右移為key騰挪位置，直到找到key應(yīng)該在的位置，最后插入。

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

空間復(fù)雜度： 雙重循環(huán)，定義了兩個(gè)簡(jiǎn)單變量，所以空間復(fù)雜度是O（1）。

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

遞歸性： 非遞歸。

原地性： 原地。

簡(jiǎn)單插入排序和簡(jiǎn)單選擇排序?qū)Ρ纫幌?，最好時(shí)間復(fù)雜度，前者是O（n），后者是O（n2），平均時(shí)間復(fù)雜度雖然都是O（n2），但是前者的系數(shù)是1/4，后者的系數(shù)是1/2，穩(wěn)定性，前者穩(wěn)定，后者不穩(wěn)定，所以簡(jiǎn)單插入排序完勝簡(jiǎn)單選擇排序。

2.5 希爾排序

希爾排序是對(duì)簡(jiǎn)單插入排序的一種改進(jìn)，又叫做縮小增量排序，也叫分組插入排序。它對(duì)插入排序的改進(jìn)是基于插入排序的兩個(gè)特點(diǎn)，1是插入排序?qū)τ谠浇咏藕眯虻臄?shù)列效率越高，2是插入排序一般情況下是低效的，因?yàn)閮?nèi)循環(huán)一次只能把數(shù)據(jù)移動(dòng)一位。針對(duì)插入排序的特點(diǎn)和缺點(diǎn)，我們可以這樣改進(jìn)它。對(duì)數(shù)列進(jìn)行分組插入排序，比如先分5組分別進(jìn)行插入排序，再分3組分別進(jìn)行插入排序，再分1組也就是不分組進(jìn)行插入排序。也就是說(shuō)希爾排序最后要進(jìn)行一次插入排序，你也許會(huì)覺(jué)得之前就進(jìn)行了很多次操作，最后還要進(jìn)行一次插入排序，效率肯定比插入排序差。但是這是不對(duì)的，因?yàn)椴迦肱判虻男适芩妮斎霐?shù)據(jù)的有序性影響很大，如果輸入數(shù)據(jù)是已經(jīng)排序的，那么插入排序的效率就是O（n），輸入數(shù)據(jù)越接近已排序，插入排序的效率就越接近O（n）。前面的分組插入排序就是為了使整個(gè)數(shù)組更接近排序狀態(tài)。它是第一個(gè)突破O（n2）的算法。

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

C語(yǔ)言實(shí)現(xiàn)：

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; } }}

代碼分析： 三重循環(huán)，最外層循環(huán)，是d增量循環(huán)，從nr/2開(kāi)始，每次減半，到1停止。內(nèi)層兩層for循環(huán)是標(biāo)準(zhǔn)的簡(jiǎn)單插入排序算法，加入了分組考慮。

算法總結(jié)： 三重循環(huán)，外層循環(huán)是d增量每次減半，內(nèi)兩層循環(huán)是簡(jiǎn)單插入排序。

時(shí)間復(fù)雜度： 希爾排序的時(shí)間復(fù)雜度是和增量序列有著密切的關(guān)系的，最好時(shí)間復(fù)雜度可以達(dá)到O（n），最壞時(shí)間復(fù)雜度可以到O（n2），如果按照Sedgewick提出的增量序列，最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度可以達(dá)到O（n1.3）。目前數(shù)學(xué)上還沒(méi)有證明希爾排序的最壞時(shí)間復(fù)雜度的下限是多少，因?yàn)椴惶米C明哪個(gè)增量序列是最優(yōu)的，不太好計(jì)算平均情況。

空間復(fù)雜度： 三重循環(huán)，只定義了兩個(gè)簡(jiǎn)單變量，顯然空間復(fù)雜度是O（1）。

穩(wěn)定性： d不為1的時(shí)候發(fā)生了不相鄰元素交換的情況，所以希爾排序是不穩(wěn)定的。

遞歸性： 非遞歸。

2.6 冒泡排序

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

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

C語(yǔ)言實(shí)現(xiàn)：

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; }}

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

算法總結(jié)： 雙重循環(huán)，相向而行，相鄰比較，順序不對(duì)就交換。可以簡(jiǎn)單總結(jié)為 鄰換對(duì)開(kāi) 四個(gè)字，鄰換，只有相鄰的元素才會(huì)進(jìn)行比較并有可能交換，對(duì)開(kāi)，內(nèi)外循環(huán)的index的增加方向是相反的。

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

空間復(fù)雜度： 雙重循環(huán)，只定義了一個(gè)簡(jiǎn)單變量，所以空間復(fù)雜度是O（1）。

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

遞歸性： 非遞歸。

2.7 快速排序

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

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

C語(yǔ)言實(shí)現(xiàn)：

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）;}

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

網(wǎng)上大部分的快排算法實(shí)現(xiàn)都是一個(gè)while循環(huán)內(nèi)嵌兩個(gè)并列的while循環(huán)，代碼比較冗長(zhǎng)。本文的快排實(shí)現(xiàn)是C語(yǔ)言之父Dennis Ritchie 在《The C Programming Language》書(shū)中所寫(xiě)的，代碼非常簡(jiǎn)潔精巧，但是理解起來(lái)非常費(fèi)勁。因此我們畫(huà)個(gè)圖來(lái)輔助理解：

算法總結(jié)： 遞歸算法都有分治合的特點(diǎn)，快排是先分后治沒(méi)有和。分是把整個(gè)區(qū)間分成兩個(gè)區(qū)間，一個(gè)區(qū)間都小于key，一個(gè)區(qū)間都大于等于key，這個(gè)是快排的重點(diǎn)和難點(diǎn)。治就是遞歸調(diào)用，遞歸調(diào)用在函數(shù)的尾部，所以是后遞歸算法。分的特點(diǎn)是先把key交換到最左邊，然后進(jìn)行分，最后再把key交換到臨界點(diǎn)。

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

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

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

遞歸性： 后遞歸，遞歸調(diào)用在函數(shù)的尾部叫后遞歸。

2.8 歸并排序

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

算法描述： 先取序列的中點(diǎn)把序列分成兩個(gè)區(qū)間，分別對(duì)左右兩個(gè)區(qū)間進(jìn)行遞歸調(diào)用，調(diào)用返回之后得到的是兩個(gè)已排序的序列，然后把這兩個(gè)序列合并成一個(gè)序列，合并采取的是非原地操作，把兩個(gè)區(qū)間復(fù)制到一個(gè)臨時(shí)數(shù)組中，然后左右兩個(gè)區(qū)間依次選擇最小的值復(fù)制回原區(qū)間中。由于是分成兩個(gè)區(qū)間進(jìn)行遞歸，所以這個(gè)算法實(shí)現(xiàn)是兩路遞歸排序。

C語(yǔ)言實(shí)現(xiàn)：

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）;}

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

算法總結(jié)： 先遞歸調(diào)用，再進(jìn)行整合。

時(shí)間復(fù)雜度： 和快速排序的原理是一樣的，時(shí)間復(fù)雜度的關(guān)鍵點(diǎn)在于遞歸樹(shù)的深度，由于我們是按index分區(qū)的，所以總是能平分一個(gè)區(qū)，不存在分配不均勻的情況，所以遞歸樹(shù)的深度總是O（logn），所以最好最壞平均時(shí)間復(fù)雜度都是O（nlogn）。

空間復(fù)雜度： 遞歸前定義了一個(gè)簡(jiǎn)單變量，其空間復(fù)雜度是O（logn），遞歸后定義了和n相關(guān)的數(shù)組變量，其空間復(fù)雜度是O（n），所以空間復(fù)雜度是O（n）。

穩(wěn)定性： 沒(méi)有交換操作，合并時(shí)并不會(huì)改變?cè)氐南鄬?duì)位置，所以歸并排序是穩(wěn)定的。

遞歸性： 前遞歸，先進(jìn)行遞歸，遞歸返回后再進(jìn)行合并操作。

原地性： 非原地，定義了臨時(shí)數(shù)組來(lái)存放被排序的值。

2.9 計(jì)數(shù)排序

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

算法描述： 先把原數(shù)組clone一份叫做arr2，再計(jì)算出數(shù)列中的最大值和最小值，創(chuàng)建一個(gè)長(zhǎng)度為max-min+1的counts數(shù)組，先統(tǒng)計(jì)數(shù)列中每個(gè)整數(shù)出現(xiàn)的次數(shù)，然后累加計(jì)數(shù)數(shù)組，此時(shí)counts［i］代表在原數(shù)組中小于等于i的元素的個(gè)數(shù)，然后逆序遍歷arr2，把a(bǔ)rr2按照正確的順序放到原數(shù)列中。

C語(yǔ)言實(shí)現(xiàn)：

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］;}

代碼分析： 先遍歷原數(shù)組，把原數(shù)組clone一份arr2，找到原數(shù)組的最大值和最小值，然后建立一個(gè)計(jì)數(shù)數(shù)組counts用來(lái)計(jì)數(shù)，長(zhǎng)度是max-min+1，再遍歷原數(shù)組，用元素的值減去min作為下標(biāo)在counts數(shù)組中尋址，對(duì)應(yīng)的counts元素++，代表這個(gè)數(shù)值的元素的個(gè)數(shù)又增加了一個(gè)，遍歷完成后，counts［i］代表在原數(shù)組中等于i的元素的個(gè)數(shù)。再累加counts，累加完成后，counts［i］代表在原數(shù)組中小于等于i的元素的個(gè)數(shù)。然后逆序遍歷arr2，把a(bǔ)rr2按照正確的順序放到原數(shù)列中。為什么要逆序呢，這是因?yàn)閏ounts［i］代表的是小于等于i的元素的個(gè)數(shù)，逆序的話能讓最后一個(gè)i值放到最后一個(gè)位置中去，這樣就不會(huì)顛倒值相等的元素的順序，能保存排序的穩(wěn)定性。

算法總結(jié)： 先遍歷原數(shù)組，找到最大值最小值，再遍歷原數(shù)組，統(tǒng)計(jì)各個(gè)數(shù)值出現(xiàn)的次數(shù)，再累加計(jì)數(shù)數(shù)組，再逆序遍歷arr2數(shù)組回寫(xiě)到原數(shù)組。

時(shí)間復(fù)雜度： 遍歷3次原數(shù)組，遍歷2次計(jì)數(shù)數(shù)組，原數(shù)組的長(zhǎng)度是n，計(jì)數(shù)數(shù)組的長(zhǎng)度是k，k = max-min+1，是一個(gè)與n無(wú)關(guān)的數(shù)，所以時(shí)間復(fù)雜度是O（n+k），不存在什么特殊情況，所以最好最壞平均時(shí)間復(fù)雜度都O（n+k）。

空間復(fù)雜度： 定義了一個(gè)計(jì)數(shù)數(shù)組，長(zhǎng)度是k，k = max-min+1，是一個(gè)與n無(wú)關(guān)的數(shù)，clone了原數(shù)組，長(zhǎng)度是n，所以空間復(fù)雜度是O（n+k）。

穩(wěn)定性： 計(jì)數(shù)排序是穩(wěn)定的，代碼分析中講了保持排序穩(wěn)定的原因。

遞歸性： 非遞歸。

2.10 桶排序

桶排序是也是一種非比較排序，它比較適合那些數(shù)據(jù)分布比較均勻的數(shù)據(jù)，其基本思想是根據(jù)數(shù)據(jù)的范圍，把其分為N個(gè)桶，然后把所有數(shù)據(jù)放入相應(yīng)的桶中，每個(gè)桶內(nèi)再進(jìn)行排序，然后把所有的桶按順序收回?cái)?shù)據(jù)，整個(gè)數(shù)據(jù)就排序好了。

算法描述： 把數(shù)據(jù)分到N個(gè)桶中，每個(gè)桶中再進(jìn)行排序。

C語(yǔ)言實(shí)現(xiàn)：

暫無(wú)

代碼分析： 暫無(wú)。

算法總結(jié)： 暫無(wú)

時(shí)間復(fù)雜度： 最好最壞平均時(shí)間復(fù)雜度都是O（n+k）。

空間復(fù)雜度： 空間復(fù)雜度是O（n+k）。

穩(wěn)定性： 桶排序是穩(wěn)定的。

遞歸性： 非遞歸。

2.11 基數(shù)排序

基數(shù)排序也是一種非比較排序，它只適用于對(duì)非負(fù)整數(shù)進(jìn)行排序，它的基本原理是先對(duì)個(gè)位進(jìn)行排序，再對(duì)十位進(jìn)行排序，再對(duì)百位進(jìn)行排序，……，直至最高位，對(duì)每位進(jìn)行排序的方法一定要選擇穩(wěn)定排序，比如計(jì)數(shù)排序?；鶖?shù)排序不一定要把整數(shù)看成是10進(jìn)制的，可以把它當(dāng)成任意進(jìn)制的數(shù)來(lái)處理都行。

算法描述： 從最低位開(kāi)始進(jìn)行穩(wěn)定排序，……，直至最高位。

C語(yǔ)言實(shí)現(xiàn)：

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］; }}

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

算法總結(jié)： 外層循環(huán)按照從低位到高位的順序進(jìn)行循環(huán)，內(nèi)層是計(jì)數(shù)排序。

時(shí)間復(fù)雜度： 外層循環(huán)的次數(shù)是位數(shù)k，內(nèi)層循環(huán)是計(jì)數(shù)排序，由于此時(shí)計(jì)數(shù)排序的k是常量，所以內(nèi)層循環(huán)的復(fù)雜度是O（n），由于不存在特殊情況，所以最好最壞平均時(shí)間復(fù)雜度都是O（nk）。

空間復(fù)雜度： 內(nèi)循環(huán)的空間復(fù)雜度是O（n），外循環(huán)不會(huì)累積內(nèi)循環(huán)的存儲(chǔ)空間，所以空間復(fù)雜度是O（n）。

穩(wěn)定性： 每輪排序都是用的穩(wěn)定排序，所以最終排序也是穩(wěn)定的，所以基數(shù)排序是穩(wěn)定的。

遞歸性： 非遞歸。

三、總結(jié)回顧

至此，我們已經(jīng)全面詳細(xì)講解了所有常見(jiàn)的排序算法，包括算法的原理、實(shí)現(xiàn)方法、以及各種性質(zhì)的分析（桶排序除外）。下面我們先畫(huà)個(gè)圖回顧一下。

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

圖中沒(méi)有寫(xiě)它們的適用性，我們?cè)谶@里說(shuō)一下。比較排序的適用性非常強(qiáng)，可適用于任何數(shù)據(jù)。非比較排序的適用性比較窄，計(jì)數(shù)排序適用于對(duì)范圍比較集中的整數(shù)進(jìn)行排序，桶排序適用于分布比較均勻的數(shù)據(jù)，基數(shù)排序適用于正整數(shù)。

我們?cè)賮?lái)看一看遞歸性、原地性與穩(wěn)定性和空間復(fù)雜度之間的關(guān)系?？梢钥闯龇窃嘏判蚨际欠€(wěn)定排序，原地排序由于需要交換，所以相鄰交換的都是穩(wěn)定排序，不相鄰交換的都是不穩(wěn)定排序。非遞歸原地排序的空間復(fù)雜度都是O（1），非遞歸非原地排序的空間復(fù)雜度都是線性的。遞歸排序的空間復(fù)雜度至少是O（logn），因?yàn)樵嘏判虿恍枰~外分配空間，所以遞歸原地排序的空間復(fù)雜度是O（logn），而非原地排序的空間復(fù)雜度是O（n），所以非遞歸非原地排序的空間復(fù)雜度是O（n）。

再來(lái)看時(shí)間復(fù)雜度，非比較排序中的計(jì)數(shù)排序和桶排序的平均時(shí)間復(fù)雜度都是O（n+k），是線性的，計(jì)數(shù)排序中，如果把位數(shù)k看成是不大于15的常量，計(jì)數(shù)排序的平均時(shí)間復(fù)雜度也可以看成是線性的。比較排序中，所有的簡(jiǎn)單排序的平均時(shí)間復(fù)雜度都是O（n2），而復(fù)雜排序基本都是O（nlogn），除了希爾是O（n1.3）。選擇排序和歸并的時(shí)間復(fù)雜度不存在優(yōu)化和惡化的情況。插入排序和冒泡排序存在優(yōu)化的情況，當(dāng)數(shù)列已經(jīng)排好序時(shí)，其時(shí)間復(fù)雜度優(yōu)化為O（n）?？炫诺臅r(shí)間復(fù)雜度存在惡化的情況，當(dāng)區(qū)間分割總是極度不均勻時(shí)，其時(shí)間復(fù)雜度惡化為O（n2）。

所有算法中，邏輯上最難理解的是堆排序和基數(shù)排序，代碼上最難理解的是快速排序。一般情況下運(yùn)行效率最高的是快排，所以快排才叫快排，很多庫(kù)的排序算法的默認(rèn)實(shí)現(xiàn)就是快排。