• 一. 復(fù)雜度
  • 時(shí)間復(fù)雜度
• 二. 數(shù)據(jù)結(jié)構(gòu)
  - 1. 數(shù)組
  - 數(shù)組為什么下標(biāo)從0開(kāi)始
  - 容器能否完全替代數(shù)組啦鸣？
  • 2. 鏈表 （Linked list）
  • 3. 棧
  • 4. 隊(duì)列
  • 5. 跳表
    • 時(shí)間復(fù)雜度：
    • 空間復(fù)雜度：
    • 跳表索引動(dòng)態(tài)更新
    • 跳表特點(diǎn)：
• 三. 算法
  • 1. 遞歸
  • 2. 排序
    • 2.1 冒泡排序
    • 2.2 插入排序
    • 2.3 選擇排序
    • 2.4 歸并排序
    • 2.5 快速排序
    • 2.6 桶排序
    • 2.7 計(jì)數(shù)排序
    • 2.8 基數(shù)排序
  • 3. 查找
    • 3.1 二分查找法

一. 復(fù)雜度

復(fù)雜度分析宿亡，是貫徹?cái)?shù)據(jù)結(jié)構(gòu)和算法中的一項(xiàng)基礎(chǔ)技能，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的目的太示，無(wú)非就是要寫(xiě)出占用空間更小、運(yùn)行時(shí)間更短的代碼拳话。

時(shí)間復(fù)雜度

1. 大O表示法：T(n) = O(f(n))

• 表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)（注意只是表示「變化趨勢(shì)」）
• 由于只是表示變化趨勢(shì)先匪，一般計(jì)算復(fù)雜度時(shí)，會(huì)忽略低階弃衍、常量呀非、系數(shù)

2. 幾種常見(jiàn)的時(shí)間復(fù)雜度量級(jí)：

   
   

多項(xiàng)式量級(jí)：

• 常數(shù)階 O(1)
• 對(duì)數(shù)階 O(logn)
• 線性階 O(n)
• 線性對(duì)數(shù)階 O(nlogn)
• 平方階 O(n2) O(n3) ... O(n^k)

非多項(xiàng)式量級(jí)：(n越多，執(zhí)行時(shí)間急劇上升，性能低)

• 指數(shù)階 O(2^n)
• 階乘階 O(n!)

3. 加法法則和乘法法則

• 加法法則：總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜度
• 乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積

4. 平均時(shí)間復(fù)雜度：

• 也叫加權(quán)平均時(shí)間復(fù)雜度或者期望時(shí)間復(fù)雜度岸裙。
• 要會(huì)計(jì)算：最好猖败、最壞、平均時(shí)間

5. 均攤時(shí)間復(fù)雜度

• 特殊的平均時(shí)間復(fù)雜度
• 相當(dāng)于算法有規(guī)律可循降允，計(jì)算時(shí)間時(shí)恩闻，可以把一次耗時(shí)多的操縱的時(shí)間，均攤給多次耗時(shí)少的操縱剧董。

二. 數(shù)據(jù)結(jié)構(gòu)

1. 數(shù)組

數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)幢尚。它用一組連續(xù)的內(nèi)存空間，來(lái)存儲(chǔ)一組具有相同類(lèi)型的數(shù)據(jù)翅楼。具有的特性：

1. 線性表
2. 連續(xù)的內(nèi)存空間
3. 相同類(lèi)型的數(shù)據(jù)
4. 可以隨機(jī)訪問(wèn)
5. 數(shù)據(jù)操作比較低效尉剩，平均情況時(shí)間復(fù)雜度為 O(n)

數(shù)組為什么下標(biāo)從0開(kāi)始

1. 由于數(shù)組是是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間毅臊，來(lái)存儲(chǔ)一組具有相同類(lèi)型的數(shù)據(jù)理茎。
   所以:

• 如果下標(biāo)從0開(kāi)始:
  • 計(jì)算下標(biāo)為k的對(duì)象的地址的公式為：a[k]_address = base_address + k * type_size
• 如果下標(biāo)從1開(kāi)始:
  • 計(jì)算下標(biāo)為k的對(duì)象的地址的公式為：a[k]_address = base_address + (k-1) * type_size
  • 對(duì)于 CPU 來(lái)說(shuō)，就是多了一次減法指令管嬉。

