@TOC

數(shù)據(jù)結(jié)構(gòu)算法學(xué)習(xí)（一）

簡(jiǎn)單地說，數(shù)據(jù)結(jié)構(gòu)是以某種特定的布局方式存儲(chǔ)數(shù)據(jù)的容器贮喧。這種“布局方式”決定了數(shù)據(jù)結(jié)構(gòu)對(duì)于某些操作是高效的馏臭，而對(duì)于其他操作則是低效的挺庞。首先我們需要理解各種數(shù)據(jù)結(jié)構(gòu)，才能在處理實(shí)際問題時(shí)選取最合適的數(shù)據(jù)結(jié)構(gòu)舅踪。

常用數(shù)據(jù)結(jié)構(gòu)

常用的數(shù)據(jù)結(jié)構(gòu)有：數(shù)組纽甘，棧，鏈表抽碌，隊(duì)列悍赢，樹，圖货徙，堆左权，散列表等

在這里插入圖片描述

1. 數(shù)組

1. 簡(jiǎn)介

數(shù)組是可以再內(nèi)存中連續(xù)存儲(chǔ)多個(gè)元素的結(jié)構(gòu)，在內(nèi)存中的分配也是連續(xù)的痴颊，數(shù)組中的元素通過數(shù)組下標(biāo)進(jìn)行訪問赏迟，數(shù)組下標(biāo)從0開始

2. 實(shí)例

NSArray *array = [NSArray arrayWithObjects:@"1",@"2",@"3",@"4", nil];
//    NSArray *array = @[@"1",@"2",@"3",@"4"];
NSLog(@"%@",array[0]);

3. 優(yōu)點(diǎn)
   1、按照索引查詢?cè)厮俣瓤?br> 2蠢棱、按照索引遍歷數(shù)組方便
4. 缺點(diǎn)
   1锌杀、數(shù)組的大小固定后就無法擴(kuò)容了
   2、數(shù)組只能存儲(chǔ)一種類型的數(shù)據(jù)
   3裳扯、添加抛丽，刪除的操作慢，因?yàn)橐苿?dòng)其他的元素饰豺。
5. 用法
6. 數(shù)組的基本操作
   Insert——在指定索引位置插入一個(gè)元素
   Get——返回指定索引位置的元素
   Delete——?jiǎng)h除指定索引位置的元素
   Size——得到數(shù)組所有元素的數(shù)量
7. 實(shí)用場(chǎng)景
   頻繁查詢亿鲜，對(duì)存儲(chǔ)空間要求不大，很少增加和刪除的情況冤吨。
8. 面試中關(guān)于數(shù)組的常見問題
   尋找數(shù)組中第二小的元素
   找到數(shù)組中第一個(gè)不重復(fù)出現(xiàn)的整數(shù)
   合并兩個(gè)有序數(shù)組
   重新排列數(shù)組中的正值和負(fù)值

2. 棧

1. 簡(jiǎn)介
   棧是一種特殊的線性表蒿柳，僅能在線性表的一端操作，棧頂允許操作漩蟆，棧底不允許操作垒探。棧的特點(diǎn)是：先進(jìn)后出，或者說是后進(jìn)先出怠李，從棧頂放入元素的操作叫入棧圾叼，取出元素叫出棧蛤克。

線性表是最基本、最簡(jiǎn)單夷蚊、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)构挤。線性表（linear list）是數(shù)據(jù)結(jié)構(gòu)的一種，一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列惕鼓。
線性表中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系筋现，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的（注意箱歧，這句話只適用大部分線性表矾飞，而不是全部。比如呀邢，循環(huán)鏈表邏輯層次上也是一種線性表（存儲(chǔ)層次上屬于鏈?zhǔn)酱鎯?chǔ)）洒沦，但是把最后一個(gè)數(shù)據(jù)元素的尾指針指向了首位結(jié)點(diǎn)）

在這里插入圖片描述

2. 實(shí)例

3. 優(yōu)點(diǎn)

4. 缺點(diǎn)

5. 用法

6. 棧的基本操作
   Push——在頂部插入一個(gè)元素
   Pop——返回并移除棧頂元素
   isEmpty——如果棧為空，則返回true
   Top——返回頂部元素价淌，但并不移除它

7. 面試中關(guān)于棧的常見問題
   使用棧計(jì)算后綴表達(dá)式
   對(duì)棧的元素進(jìn)行排序
   判斷表達(dá)式是否括號(hào)平衡

3. 鏈表

1. 簡(jiǎn)介

鏈表是一種物理存儲(chǔ)單元上非連續(xù)微谓、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的输钩。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成豺型，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。 相比于線性表順序結(jié)構(gòu)掸宛，操作復(fù)雜。由于不必須按順序存儲(chǔ)肴焊，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多功戚，但是查找一個(gè)節(jié)點(diǎn)或者訪問特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間娶眷，而線性表和順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。
根據(jù)指針的指向啸臀，鏈表能形成不同的結(jié)構(gòu)届宠，例如單鏈表，雙向鏈表乘粒，循環(huán)鏈表等豌注。

如圖所示：

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

• 雙向鏈表也叫雙鏈表，是鏈表的一種灯萍，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針轧铁，分別指向直接后繼和直接前驅(qū)。所以旦棉，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始齿风，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)药薯。一般我們都構(gòu)造雙向循環(huán)鏈表。

  
  
  在這里插入圖片描述

在這里插入圖片描述

2. 實(shí)例

3. 優(yōu)點(diǎn)
   鏈表是很常用的一種數(shù)據(jù)結(jié)構(gòu)救斑，不需要初始化容量果善，可以任意加減元素；
   添加或者刪除元素時(shí)只需要改變前后兩個(gè)元素結(jié)點(diǎn)的指針域指向地址即可系谐，所以添加，刪除很快讨跟；

4. 缺點(diǎn)
   因?yàn)楹写罅康闹羔樣蚣退加每臻g較大；
   查找元素需要遍歷鏈表來查找晾匠，非常耗時(shí)茶袒。