2. C 語(yǔ)言設(shè)計(jì)者用 0 開(kāi)始計(jì)數(shù)數(shù)組下標(biāo)皂林，之后的 Java、JavaScript 等高級(jí)語(yǔ)言都效仿了 C 語(yǔ)言蚯撩。

容器能否完全替代數(shù)組础倍？

例如Java的ArrayList，ArrayList 最大的優(yōu)勢(shì)就是可以將很多數(shù)組操作的細(xì)節(jié)封裝起來(lái)求厕。比如前面提到的數(shù)組插入著隆、刪除數(shù)據(jù)時(shí)需要搬移其他數(shù)據(jù)等。另外呀癣，它還有一個(gè)優(yōu)勢(shì)美浦，就是支持動(dòng)態(tài)擴(kuò)容。

那么项栏，作為高級(jí)語(yǔ)言編程者浦辨，是不是數(shù)組就無(wú)用武之地了呢？當(dāng)然不是沼沈，有些時(shí)候流酬，用數(shù)組會(huì)更合適些，總的來(lái)說(shuō)列另，對(duì)于業(yè)務(wù)開(kāi)發(fā)芽腾，直接使用容器就足夠了，省時(shí)省力页衙。畢竟損耗一丟丟性能摊滔，完全不會(huì)影響到系統(tǒng)整體的性能阴绢。但如果你是做一些非常底層的開(kāi)發(fā)，比如開(kāi)發(fā)網(wǎng)絡(luò)框架艰躺，性能的優(yōu)化需要做到極致呻袭，這個(gè)時(shí)候數(shù)組就會(huì)優(yōu)于容器，成為首選腺兴。

2. 鏈表 （Linked list）

不需要一塊連續(xù)的內(nèi)存空間厨诸，它通過(guò)“指針”將一組零散的內(nèi)存塊串聯(lián)起來(lái)使用蠢络。

幾種常見(jiàn)的鏈表形式：
1. 單鏈表
2. 循環(huán)鏈表
3. 雙向鏈表 （空間換時(shí)間思想）
4. 雙向循環(huán)列表

與數(shù)組的對(duì)比：

不過(guò)灵再，數(shù)組和鏈表的對(duì)比寺鸥，并不能局限于時(shí)間復(fù)雜度帽馋。而且耻卡，在實(shí)際的軟件開(kāi)發(fā)中舷胜，不能僅僅利用復(fù)雜度分析就決定使用哪個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)叁扫。

寫(xiě)鏈表代碼的幾個(gè)技巧：
1. 理解指針或引用的含義、警惕指針丟失和內(nèi)存泄漏
2. 利用哨兵簡(jiǎn)化實(shí)現(xiàn)難度
3. 重點(diǎn)留意邊界條件處理
4. 舉例畫(huà)圖陪腌、輔助思考

寫(xiě)鏈表代碼是最考驗(yàn)邏輯思維能力的。因?yàn)檠糖疲湵泶a到處都是指針的操作诗鸭、邊界條件的處理，稍有不慎就容易產(chǎn)生 Bug参滴。鏈表代碼寫(xiě)得好壞强岸，可以看出一個(gè)人寫(xiě)代碼是否夠細(xì)心，考慮問(wèn)題是否全面砾赔，思維是否縝密蝌箍。所以，這也是很多面試官喜歡讓人手寫(xiě)鏈表代碼的原因暴心。所以妓盲，這一節(jié)講到的東西，你一定要自己寫(xiě)代碼實(shí)現(xiàn)一下专普，才有效果悯衬。

1. 單鏈表反轉(zhuǎn)
2. 鏈表中環(huán)的檢測(cè)
3. 兩個(gè)有序的鏈表合并
4. 刪除鏈表倒數(shù)第 n 個(gè)結(jié)點(diǎn)
5. 求鏈表的中間結(jié)點(diǎn)

3. 棧

• 用數(shù)組實(shí)現(xiàn)的 順序棧
• 用鏈表實(shí)現(xiàn)的 鏈?zhǔn)綏?/li>
• 出棧入棧時(shí)間復(fù)雜度 空間復(fù)雜度都是O（1）
• 先進(jìn)后出

應(yīng)用：

• 1，函數(shù)的臨時(shí)變量的存儲(chǔ)銷(xiāo)毀
• 2檀夹，表達(dá)式求值
• 3筋粗，瀏覽器的前進(jìn)后退

4. 隊(duì)列

特點(diǎn)：先進(jìn)先出

• 用數(shù)組實(shí)現(xiàn) 順序隊(duì)列
• 用鏈表實(shí)現(xiàn) 鏈?zhǔn)疥?duì)列

隊(duì)列拓展：

• 循環(huán)隊(duì)列

  • 解決用數(shù)組實(shí)現(xiàn)的隊(duì)列需要數(shù)據(jù)遷移的問(wèn)題
  • 隊(duì)空：head == tail

  • 隊(duì)滿(mǎn)：(tail+1)%n=head。

    
    

• 阻塞隊(duì)列

  • 隊(duì)列滿(mǎn)了時(shí)炸渡，不給入隊(duì)娜亿。
  • 生產(chǎn)者 - 消費(fèi)者模型

• 并發(fā)隊(duì)列

  • 線程安全的隊(duì)列我們叫作并發(fā)隊(duì)列

5. 跳表

我們知道，數(shù)組支持快速的隨機(jī)訪問(wèn)蚌堵，而鏈表不支持买决，這樣的話，就不能用二分查找法來(lái)對(duì)鏈表進(jìn)行快速查找。實(shí)際上策州，我們只需要對(duì)鏈表稍加改造瘸味，就可以支持類(lèi)似“二分”的查找算法。我們把改造之后的數(shù)據(jù)結(jié)構(gòu)叫作跳表（Skip list）够挂。

跳表旁仿，其實(shí)就是對(duì)有序鏈表建立多級(jí)“索引”，每?jī)蓚€(gè)（也可以是其他數(shù)量）結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)到上一級(jí)孽糖，我們把抽出來(lái)的那一級(jí)叫作索引或索引層枯冈。你可以看我畫(huà)的圖。圖中的 down 表示 down 指針办悟，指向下一級(jí)結(jié)點(diǎn)尘奏。

如果我們現(xiàn)在要查找某個(gè)結(jié)點(diǎn)，比如 16病蛉。我們可以先在索引層遍歷炫加，當(dāng)遍歷到索引層中值為 13 的結(jié)點(diǎn)時(shí)，我們發(fā)現(xiàn)下一個(gè)結(jié)點(diǎn)是 17铺然，那要查找的結(jié)點(diǎn) 16 肯定就在這兩個(gè)結(jié)點(diǎn)之間俗孝。然后我們通過(guò)索引層結(jié)點(diǎn)的 down 指針，下降到原始鏈表這一層魄健，繼續(xù)遍歷赋铝。這個(gè)時(shí)候，我們只需要再遍歷 2 個(gè)結(jié)點(diǎn)沽瘦，就可以找到值等于 16 的這個(gè)結(jié)點(diǎn)了革骨。這樣，原來(lái)如果要查找 16析恋，需要遍歷 10 個(gè)結(jié)點(diǎn)良哲，現(xiàn)在只需要遍歷 7 個(gè)結(jié)點(diǎn)。

我舉的例子數(shù)據(jù)量不大绿满，查找效率的提升也并不明顯臂外。為了讓你能真切地感受索引提升查詢(xún)效率。我畫(huà)了一個(gè)包含 64 個(gè)結(jié)點(diǎn)的鏈表喇颁，按照前面講的這種思路漏健，建立了五級(jí)索引。

從圖中我們可以看出橘霎，原來(lái)沒(méi)有索引的時(shí)候蔫浆，查找 62 需要遍歷 62 個(gè)結(jié)點(diǎn)，現(xiàn)在只需要遍歷 11 個(gè)結(jié)點(diǎn)姐叁，速度是不是提高了很多瓦盛？所以洗显，當(dāng)鏈表的長(zhǎng)度 n 比較大時(shí)，比如 1000原环、10000 的時(shí)候挠唆，在構(gòu)建索引之后，查找效率的提升就會(huì)非常明顯嘱吗。

時(shí)間復(fù)雜度：

跳表查詢(xún)某個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度是多少呢玄组？

按照我們剛才講的，每?jī)蓚€(gè)結(jié)點(diǎn)會(huì)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)谒麦，那第一級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是 n/2俄讹，第二級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是 n/4，第三級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是 n/8绕德，依次類(lèi)推患膛，也就是說(shuō)，第 k 級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)是第 k-1 級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)的 1/2耻蛇，那第 k級(jí)索引結(jié)點(diǎn)的個(gè)數(shù)就是 n/(2k)踪蹬。