5. 用法
   鏈表是另一個(gè)重要的線性數(shù)據(jù)結(jié)構(gòu)，乍一看可能有點(diǎn)像數(shù)組凉馆，但在內(nèi)存分配薪寓、內(nèi)部結(jié)構(gòu)以及數(shù)據(jù)插入和刪除的基本操作方面均有所不同。
   鏈表就像一個(gè)節(jié)點(diǎn)鏈澜共，其中每個(gè)節(jié)點(diǎn)包含著數(shù)據(jù)和指向后續(xù)節(jié)點(diǎn)的指針向叉。 鏈表還包含一個(gè)頭指針，它指向鏈表的第一個(gè)元素嗦董，但當(dāng)列表為空時(shí)母谎，它指向null或無具體內(nèi)容。
   鏈表一般用于實(shí)現(xiàn)文件系統(tǒng)京革、哈希表和鄰接表奇唤。

6. 適用場(chǎng)景
   數(shù)據(jù)量較小，需要頻繁增加匹摇，刪除操作的場(chǎng)景

7. 鏈表的基本操作：
   InsertAtEnd - 在鏈表的末尾插入指定元素
   InsertAtHead - 在鏈接列表的開頭/頭部插入指定元素
   Delete - 從鏈接列表中刪除指定元素
   DeleteAtHead - 刪除鏈接列表的第一個(gè)元素
   Search - 從鏈表中返回指定元素
   isEmpty - 如果鏈表為空咬扇，則返回true

8. 面試中關(guān)于鏈表的常見問題
   反轉(zhuǎn)鏈表
   檢測(cè)鏈表中的循環(huán)
   返回鏈表倒數(shù)第N個(gè)節(jié)點(diǎn)
   刪除鏈表中的重復(fù)項(xiàng)

4. 隊(duì)列

1. 簡(jiǎn)介
   與棧相似，隊(duì)列是另一種順序存儲(chǔ)元素的線性數(shù)據(jù)結(jié)構(gòu)廊勃。棧與隊(duì)列的最大差別在于棧是LIFO（后進(jìn)先出）懈贺，而隊(duì)列是FIFO，即先進(jìn)先出坡垫。
   一個(gè)完美的隊(duì)列現(xiàn)實(shí)例子：售票亭排隊(duì)隊(duì)伍隅居。如果有新人加入，他需要到隊(duì)尾去排隊(duì)葛虐，而非隊(duì)首——排在前面的人會(huì)先拿到票胎源，然后離開隊(duì)伍。
   下圖是包含四個(gè)元素（1屿脐，2涕蚤，3和4）的隊(duì)列宪卿，其中在頂部的1將被最先移除：
   移除先入隊(duì)的元素、插入新元素

   
   
   在這里插入圖片描述

2. 實(shí)例

3. 優(yōu)點(diǎn)

4. 缺點(diǎn)

5. 用法

6. 隊(duì)列的基本操作
   Enqueue()——在隊(duì)列尾部插入元素
   Dequeue()——移除隊(duì)列頭部的元素
   isEmpty()——如果隊(duì)列為空万栅，則返回true
   Top()——返回隊(duì)列的第一個(gè)元素

7. 面試中關(guān)于隊(duì)列的常見問題
   使用隊(duì)列表示棧
   對(duì)隊(duì)列的前k個(gè)元素倒序
   使用隊(duì)列生成從1到n的二進(jìn)制數(shù)

5. 樹

1. 簡(jiǎn)介
   樹形結(jié)構(gòu)是一種層級(jí)式的數(shù)據(jù)結(jié)構(gòu)佑钾，由頂點(diǎn)（節(jié)點(diǎn)）和連接它們的邊組成。 樹類似于圖烦粒，但區(qū)分樹和圖的重要特征是樹中不存在環(huán)路休溶。
   樹形結(jié)構(gòu)被廣泛應(yīng)用于人工智能和復(fù)雜算法，它可以提供解決問題的有效存儲(chǔ)機(jī)制扰她。
   這是一個(gè)簡(jiǎn)單樹的示意圖兽掰，以及樹數(shù)據(jù)結(jié)構(gòu)中使用的基本術(shù)語：
   Root - 根節(jié)點(diǎn)
   Parent - 父節(jié)點(diǎn)
   Child - 子節(jié)點(diǎn)
   Leaf - 葉子節(jié)點(diǎn)
   Sibling - 兄弟節(jié)點(diǎn)

以下是樹形結(jié)構(gòu)的主要類型：

• N元樹
• 平衡樹
• 二叉樹
• 二叉搜索樹
• AVL樹
• 紅黑樹
• 2-3樹
  其中，二叉樹和二叉搜索樹是最常用的樹徒役。

樹是一種數(shù)據(jù)結(jié)構(gòu)孽尽，它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做 “樹” 是因?yàn)樗雌饋硐褚豢玫箳斓臉溆俏穑簿褪钦f它是根朝上杉女，而葉朝下的。它具有以下的特點(diǎn)：
每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)鸳吸；
沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)熏挎；

每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；
除了根節(jié)點(diǎn)外晌砾，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹婆瓜；

在日常的應(yīng)用中，我們討論和用的更多的是樹的其中一種結(jié)構(gòu)贡羔，就是二叉樹

在這里插入圖片描述

二叉樹是樹的特殊一種廉白，具有如下特點(diǎn)：
1、每個(gè)結(jié)點(diǎn)最多有兩顆子樹乖寒，結(jié)點(diǎn)的度最大為2猴蹂。
2、左子樹和右子樹是有順序的楣嘁，次序不能顛倒磅轻。
3、即使某結(jié)點(diǎn)只有一個(gè)子樹逐虚，也要區(qū)分左右子樹聋溜。

二叉樹是一種比較有用的折中方案，它添加叭爱，刪除元素都很快撮躁，并且在查找方面也有很多的算法優(yōu)化，所以买雾，二叉樹既有鏈表的好處把曼，也有數(shù)組的好處杨帽，是兩者的優(yōu)化方案，在處理大批量的動(dòng)態(tài)數(shù)據(jù)方面非常有用嗤军。