假設(shè)索引有 h 級(jí)，最高級(jí)的索引有 2 個(gè)結(jié)點(diǎn)城丧。通過(guò)上面的公式延曙，我們可以得到 n/(2h)=2，從而求得 h=log2n-1亡哄。如果包含原始鏈表這一層，整個(gè)跳表的高度就是 log2n布疙。我們?cè)谔碇胁樵?xún)某個(gè)數(shù)據(jù)的時(shí)候蚊惯，如果每一層都要遍歷 m 個(gè)結(jié)點(diǎn)，那在跳表中查詢(xún)一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度就是 O(m*logn)灵临。

那這個(gè) m 的值是多少呢截型？按照前面這種索引結(jié)構(gòu)，我們每一級(jí)索引都最多只需要遍歷 3 個(gè)結(jié)點(diǎn)儒溉，也就是說(shuō) m=3宦焦。

所以在跳表中查詢(xún)?nèi)我鈹?shù)據(jù)的時(shí)間復(fù)雜度就是 O(logn)。這個(gè)查找的時(shí)間復(fù)雜度跟二分查找是一樣的顿涣。換句話說(shuō)波闹，我們其實(shí)是基于單鏈表實(shí)現(xiàn)了二分查找，是不是很神奇涛碑？不過(guò)精堕，天下沒(méi)有免費(fèi)的午餐，這種查詢(xún)效率的提升蒲障，前提是建立了很多級(jí)索引歹篓，也就是我們?cè)诘?6 節(jié)講過(guò)的空間換時(shí)間的設(shè)計(jì)思路瘫证。

空間復(fù)雜度：

跳表是不是很浪費(fèi)內(nèi)存？比起單純的單鏈表庄撮，跳表需要存儲(chǔ)多級(jí)索引背捌，肯定要消耗更多的存儲(chǔ)空間。那到底需要消耗多少額外的存儲(chǔ)空間呢洞斯？我們來(lái)分析一下跳表的空間復(fù)雜度毡庆。

跳表的空間復(fù)雜度分析并不難，我在前面說(shuō)了巡扇，假設(shè)原始鏈表大小為 n扭仁，那第一級(jí)索引大約有 n/2 個(gè)結(jié)點(diǎn)，第二級(jí)索引大約有 n/4 個(gè)結(jié)點(diǎn)厅翔，以此類(lèi)推乖坠，每上升一級(jí)就減少一半，直到剩下 2 個(gè)結(jié)點(diǎn)刀闷。如果我們把每層索引的結(jié)點(diǎn)數(shù)寫(xiě)出來(lái)熊泵，就是一個(gè)等比數(shù)列。

這幾級(jí)索引的結(jié)點(diǎn)總和就是 n/2+n/4+n/8…+8+4+2=n-2甸昏。所以顽分，跳表的空間復(fù)雜度是 O(n)。也就是說(shuō)施蜜，如果將包含 n 個(gè)結(jié)點(diǎn)的單鏈表構(gòu)造成跳表卒蘸，我們需要額外再用接近 n 個(gè)結(jié)點(diǎn)的存儲(chǔ)空間。那我們有沒(méi)有辦法降低索引占用的內(nèi)存空間呢翻默？

我們前面都是每?jī)蓚€(gè)結(jié)點(diǎn)抽一個(gè)結(jié)點(diǎn)到上級(jí)索引缸沃，如果我們每三個(gè)結(jié)點(diǎn)或五個(gè)結(jié)點(diǎn)，抽一個(gè)結(jié)點(diǎn)到上級(jí)索引修械，是不是就不用那么多索引結(jié)點(diǎn)了呢趾牧？

第一級(jí)索引需要大約 n/3 個(gè)結(jié)點(diǎn)，第二級(jí)索引需要大約 n/9 個(gè)結(jié)點(diǎn)肯污。每往上一級(jí)翘单，索引結(jié)點(diǎn)個(gè)數(shù)都除以 3。為了方便計(jì)算蹦渣，我們假設(shè)最高一級(jí)的索引結(jié)點(diǎn)個(gè)數(shù)是 1哄芜。我們把每級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)都寫(xiě)下來(lái)，也是一個(gè)等比數(shù)列剂桥。

通過(guò)等比數(shù)列求和公式忠烛，總的索引結(jié)點(diǎn)大約就是 n/3+n/9+n/27+…+9+3+1=n/2。盡管空間復(fù)雜度還是 O(n)权逗，但比上面的每?jī)蓚€(gè)結(jié)點(diǎn)抽一個(gè)結(jié)點(diǎn)的索引構(gòu)建方法美尸，要減少了一半的索引結(jié)點(diǎn)存儲(chǔ)空間冤议。

實(shí)際上，在軟件開(kāi)發(fā)中师坎，我們不必太在意索引占用的額外空間恕酸。在講數(shù)據(jù)結(jié)構(gòu)和算法時(shí)，我們習(xí)慣性地把要處理的數(shù)據(jù)看成整數(shù)胯陋，但是在實(shí)際的軟件開(kāi)發(fā)中蕊温，原始鏈表中存儲(chǔ)的有可能是很大的對(duì)象，而索引結(jié)點(diǎn)只需要存儲(chǔ)關(guān)鍵值和幾個(gè)指針遏乔，并不需要存儲(chǔ)對(duì)象义矛，所以當(dāng)對(duì)象比索引結(jié)點(diǎn)大很多時(shí)，那索引占用的額外空間就可以忽略了盟萨。

跳表索引動(dòng)態(tài)更新

當(dāng)我們不停地往跳表中插入數(shù)據(jù)時(shí)凉翻，如果我們不更新索引，就有可能出現(xiàn)某 2 個(gè)索引結(jié)點(diǎn)之間數(shù)據(jù)非常多的情況捻激。極端情況下制轰，跳表還會(huì)退化成單鏈表。

作為一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)胞谭，我們需要某種手段來(lái)維護(hù)索引與原始鏈表大小之間的平衡垃杖，也就是說(shuō)，如果鏈表中結(jié)點(diǎn)多了丈屹，索引結(jié)點(diǎn)就相應(yīng)地增加一些调俘，避免復(fù)雜度退化，以及查找旺垒、插入脉漏、刪除操作性能下降。

當(dāng)我們往跳表中插入數(shù)據(jù)的時(shí)候袖牙，我們可以選擇同時(shí)將這個(gè)數(shù)據(jù)插入到部分索引層中。如何選擇加入哪些索引層呢舅锄？

我們通過(guò)一個(gè)隨機(jī)函數(shù)鞭达，來(lái)決定將這個(gè)結(jié)點(diǎn)插入到哪幾級(jí)索引中，比如隨機(jī)函數(shù)生成了值 K皇忿，那我們就將這個(gè)結(jié)點(diǎn)添加到第一級(jí)到第 K 級(jí)這 K 級(jí)索引中畴蹭。

隨機(jī)函數(shù)的選擇很有講究，從概率上來(lái)講鳍烁，能夠保證跳表的索引大小和數(shù)據(jù)大小平衡性叨襟，不至于性能過(guò)度退化。

跳表特點(diǎn)：

1. 前提是有序鏈表
2. 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)
3. 支持快速的查詢(xún)幔荒、插入糊闽、刪除操作梳玫，時(shí)間復(fù)雜度為O(logn)
4. 表面上空間復(fù)雜度是O(n)，但是因?yàn)樗饕恍枰鎯?chǔ)關(guān)鍵值和幾個(gè)指針右犹，并不需要存儲(chǔ)對(duì)象提澎，所以當(dāng)對(duì)象比索引結(jié)點(diǎn)大很多時(shí)，那索引占用的額外空間就可以忽略了念链。
5. 和紅黑樹(shù)相比的優(yōu)勢(shì)：當(dāng)需要按區(qū)間查找數(shù)據(jù)時(shí)盼忌，跳表可以做到 O(logn) 的時(shí)間復(fù)雜度定位區(qū)間的起點(diǎn)，然后在原始鏈表中順序往后遍歷就可以了掂墓。
6. 代碼實(shí)現(xiàn)比紅黑樹(shù)容易很多谦纱。

三. 算法

1. 遞歸

可以用遞歸的條件：

1. 一個(gè)問(wèn)題的解可以分解為幾個(gè)子問(wèn)題的解
2. 這個(gè)問(wèn)題與分解之后的子問(wèn)題，除了數(shù)據(jù)規(guī)模不同君编，求解思路完全一樣
3. 存在遞歸終止條件