二叉樹有很多擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)注盈，包括平衡二叉樹、紅黑樹叙赚、B+樹等老客，這些數(shù)據(jù)結(jié)構(gòu)二叉樹的基礎(chǔ)上衍生了很多的功能，在實(shí)際應(yīng)用中廣泛用到震叮，例如mysql的數(shù)據(jù)庫索引結(jié)構(gòu)用的就是B+樹胧砰，還有HashMap的底層源碼中用到了紅黑樹。這些二叉樹的功能強(qiáng)大冤荆，但算法上比較復(fù)雜，想學(xué)習(xí)的話還是需要花時(shí)間去深入的权纤。

2. 實(shí)例

3. 優(yōu)點(diǎn)

4. 缺點(diǎn)

5. 用法

6. 面試中關(guān)于樹結(jié)構(gòu)的常見問題：
   求二叉樹的高度
   在二叉搜索樹中查找第k個(gè)最大值
   查找與根節(jié)點(diǎn)距離k的節(jié)點(diǎn)
   在二叉樹中查找給定節(jié)點(diǎn)的祖先節(jié)點(diǎn)

6. 圖

1. 簡(jiǎn)介
   圖是一組以網(wǎng)絡(luò)形式相互連接的節(jié)點(diǎn)钓简。節(jié)點(diǎn)也稱為頂點(diǎn)。 一對(duì)節(jié)點(diǎn)（x汹想，y）稱為邊（edge）外邓，表示頂點(diǎn)x連接到頂點(diǎn)y。邊可以包含權(quán)重/成本古掏，顯示從頂點(diǎn)x到y(tǒng)所需的成本损话。

   
   
   在這里插入圖片描述

圖的類型
無向圖
有向圖

常見圖遍歷算法
廣度優(yōu)先搜索
深度優(yōu)先搜索

2. 實(shí)例

3. 優(yōu)點(diǎn)

4. 缺點(diǎn)

5. 用法

6. 面試中關(guān)于圖的常見問題
   實(shí)現(xiàn)廣度和深度優(yōu)先搜索
   檢查圖是否為樹
   計(jì)算圖的邊數(shù)
   找到兩個(gè)頂點(diǎn)之間的最短路徑

7. 堆

1. 簡(jiǎn)介
   堆是一種比較特殊的數(shù)據(jù)結(jié)構(gòu)，可以被看做一棵樹的數(shù)組對(duì)象槽唾，具有以下的性質(zhì)：

堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值丧枪；
堆總是一棵完全二叉樹。
將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆庞萍，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆拧烦。常見的堆有二叉堆、斐波那契堆等钝计。

在這里插入圖片描述

在這里插入圖片描述

堆的定義如下：n個(gè)元素的序列{k1,k2,ki,…,kn}當(dāng)且僅當(dāng)滿足下關(guān)系時(shí)恋博，稱之為堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)私恬，
滿足前者的表達(dá)式的成為小頂堆债沮，滿足后者表達(dá)式的為大頂堆，這兩者的結(jié)構(gòu)圖可以用完全二叉樹排列出來

2. 實(shí)例

3. 優(yōu)點(diǎn)

4. 缺點(diǎn)

5. 用法

8. 散列

1. 簡(jiǎn)介
   散列表本鸣，也叫哈希表疫衩，是根據(jù)關(guān)鍵碼和值 (key和value) 直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)，通過key和value來映射到集合中的一個(gè)位置荣德，這樣就可以很快找到集合中的對(duì)應(yīng)元素隧土。

記錄的存儲(chǔ)位置=f(key)

這里的對(duì)應(yīng)關(guān)系f 成為散列函數(shù)提针，又稱為哈希 (hash函數(shù))，而散列表就是把Key通過一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字曹傀，
然后就將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余辐脖，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)

將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里

這種存儲(chǔ)空間可以充分利用數(shù)組的查找優(yōu)勢(shì)來查找元素，所以查找的速度很快皆愉。

哈希表在應(yīng)用中也是比較常見的嗜价，就如Java中有些集合類就是借鑒了哈希原理構(gòu)造的，例如HashMap幕庐，HashTable等久锥，利用hash表的優(yōu)勢(shì)，對(duì)于集合的查找元素時(shí)非常方便的异剥，然而瑟由，因?yàn)楣１硎腔跀?shù)組衍生的數(shù)據(jù)結(jié)構(gòu)，在添加刪除元素方面是比較慢的冤寿，所以很多時(shí)候需要用到一種數(shù)組鏈表來做歹苦，也就是拉鏈法。拉鏈法是數(shù)組結(jié)合鏈表的一種結(jié)構(gòu)督怜，較早前的hashMap底層的存儲(chǔ)就是采用這種結(jié)構(gòu)殴瘦，直到j(luò)dk1.8之后才換成了數(shù)組加紅黑樹的結(jié)構(gòu).iOS中weak表（弱引用表）就是典型的哈希表

在這里插入圖片描述

左邊很明顯是個(gè)數(shù)組，數(shù)組的每個(gè)成員包括一個(gè)指針号杠，指向一個(gè)鏈表的頭蚪腋，
當(dāng)然這個(gè)鏈表可能為空，也可能元素很多姨蟋。
我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去屉凯，
也是根據(jù)這些特征，找到正確的鏈表眼溶，再從鏈表中找出這個(gè)元素神得。

哈希表的應(yīng)用場(chǎng)景很多，當(dāng)然也有很多問題要考慮偷仿，比如哈希沖突的問題哩簿，如果處理的不好會(huì)浪費(fèi)大量的時(shí)間，導(dǎo)致應(yīng)用崩潰酝静。

2. 實(shí)例

3. 優(yōu)點(diǎn)

4. 缺點(diǎn)

5. 用法
   哈希法（Hashing）是一個(gè)用于唯一標(biāo)識(shí)對(duì)象并將每個(gè)對(duì)象存儲(chǔ)在一些預(yù)先計(jì)算的唯一索引（稱為“鍵（key）”）中的過程节榜。因此，對(duì)象以鍵值對(duì)的形式存儲(chǔ)别智，這些鍵值對(duì)的集合被稱為“字典”宗苍。可以使用鍵搜索每個(gè)對(duì)象』淇撸基于哈希法有很多不同的數(shù)據(jù)結(jié)構(gòu)让歼，但最常用的數(shù)據(jù)結(jié)構(gòu)是哈希表。
   哈希表通常使用數(shù)組實(shí)現(xiàn)丽啡。

散列數(shù)據(jù)結(jié)構(gòu)的性能取決于以下三個(gè)因素：
哈希函數(shù)
哈希表的大小
碰撞處理方法

6. 面試中關(guān)于哈希結(jié)構(gòu)的常見問題：
   在數(shù)組中查找對(duì)稱鍵值對(duì)
   追蹤遍歷的完整路徑
   查找數(shù)組是否是另一個(gè)數(shù)組的子集
   檢查給定的數(shù)組是否不相交

9. 字典樹（Trie）

1. 簡(jiǎn)介
   字典樹谋右，也稱為“前綴樹”，是一種特殊的樹狀數(shù)據(jù)結(jié)構(gòu)补箍，對(duì)于解決字符串相關(guān)問題非常有效改执。它能夠提供快速檢索，主要用于搜索字典中的單詞坑雅，在搜索引擎中自動(dòng)提供建議辈挂，甚至被用于IP的路由。
   以下是在字典樹中存儲(chǔ)三個(gè)單詞“top”裹粤，“so”和“their”的例子：

在這里插入圖片描述

這些單詞以頂部到底部的方式存儲(chǔ)终蒂，其中綠色節(jié)點(diǎn)“p”，“s”和“r”分別表示“top”遥诉，“thus”和“theirs”的底部拇泣。

2. 面試中關(guān)于字典樹的常見問題
   計(jì)算字典樹中的總單詞數(shù)
   打印存儲(chǔ)在字典樹中的所有單詞
   使用字典樹對(duì)數(shù)組的元素進(jìn)行排序
   使用字典樹從字典中形成單詞
   構(gòu)建T9字典（字典樹+ DFS ）

常用算法

算法是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令突那，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制挫酿。對(duì)于同一個(gè)問題的解決构眯，可能會(huì)存在著不同的算法愕难，為了衡量一個(gè)算法的優(yōu)劣，提出了空間復(fù)雜度與時(shí)間復(fù)雜度這兩個(gè)概念惫霸。

• 時(shí)間復(fù)雜度
  一般情況下猫缭，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間度量記為 ** T(n) = O(f(n)) **壹店，它表示隨問題規(guī)模n的增大猜丹，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度硅卢，簡(jiǎn)稱時(shí)間復(fù)雜度射窒。這里需要重點(diǎn)理解這個(gè)增長(zhǎng)率。

//舉個(gè)例子将塑，看下面3個(gè)代碼：

1脉顿、{++x;}

2、for(i = 1; i <= n; i++) { ++x; }

3点寥、for(j = 1; j <= n; j++) 
        for(j = 1; j <= n; j++) 
             { ++x; }

//上述含有 ++x 操作的語句的頻度分別為1 艾疟、n 、n^2，

//假設(shè)問題的規(guī)模擴(kuò)大了n倍蔽莱，3個(gè)代碼的增長(zhǎng)率分別是1 弟疆、n 、n^2

//它們的時(shí)間復(fù)雜度分別為O(1)盗冷、O(n )怠苔、O(n^2)

• 空間復(fù)雜度
  空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度，記做S(n)=O(f(n))正塌。一個(gè)算法的優(yōu)劣主要從算法的執(zhí)行時(shí)間和所需要占用的存儲(chǔ)空間兩個(gè)方面衡量嘀略。

1. 排序相關(guān)算法

常用的算法一般為快速排序、歸并排序乓诽、希爾排序等帜羊。特別的，如果一個(gè)序列基本成有序鸠天，插入排序是最快的讼育。

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

1. 插入排序

• 時(shí)間復(fù)查度：O(n^2)

最好情況下，當(dāng)待排序序列中記錄已經(jīng)有序時(shí)稠集，則需要n-1次比較奶段，不需要移動(dòng)，時(shí)間復(fù)雜度為** O(n) 剥纷。最差情況下痹籍，當(dāng)待排序序列中所有記錄正好逆序時(shí)，則比較次數(shù)和移動(dòng)次數(shù)都達(dá)到最大值晦鞋，時(shí)間復(fù)雜度為 O(n^2) 蹲缠。平均情況下，時(shí)間復(fù)雜度為 O(n^2) **悠垛。

• 簡(jiǎn)介

直接插入的思想是：是將一個(gè)記錄插入到已排好序的有序表中线定，從而得到一個(gè)新的、記錄數(shù)增1的有序表确买。
例如斤讥，排序序列(3,2,1,5)的過程是，初始時(shí)有序序列為(3)湾趾，然后從位置1開始芭商，先訪問到2，將2插入到3前面搀缠，得到有序序列(2,3)铛楣，之后訪問1,找到合適的插入位置后得到有序序列(1,2,3)，最后訪問5胡嘿，得到最終有序序列(1,2,3,5).

• 算法

插入排序是一種最簡(jiǎn)單直觀的排序算法蛉艾，它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描勿侯，找到相應(yīng)位置并插入拓瞪。
算法步驟：
將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列助琐。從頭到尾依次掃描未排序序列祭埂，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等兵钮，則將待插入元素插入到相等元素的后面蛆橡。）
原始：5 4 1 3 6 7 8 2
第一趟：4 5 1 3 6 7 8 2
第二趟：1 4 5 3 6 7 8 2

• 代碼實(shí)現(xiàn)