寫(xiě)遞歸算法的思路：

1. 歸納出遞歸表達(dá)式
2. 尋找終止條件

遞歸代碼的弊端：

1. 堆棧溢出
2. 可能會(huì)重復(fù)計(jì)算
3. 函數(shù)調(diào)用耗時(shí)多
4. 空間復(fù)雜度高

2. 排序

衡量排序算法好壞的三要素：

1. 執(zhí)行效率

• 最好時(shí)間復(fù)雜度
• 最壞時(shí)間復(fù)雜度
• 平均時(shí)間復(fù)雜度
• 時(shí)間復(fù)雜度的系數(shù)跨嘉、常數(shù) 、低階（因?yàn)榕判虻臄?shù)據(jù)規(guī)模一般不會(huì)非常大）
• 比較啦粹、交換的次數(shù)

2. 額外內(nèi)存消耗（內(nèi)存消耗為O(1)的稱(chēng)為原地排序）
3. 穩(wěn)定性偿荷，是否是穩(wěn)定排序（即如果待排序的序列中存在值相等的元素，經(jīng)過(guò)排序之后唠椭，相等元素之間原有的先后順序不變）

按時(shí)間復(fù)雜度分類(lèi)：

1. O(n2)： 冒泡排序跳纳、插入排序、選擇排序
2. O(nlogn)：歸并排序贪嫂、快速排序
3. O(n) ：桶排序寺庄、計(jì)數(shù)排序、基數(shù)排序 （條件苛刻力崇，適用于部分場(chǎng)景）

2.1 冒泡排序

原理： 從下往上斗塘，逐次比較兩個(gè)相鄰的數(shù)據(jù)，如果下面的數(shù)據(jù)比上面的數(shù)據(jù)大亮靴，則把這兩個(gè)數(shù)據(jù)的位置互換馍盟。

• 最好時(shí)間復(fù)雜度 O(n)
• 最壞時(shí)間復(fù)雜度 O(n^2)
• 平均時(shí)間復(fù)雜度 O(n^2)
• 原地排序、穩(wěn)定排序

2.2 插入排序

原理： 分為已排區(qū)域和未排區(qū)域茧吊，每次拿未排區(qū)域中的第一個(gè)數(shù)贞岭，插入到已排區(qū)域中正確的位置。

• 最好時(shí)間復(fù)雜度 O(n)
• 最壞時(shí)間復(fù)雜度 O(n^2)
• 平均時(shí)間復(fù)雜度 O(n^2)
• 原地排序搓侄、穩(wěn)定排序

2.3 選擇排序

原理： 分為已排區(qū)域和未排區(qū)域瞄桨，每次從未排區(qū)域中選取最小的數(shù)，放到已排區(qū)域的最后面讶踪。

• 最好時(shí)間復(fù)雜度 O(n^2)
• 最壞時(shí)間復(fù)雜度 O(n^2)
• 平均時(shí)間復(fù)雜度 O(n^2)
• 原地排序芯侥、 非穩(wěn)定的排序算法
• 一般都不考慮用該算法。

2.4 歸并排序

原理： 歸并排序的核心思想還是蠻簡(jiǎn)單的乳讥。如果要排序一個(gè)數(shù)組柱查，我們先把數(shù)組從中間分成前后兩部分廓俭，然后對(duì)前后兩部分分別排序，再將排好序的兩部分合并在一起物赶，這樣整個(gè)數(shù)組就都有序了白指。

• 非原地排序，空間復(fù)雜度為O(n)
• 穩(wěn)定排序
• 利用分治遞歸思想
• 遞推公式： merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

• 最好酵紫、最壞告嘲、平均時(shí)間復(fù)雜度都是 O(nlogn)

  
  

2.5 快速排序

• 原地排序
• 非穩(wěn)定排序
• 遞推公式： quick_sort(p…r) = partition(p…r) + quick_sort(p…q-1) + quick_sort(q+1, r)
• 最好時(shí)間復(fù)雜度: O(nlogn)
• 最壞時(shí)間復(fù)雜度: O(n^2) （極小幾率出現(xiàn)）
• 平均時(shí)間復(fù)雜度: O(nlogn)

2.6 桶排序