static void funDInsertSort(int[] array) {

    int j;

    for (int i = 1; i < array.length; i++) {

        int temp = array[I];

        j = i - 1;

        while (j > -1 && temp < array[j]) {

            array[j + 1] = array[j];

            j--;
        }

        array[j + 1] = temp;

    }

    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
}

2. 希爾排序

• 時(shí)間復(fù)查度：O(nlog(n))

• 簡(jiǎn)介

希爾排序又稱“縮小增量排序”，它是基于直接插入排序的以下兩點(diǎn)性質(zhì)而提出的一種改進(jìn)：(1) 直接插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)掘譬，效率高泰演，即可以達(dá)到線性排序的效率。(2) 直接插入排序一般來說是低效的葱轩，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位
由于多次插入排序睦焕，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序靴拱，但在不同的插入排序過程中垃喊，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂袜炕，所以shell排序是不穩(wěn)定的本谜。

• 算法

算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序偎窘，然后再用一個(gè)較小的增量對(duì)它進(jìn)行乌助，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)评架，整個(gè)要排序的數(shù)被分成一組眷茁，排序完成炕泳。
注意：增量的選擇尤為重要纵诞，一種參考h=3*d+1進(jìn)行迭代。

在這里插入圖片描述

說明一下：每一趟分組后進(jìn)行排序培遵，按照小到大順序浙芙，交換位置
第一趟中： 592 72交換位置，但是該數(shù)據(jù)在原始數(shù)據(jù)的位置仍然不變籽腕。
（1嗡呼，592）----（6，72）交換后（1皇耗，72）—（6南窗，592）
第二趟中：（1，72）–（3，874）–（5万伤，283）–（7窒悔，911）–（9，820）
交換排序后（1敌买，72）–（3简珠，283）–（5，820）–（7虹钮，874）–（9聋庵，911）

• 代碼實(shí)現(xiàn)

//Shell排序的算法實(shí)現(xiàn):
//1． 不設(shè)監(jiān)視哨的算法描述
void ShellPass(SeqList R，int d)
{//希爾排序中的一趟排序芙粱，d為當(dāng)前增量
for(i=d+1;i<=n祭玉；i++) //將R[d+1．．n]分別插入各組當(dāng)前的有序區(qū)
if(R[ i ].key<R[i-d].key){
R[0]=R[i];j=i-d； //R[0]只是暫存單元春畔，不是哨兵
do {//查找R的插入位置
R[j+d]=R[j]攘宙； //后移記錄
j=j-d； //查找前一記錄
}while(j>0&&R[0].key<R[j].key)拐迁；
R[j+d]=R[0]蹭劈； //插入R到正確的位置上
} //endif

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

#include<stdio.h>
#include<math.h>
 
#define MAXNUM 10
 
void main()
{
    void shellSort(int array[],int n,int t);//t為排序趟數(shù)
    int array[MAXNUM],I;
    for(i=0;i<MAXNUM;i++)
        scanf("%d",&array[I]);
    shellSort(array,MAXNUM,(int)(log(MAXNUM+1)/log(2)));//排序趟數(shù)應(yīng)為log2(n+1)的整數(shù)部分
    for(i=0;i<MAXNUM;i++)
        printf("%d ",array[I]);
    printf("\n");
}
 
//根據(jù)當(dāng)前增量進(jìn)行插入排序
void shellInsert(int array[],int n,int dk)
{
    int i,j,temp;
    for(i=dk;i<n;i++)//分別向每組的有序區(qū)域插入
    {
        temp=array[I];
        for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比較與記錄后移同時(shí)進(jìn)行
            array[j+dk]=array[j];
        if(j!=i-dk)
            array[j+dk]=temp;//插入
    }
}
 
//計(jì)算Hibbard增量
int dkHibbard(int t,int k)
{
    return (int)(pow(2,t-k+1)-1);
}
 
//希爾排序
void shellSort(int array[],int n,int t)
{
    void shellInsert(int array[],int n,int dk);
    int I;
    for(i=1;i<=t;i++)
        shellInsert(array,n,dkHibbard(t,i));
}
 
//此寫法便于理解，實(shí)際應(yīng)用時(shí)應(yīng)將上述三個(gè)函數(shù)寫成一個(gè)函數(shù)线召。

3. 選擇排序

• 時(shí)間復(fù)查度：O(n^2)

• 算法

算法步驟：
1）首先在未排序序列中找到最衅倘汀（大）元素，存放到排序序列的起始位置
2）再從剩余未排序元素中繼續(xù)尋找最谢貉汀（大）元素哈打，然后放到已排序序列的末尾。
3）重復(fù)第二步讯壶，直到所有元素均排序完畢料仗。
例子：5 8 3 6 4
第一趟：用除去第一個(gè)元素5以外的其余元素的最小值（為3）來與5比較，最小的交換（5>3）
3 8 5 6 4
第二趟：同理伏蚊，用除去第二個(gè)元素8以外的其余元素的最小值（為4）來與8比較
3 4 5 6 8

• 代碼實(shí)現(xiàn)

static void funSelectionSort(int[] array) {

    for (int i = 0; i < array.length - 1; i++) {

        int mink = I;

            // 每次從未排序數(shù)組中找到最小值的坐標(biāo)
        for (int j = i + 1; j < array.length; j++) {

            if (array[j] < array[mink]) {
                mink = j;
            }
        }

        // 將最小值放在最前面
        if (mink != i) {
            int temp = array[mink];
            array[mink] = array[I];
            array[i] = temp;
        }
    }

    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
}

• 分析

簡(jiǎn)單選擇排序過程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況** 無關(guān)立轧。當(dāng)i=1時(shí)，需進(jìn)行n-1次比較躏吊；當(dāng)i=2時(shí)氛改，需進(jìn)行n-2次比較；依次類推比伏，共需要進(jìn)行的比較次數(shù)是(n-1)+(n-2)+…+2+1=n(n-1)/2胜卤，即進(jìn)行比較操作的時(shí)間復(fù)雜度為 O(n^2) ，進(jìn)行移動(dòng)操作的時(shí)間復(fù)雜度為 O(n) 赁项「瘐铮總的時(shí)間復(fù)雜度為 O(n^2) **澈段。
最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了舰攒，則不需要移動(dòng)記錄均蜜。最壞情況下，即待排序記錄初始狀態(tài)是按第一條記錄最大芒率，之后的記錄從小到大順序排列囤耳，則需要移動(dòng)記錄的次數(shù)最多為3（n-1）。
簡(jiǎn)單選擇排序是不穩(wěn)定排序偶芍。

4. 冒泡排序

• 時(shí)間復(fù)查度：O(n^2)

最佳情況下冒泡排序只需一次遍歷就能確定數(shù)組已經(jīng)排好序充择，不需要進(jìn)行下一次遍歷，所以最佳情況下匪蟀，時(shí)間復(fù)雜度為** O(n) 椎麦。
最壞情況下冒泡排序需要n-1次遍歷，第一次遍歷需要比較n-1次材彪，第二次遍歷需要n-2次观挎，...，最后一次需要比較1次段化，最差情況下時(shí)間復(fù)雜度為 O(n^2) **嘁捷。

• 簡(jiǎn)介
  冒泡排序的基本思想是：設(shè)排序序列的記錄個(gè)數(shù)為n，進(jìn)行n-1次遍歷显熏，每次遍歷從開始位置依次往后比較前后相鄰元素雄嚣，這樣較大的元素往后移，n-1次遍歷結(jié)束后喘蟆，序列有序缓升。

• 算法

算法步驟：
1）比較相鄰的元素。如果第一個(gè)比第二個(gè)大蕴轨，就交換他們兩個(gè)港谊。
2）對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)橙弱。這步做完后歧寺，最后的元素會(huì)是最大的數(shù)。
3）針對(duì)所有的元素重復(fù)以上的步驟膘螟，除了最后一個(gè)成福。
4）持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟碾局，直到?jīng)]有任何一對(duì)數(shù)字需要比較荆残。
5 3 8 4 7 假設(shè)從小到大，從后面第一個(gè)開始：
5 3 4 8 7
3 5 4 8 7 ----第一次排序結(jié)束净当，最小的在前面
3 5 4 7 8
3 4 5 7 8 ----第二次排序結(jié)束内斯，第二最小排好
結(jié)束