桶排序，顧名思義奖地，會(huì)用到“桶”橄唬，核心思想是將要排序的數(shù)據(jù)分到幾個(gè)有序的桶里，每個(gè)桶里的數(shù)據(jù)再單獨(dú)進(jìn)行排序参歹。桶內(nèi)排完序之后仰楚，再把每個(gè)桶里的數(shù)據(jù)按照順序依次取出，組成的序列就是有序的了犬庇。

桶排序的時(shí)間復(fù)雜度為什么是 O(n) 呢僧界？我們一塊兒來(lái)分析一下。如果要排序的數(shù)據(jù)有 n 個(gè)臭挽，我們把它們均勻地劃分到 m 個(gè)桶內(nèi)捂襟，每個(gè)桶里就有 k=n/m 個(gè)元素。每個(gè)桶內(nèi)部使用快速排序欢峰，時(shí)間復(fù)雜度為 O(k * logk)葬荷。m 個(gè)桶排序的時(shí)間復(fù)雜度就是 O(m * k * logk)，因?yàn)?k=n/m纽帖，所以整個(gè)桶排序的時(shí)間復(fù)雜度就是 O(n*log(n/m))宠漩。當(dāng)桶的個(gè)數(shù) m 接近數(shù)據(jù)個(gè)數(shù) n 時(shí)，log(n/m) 就是一個(gè)非常小的常量懊直，這個(gè)時(shí)候桶排序的時(shí)間復(fù)雜度接近 O(n)扒吁。

苛刻的條件：

1. 要排序的數(shù)據(jù)需要很容易就能劃分成 m 個(gè)桶
2. 桶與桶之間有著天然的大小順序
3. 數(shù)據(jù)在各個(gè)桶之間的分布是比較均勻的

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

計(jì)數(shù)排序其實(shí)是桶排序的一種特殊情況： 數(shù)據(jù)的訪問(wèn)很小（例如年齡室囊、考生的成績(jī)）瘦陈，桶的數(shù)量是有限的。
以給高考考生成績(jī)進(jìn)行排名為例波俄，考生的滿(mǎn)分是 900 分，最小是 0 分蛾默，對(duì)應(yīng)901個(gè)桶懦铺，把全國(guó)的考生放入這901個(gè)桶，桶內(nèi)的數(shù)據(jù)都是分?jǐn)?shù)相同的考生支鸡，所以并不需要再進(jìn)行排序冬念。

特殊要求：

1. 只能用在數(shù)據(jù)范圍不大的場(chǎng)景中趁窃，如果數(shù)據(jù)范圍 k 比要排序的數(shù)據(jù) n 大很多，就不適合用計(jì)數(shù)排序了
2. 計(jì)數(shù)排序只能給非負(fù)整數(shù)排序急前，如果要排序的數(shù)據(jù)是其他類(lèi)型的醒陆，要將其在不改變相對(duì)大小的情況下，轉(zhuǎn)化為非負(fù)整數(shù)裆针。如果要排序的數(shù)據(jù)中有負(fù)數(shù)刨摩，數(shù)據(jù)的范圍是 [-1000, 1000]，那我們就需要先對(duì)每個(gè)數(shù)據(jù)都加 1000世吨，轉(zhuǎn)化成非負(fù)整數(shù)澡刹。如果考生成績(jī)精確到小數(shù)后一位，我們就需要將所有的分?jǐn)?shù)都先乘以 10耘婚，轉(zhuǎn)化成整數(shù)罢浇。

2.8 基數(shù)排序

我們?cè)賮?lái)看這樣一個(gè)排序問(wèn)題。假設(shè)我們有 10 萬(wàn)個(gè)手機(jī)號(hào)碼沐祷，希望將這 10 萬(wàn)個(gè)手機(jī)號(hào)碼從小到大排序嚷闭，你有什么比較快速的排序方法呢？

我們之前講的快排赖临，時(shí)間復(fù)雜度可以做到 O(nlogn)胞锰，還有更高效的排序算法嗎？桶排序思杯、計(jì)數(shù)排序能派上用場(chǎng)嗎胜蛉？手機(jī)號(hào)碼有 11 位，范圍太大色乾，顯然不適合用這兩種排序算法誊册。針對(duì)這個(gè)排序問(wèn)題，有沒(méi)有時(shí)間復(fù)雜度是 O(n) 的算法呢暖璧？現(xiàn)在我就來(lái)介紹一種新的排序算法案怯，基數(shù)排序。