• 代碼實(shí)現(xiàn)

// 冒泡排序 注意 flag 的作用
static void funBubbleSort(int[] array) {

    boolean flag = true;

    for (int i = 0; i < array.length - 1 && flag; i++) {

        flag = false;

        for (int j = 0; j < array.length - 1 - i; j++) {

            if (array[j] > array[j + 1]) {

                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;

                flag = true;
            }
        }
    }

    for (int i = 0; i < array.length; i++) {
        System.out.println(array[I]);
    }
}

5. 快速排序

• 時(shí)間復(fù)查度：O(nlogn)
• 簡(jiǎn)介

快速排序的主要思想是：在待排序的序列中選擇一個(gè)稱為主元的元素蕴潦，將數(shù)組分為兩部分，使得第一部分中的所有元素都小于或等于主元俘闯，而第二部分中的所有元素都大于主元潭苞，然后對(duì)兩部分遞歸地應(yīng)用快速排序算法。其實(shí)其思想是來自冒泡排序真朗，冒泡排序是通過相鄰元素的比較和交換把最小的冒泡到最頂端此疹，而快速排序是比較和交換小數(shù)和大數(shù)，這樣一來不僅把小數(shù)冒泡到上面同時(shí)也把大數(shù)沉到下面遮婶。

• 算法

在這里插入圖片描述

• 代碼實(shí)現(xiàn)

// 快速排序
static void funQuickSort(int[] mdata, int start, int end) {
    if (end > start) {
        int pivotIndex = quickSortPartition(mdata, start, end);
        funQuickSort(mdata, start, pivotIndex - 1);
        funQuickSort(mdata, pivotIndex + 1, end);
    }
}

// 快速排序前的劃分
static int quickSortPartition(int[] list, int first, int last) {

    int pivot = list[first];
    int low = first + 1;
    int high = last;

    while (high > low) {

        while (low <= high && list[low] <= pivot) {
            low++;
        }

        while (low <= high && list[high] > pivot) {
            high--;
        }

        if (high > low) {
            int temp = list[high];
            list[high] = list[low];
            list[low] = temp;
        }
    }

    while (high > first && list[high] >= pivot) {
        high--;
    }

    if (pivot > list[high]) {
        list[first] = list[high];
        list[high] = pivot;
        return high;
    } else {
        return first;
    }
}

• 分析

在快速排序算法中蝗碎，比較關(guān)鍵的一個(gè)部分是主元的選擇。在最差情況下旗扑，劃分由n個(gè)元素構(gòu)成的數(shù)組需要進(jìn)行n次比較和n次移動(dòng)蹦骑，因此劃分需要的時(shí)間是O(n)。在最差情況下臀防，每次主元會(huì)將數(shù)組劃分為一個(gè)大的子數(shù)組和一個(gè)空數(shù)組雄坪，這個(gè)大的子數(shù)組的規(guī)模是在上次劃分的子數(shù)組的規(guī)模上減1匆光，這樣在最差情況下算法需要(n-1)+(n-2)+...+1= ** O(n^2) 時(shí)間。
最佳情況下，每次主元將數(shù)組劃分為規(guī)模大致相等的兩部分跪削，時(shí)間復(fù)雜度為 O(nlogn) **。

6. 歸并排序

• 時(shí)間復(fù)查度：O(nlogn）
  歸并排序的時(shí)間復(fù)雜度為O(nlogn)咧栗，它是一種穩(wěn)定的排序蒂誉。
• 簡(jiǎn)介

歸并排序是另一種不同的排序方法，因?yàn)闅w并排序使用了遞歸分治的思想篡悟，所以理解起來比較容易谜叹。其基本思想是，先遞歸劃分子問題搬葬，然后合并結(jié)果荷腊。把待排序列看成由兩個(gè)有序的子序列，然后合并兩個(gè)子序列急凰，然后把子序列看成由兩個(gè)有序序列女仰。倒著來看，其實(shí)就是先兩兩合并抡锈，然后四四合并疾忍。。床三。最終形成有序序列一罩。空間復(fù)雜度為O(n)撇簿，時(shí)間復(fù)雜度為O(nlogn)聂渊。