剛剛這個(gè)問(wèn)題里有這樣的規(guī)律：假設(shè)要比較兩個(gè)手機(jī)號(hào)碼 a澎办，b 的大小嘲碱，如果在前面幾位中，a 手機(jī)號(hào)碼已經(jīng)比 b 手機(jī)號(hào)碼大了局蚀，那后面的幾位就不用看了麦锯。

借助穩(wěn)定排序算法，這里有一個(gè)巧妙的實(shí)現(xiàn)思路琅绅。還記得我們第 11 節(jié)中扶欣，在闡述排序算法的穩(wěn)定性的時(shí)候舉的訂單的例子嗎？我們這里也可以借助相同的處理思路，先按照最后一位來(lái)排序手機(jī)號(hào)碼料祠，然后骆捧，再按照倒數(shù)第二位重新排序，以此類(lèi)推髓绽，最后按照第一位重新排序敛苇。經(jīng)過(guò) 11 次排序之后，手機(jī)號(hào)碼就都有序了顺呕。

手機(jī)號(hào)碼稍微有點(diǎn)長(zhǎng)枫攀，畫(huà)圖比較不容易看清楚，我用字符串排序的例子塘匣，畫(huà)了一張基數(shù)排序的過(guò)程分解圖脓豪，你可以看下。

注意忌卤，這里按照每位來(lái)排序的排序算法要是穩(wěn)定的扫夜，否則這個(gè)實(shí)現(xiàn)思路就是不正確的。因?yàn)槿绻欠欠€(wěn)定排序算法驰徊，那最后一次排序只會(huì)考慮最高位的大小順序笤闯，完全不管其他位的大小關(guān)系，那么低位的排序就完全沒(méi)有意義了棍厂。

根據(jù)每一位來(lái)排序颗味，我們可以用剛講過(guò)的桶排序或者計(jì)數(shù)排序，它們的時(shí)間復(fù)雜度可以做到 O(n)牺弹。如果要排序的數(shù)據(jù)有 k 位浦马，那我們就需要 k 次桶排序或者計(jì)數(shù)排序，總的時(shí)間復(fù)雜度是 O(k*n)张漂。當(dāng) k 不大的時(shí)候晶默，比如手機(jī)號(hào)碼排序的例子，k 最大就是 11航攒，所以基數(shù)排序的時(shí)間復(fù)雜度就近似于 O(n)磺陡。

實(shí)際上，有時(shí)候要排序的數(shù)據(jù)并不都是等長(zhǎng)的漠畜，比如我們排序牛津字典中的 20 萬(wàn)個(gè)英文單詞币他，最短的只有 1 個(gè)字母，最長(zhǎng)的我特意去查了下憔狞，有 45 個(gè)字母蝴悉，中文翻譯是塵肺病。對(duì)于這種不等長(zhǎng)的數(shù)據(jù)瘾敢，基數(shù)排序還適用嗎辫封？

實(shí)際上硝枉，我們可以把所有的單詞補(bǔ)齊到相同長(zhǎng)度，位數(shù)不夠的可以在后面補(bǔ)“0”倦微，因?yàn)楦鶕?jù)ASCII 值，所有字母都大于“0”正压，所以補(bǔ)“0”不會(huì)影響到原有的大小順序欣福。這樣就可以繼續(xù)用基數(shù)排序了。

我來(lái)總結(jié)一下焦履，基數(shù)排序?qū)σ判虻臄?shù)據(jù)是有要求的：

1. 需要可以分割出獨(dú)立的“位”來(lái)比較拓劝，而且位之間有遞進(jìn)的關(guān)系，如果 a 數(shù)據(jù)的高位比 b 數(shù)據(jù)大嘉裤，那剩下的低位就不用比較了
2. 除此之外郑临，每一位的數(shù)據(jù)范圍不能太大，要可以用線性排序算法來(lái)排序屑宠，否則厢洞，基數(shù)排序的時(shí)間復(fù)雜度就無(wú)法做到 O(n) 了。

3. 查找

3.1 二分查找法

1. 依賴(lài)于數(shù)組結(jié)構(gòu)（數(shù)據(jù)量太大不適合用二分查找法典奉，數(shù)據(jù)需要連續(xù)的存儲(chǔ)空間）
2. 數(shù)據(jù)必須是排好序的
3. 時(shí)間復(fù)雜度：logn