• 算法

例如差购，排序序列(3,2,8,6,7,9,1,5)的過程是，先將序列分為兩部分汉嗽，(3,2,8,6)和(7,9,1,5)欲逃，然后對(duì)兩部分分別應(yīng)用歸并排序，第1部分(3,2,8,6)饼暑，第2部分(7,9,1,5)稳析，對(duì)兩個(gè)部分分別進(jìn)行歸并排序，第1部分繼續(xù)分為(3,2)和(8,6)弓叛，(3,2)繼續(xù)分為(3)和(2)迈着，(8,6)繼續(xù)分為(8)和(6)，之后進(jìn)行合并得到(2,3)邪码，(6,8)裕菠，再合并得到(2,3,6,8)，第2部分進(jìn)行歸并排序得到(1,5,7,9)闭专，最后合并兩部分得到(1,2,3,5,6,7,8,9)奴潘。

• 代碼實(shí)現(xiàn)

//歸并排序
    static void funMergeSort(int[] array) {

        if (array.length > 1) {

            int length1 = array.length / 2;
            int[] array1 = new int[length1];
            System.arraycopy(array, 0, array1, 0, length1);
            funMergeSort(array1);

            int length2 = array.length - length1;
            int[] array2 = new int[length2];
            System.arraycopy(array, length1, array2, 0, length2);
            funMergeSort(array2);

            int[] datas = merge(array1, array2);
            System.arraycopy(datas, 0, array, 0, array.length);
        }

    }

    //合并兩個(gè)數(shù)組
    static int[] merge(int[] list1, int[] list2) {

        int[] list3 = new int[list1.length + list2.length];

        int count1 = 0;
        int count2 = 0;
        int count3 = 0;

        while (count1 < list1.length && count2 < list2.length) {

            if (list1[count1] < list2[count2]) {
                list3[count3++] = list1[count1++];
            } else {
                list3[count3++] = list2[count2++];
            }
        }

        while (count1 < list1.length) {
            list3[count3++] = list1[count1++];
        }

        while (count2 < list2.length) {
            list3[count3++] = list2[count2++];
        }

        return list3;
    }

7. 堆排序

• 時(shí)間復(fù)查度：

• 簡(jiǎn)介

在介紹堆排序之前首先需要了解堆的定義，n個(gè)關(guān)鍵字序列K1影钉，K2画髓，…，Kn稱為堆平委，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)（簡(jiǎn)稱為堆性質(zhì)）：(1) ki <= k(2i）且 ki <= k(2i+1) (1 ≤ i≤ n/2）奈虾，當(dāng)然，這是小根堆廉赔，大根堆則換成>=號(hào)肉微。
如果將上面滿足堆性質(zhì)的序列看成是一個(gè)完全二叉樹，則堆的含義表明蜡塌，完全二叉樹中所有的非終端節(jié)點(diǎn)的值均不大于（或不小于）其左右孩子節(jié)點(diǎn)的值碉纳。
堆排序的主要思想是：給定一個(gè)待排序序列，首先經(jīng)過一次調(diào)整馏艾，將序列構(gòu)建成一個(gè)大頂堆劳曹，此時(shí)第一個(gè)元素是最大的元素，將其和序列的最后一個(gè)元素交換琅摩，然后對(duì)前n-1個(gè)元素調(diào)整為大頂堆铁孵，再將其第一個(gè)元素和末尾元素交換，這樣最后即可得到有序序列房资。

• 算法

基本過程：
a.將無需序列構(gòu)建成一個(gè)堆蜕劝，根據(jù)升序降序需求選擇大頂堆或小頂堆;
b.將堆頂元素與末尾元素交換，將最大元素"沉"到數(shù)組末端;
c.重新調(diào)整結(jié)構(gòu)志膀，使其滿足堆定義熙宇，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素鳖擒，反復(fù)執(zhí)行調(diào)整+交換步驟溉浙，直到整個(gè)序列有序烫止。

• 代碼實(shí)現(xiàn)

//堆排序
public class TestHeapSort {

    public static void main(String[] args) {
        int arr[] = { 5, 6, 1, 0, 2, 9 };
        heapsort(arr, 6);
        System.out.println(Arrays.toString(arr));
    }

    static void heapsort(int arr[], int n) {

        // 先建大頂堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapAdjust(arr, i, n);
        }

        for (int i = 0; i < n - 1; i++) {
            swap(arr, 0, n - i - 1);
            heapAdjust(arr, 0, n - i - 1);
        }
    }

    // 交換兩個(gè)數(shù)
    static void swap(int arr[], int low, int high) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }

    // 調(diào)整堆
    static void heapAdjust(int arr[], int index, int n) {

        int temp = arr[index];

        int child = 0;

        while (index * 2 + 1 < n) {
                        
            child = index * 2 + 1;
                        
            // child為左右孩子中較大的那個(gè)
            if (child != n - 1 && arr[child] < arr[child + 1]) {
                child++;
            }
            // 如果指定節(jié)點(diǎn)大于較大的孩子 不需要調(diào)整
            if (temp > arr[child]) {
                break;
            } else {
                // 否則繼續(xù)往下判斷孩子的孩子 直到找到合適的位置
                arr[index] = arr[child];
                index = child;
            }
        }

        arr[index] = temp;
    }
}

• 分析

由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件戳稽。堆排序時(shí)間復(fù)雜度也為O(nlogn)馆蠕，空間復(fù)雜度為O(1)。它是不穩(wěn)定的排序方法惊奇。與快排和歸并排序相比互躬，堆排序在最差情況下的時(shí)間復(fù)雜度優(yōu)于快排，空間效率高于歸并排序颂郎。

2. 查找相關(guān)算法

1. 順序查找

順序查找又稱線性查找吼渡。它的過程為：從查找表的最后一個(gè)元素開始逐個(gè)與給定關(guān)鍵字比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等乓序，則查找成功寺酪，否則，若直至第一個(gè)記錄替劈，其關(guān)鍵字和給定值比較都不等寄雀，則表明表中沒有所查記錄查找不成功，它的缺點(diǎn)是效率低下陨献。

2. 二分查找

• 簡(jiǎn)介
  二分查找又稱折半查找盒犹，對(duì)于有序表來說，它的優(yōu)點(diǎn)是比較次數(shù)少眨业，查找速度快急膀，平均性能好。
  二分查找的基本思想是將n個(gè)元素分成大致相等的兩部分龄捡，取a[n/2]與x做比較脖阵，如果x=a[n/2],則找到x，算法中止墅茉；如果x<a[n/2]命黔，則只要在數(shù)組a的左半部分繼續(xù)搜索x，如果x>a[n/2]就斤，則只要在數(shù)組a的右半部搜索x悍募。
  二分查找的時(shí)間復(fù)雜度為O(logn)
• 算法
• 代碼實(shí)現(xiàn)

//給定有序查找表array 二分查找給定的值data
//查找成功返回下標(biāo) 查找失敗返回-1

static int funBinSearch(int[] array, int data) {

    int low = 0;
    int high = array.length - 1;

    while (low <= high) {

        int mid = (low + high) / 2;

        if (data == array[mid]) {
            return mid;
        } else if (data < array[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

3. 經(jīng)典算法

3.1.遞歸算法

• 簡(jiǎn)介

在平常解決一些編程或者做一些算法題的時(shí)候，經(jīng)常會(huì)用到遞歸洋机。程序調(diào)用自身的編程技巧稱為遞歸坠宴。它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解。上面介紹的快速排序和歸并排序都用到了遞歸的思想绷旗。

• 實(shí)例代碼

1. 斐波那契數(shù)列喜鼓，又稱黃金分割數(shù)列副砍、因數(shù)學(xué)家列昂納多·斐波那契以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”庄岖，指的是這樣一個(gè)數(shù)列：0豁翎、1、1隅忿、2心剥、3、5背桐、8优烧、13、21链峭、34畦娄、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F（0）=0弊仪，F(xiàn)（1）=1熙卡，F(xiàn)（n）=F(n-1)+F(n-2)（n≥2，n∈N*）撼短。

//斐波那契數(shù)列 遞歸實(shí)現(xiàn)
static long funFib(long index) {

    if (index == 0) {
        return 0;
    } else if (index == 1) {
        return 1;
    } else {
        return funFib(index - 1) + funFib(index - 2);
    }
}

上面代碼是斐波那契數(shù)列的遞歸實(shí)現(xiàn)再膳，然而我們不難得到它的時(shí)間復(fù)雜度是O(2^n)，遞歸有時(shí)候可以很方便地解決一些問題曲横，但是它也會(huì)帶來一些效率上的問題喂柒。下面的代碼是求斐波那契數(shù)列的另一種方式，效率比遞歸方法的效率高禾嫉。

static long funFib2(long index) {

    long f0 = 0;
    long f1 = 1;
    long f2 = 1;

    if (index == 0) {
        return f0;
    } else if (index == 1) {
        return f1;
    } else if (index == 2) {
        return f2;
    }

    for (int i = 3; i <= index; i++) {
        f0 = f1;
        f1 = f2;
        f2 = f0 + f1;
    }

    return f2;
}

• 分析

3.2.分治算法

• 簡(jiǎn)介

分治算法的思想是將待解決的問題分解為幾個(gè)規(guī)模較小但類似于原問題的子問題灾杰，遞歸地求解這些子問題，然后合并這些子問題的解來建立最終的解熙参。分治算法中關(guān)鍵地一步其實(shí)就是遞歸地求解子問題艳吠。關(guān)于分治算法的一個(gè)典型例子就是上面介紹的歸并排序。百度講解

• 實(shí)例
• 分析

3.3.動(dòng)態(tài)規(guī)劃

• 簡(jiǎn)介

動(dòng)態(tài)規(guī)劃與分治方法相似孽椰，都是通過組合子問題的解來求解待解決的問題昭娩。但是，分治算法將問題劃分為互不相交的子問題黍匾，遞歸地求解子問題栏渺，再將它們的解組合起來，而動(dòng)態(tài)規(guī)劃應(yīng)用于子問題重疊的情況锐涯，即不同的子問題具有公共的子子問題磕诊。動(dòng)態(tài)規(guī)劃方法通常用來求解最優(yōu)化問題。查看更多關(guān)于動(dòng)態(tài)規(guī)劃的內(nèi)容百度百科介紹
動(dòng)態(tài)規(guī)劃典型的一個(gè)例子是最長(zhǎng)公共子序列問題可以參考大神播客。

4. 鏈表相關(guān)算法

需要掌握的算法

1. 圖搜索 （廣度優(yōu)先霎终、深度優(yōu)先）
2. 排序
3. 動(dòng)態(tài)規(guī)劃
4. 匹配算法和網(wǎng)絡(luò)流算法
5. 正則表達(dá)式和字符串匹配
6. 貪婪算法
7. 概率方法
8. 近似算法
9. 三路劃分-快速排序
10. 合并排序（更具擴(kuò)展性滞磺，復(fù)雜度類似快速排序）
11. DF/BF 搜索 （要知道使用場(chǎng)景）
12. Prim / Kruskal （最小生成樹）
13. Dijkstra （最短路徑算法）
14. 選擇算法
15. 遺傳算法

比較好的算法學(xué)習(xí)文章：

• 15道使用頻率極高的基礎(chǔ)算法題
• 輕松搞定面試中的二叉樹題目
• JAVA中關(guān)于鏈表的操作和基本算法
• 字符串相關(guān)算法問題