數(shù)據(jù)結(jié)構(gòu)與算法

數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)指的是“一組數(shù)據(jù)的存儲結(jié)構(gòu)”，算法指的是“操作數(shù)據(jù)的一組方法”。

數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的，算法是要作用再特定的數(shù)據(jù)結(jié)構(gòu)上的。最常用的數(shù)據(jù)結(jié)構(gòu)預(yù)算法:數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊(duì)列、散列表、二叉樹、堆、跳表、圖、Tire樹

算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法

1

算法的復(fù)雜度

1.1大O復(fù)雜度表示法

T(n)表示代碼執(zhí)行的時間;n表示數(shù)據(jù)規(guī)模的大小;f(n)表示每行代碼執(zhí)行的次數(shù)總和。因?yàn)檫@是一個公式，所以用f(n)來表示。公式中的O,表示代碼的執(zhí)行時間T(n)與f(n)表達(dá)式成正比。

所以，第一個例子中的T(n)=O(2n+2)，第二個例子中的T(m)=0(2n2+2n+3)。這就是大O時間復(fù)雜度表示法。大O時間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時間，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢，所以，也叫作漸進(jìn)時間復(fù)雜度(asymptotictimecomplexity)，簡稱時間復(fù)雜度。

當(dāng)n很大時，你可以把它想象成10000、100000。而公式中的低階、常量、系數(shù)三部分并不左右增長趨勢,所以都可以忽略。我們只需要記錄-個最大量級就可以了，如果用大O表示法表示剛講的那兩段代碼的時間復(fù)雜度,就可以記為:T(n)=O(n);T(n)=0(n2)。

1.2.復(fù)雜度分析法則

1）單段代碼看高頻：比如循環(huán)。

2）多段代碼取最大：比如一段代碼中有單循環(huán)和多重循環(huán)，那么取多重循環(huán)的復(fù)雜度。

3）嵌套代碼求乘積：比如遞歸、多重循環(huán)等

4）多個規(guī)模求加法：比如方法有兩個參數(shù)控制兩個循環(huán)的次數(shù)，那么這時就取二者復(fù)雜度相加。1.3時間復(fù)雜度分析只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼

加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度

乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積

1.4幾種常見時間復(fù)雜度實(shí)例分析多項(xiàng)式階：隨著數(shù)據(jù)規(guī)模的增長，算法的執(zhí)行時間和空間占用，按照多項(xiàng)式的比例增長。包括，

O(1)（常數(shù)階）、O(logn)（對數(shù)階）、O(n)（線性階）、O(nlogn)（線性對數(shù)階）、O(n^2)（平方階）、O(n^3)（立方階）

非多項(xiàng)式階：隨著數(shù)據(jù)規(guī)模的增長，算法的執(zhí)行時間和空間占用暴增，這類算法性能極差。包括，

O(2^n)（指數(shù)階）、O(n!)（階乘階）O(1):

常量級時間復(fù)雜度,只要代碼的執(zhí)行時間不隨n的增大而增長，這樣代碼的時間復(fù)雜度我們都記作O(1)。O(logn)、O(nlogn)

i=1;

while(i<=n){

i=i*2;

}

x=log2n，所以，這段代碼的時間復(fù)雜度就是O(log2n)O(m+n)、O(m*n)

intcal(intm,intn){

intsum_1=0;

inti=1;

for(;i<m;++i){

sum_1=sum_1+i;

}

intsum_2=0;

intj=1;

for(;j<n;++j){

sum_2=sum_2+j;

}

returnsum_1+sum_2;

}

從代碼中可以看出，m和n是表示兩個數(shù)據(jù)規(guī)模。我們無法事先評估m(xù)和n誰的量級大，所以我們在表示復(fù)雜度的時候，就不能簡單地利用加法法則，省略掉其中一個。所以，上面代碼的時間復(fù)雜度就是0(m+n)。針對這種情況，原來的加法法則就不正確了，我們需要將加法規(guī)則改為:T1(m)+T2(m)=O(f(m)+g(n))。但是乘法法則繼續(xù)有效:T1(m)*T2(n)=O(f(m)*f(n))。1.5空間復(fù)雜度分析表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。voidprint(intn){

inti=0;

int[]a=newint[n];

for(i;i<n;++i){

a[i]=i*i;

}

for(i=n-1;i>=0;--i){

printouta[i]

}

}

跟時間復(fù)雜度分析一樣，我們可以看到，第2行代碼中，我們申請了一個空間存儲變量i,但是它是常最階的，跟數(shù)據(jù)規(guī)模n沒有關(guān)系，所以我們可以忽略。第3行申請了一個大小為n的int類型數(shù)組，除此之外，剩下的代碼都沒有占用更多的空間，所以整段代碼的空間復(fù)雜度就是O(n)。我們常見的空間復(fù)雜度就是O(1)、O(n)、O(n2),像O(logn)、O(nlogn)這樣的對數(shù)階復(fù)雜度平時都用不到。而且，空間復(fù)雜度分析比時間復(fù)雜度分析要簡單很多。所以，對于空間復(fù)雜度，掌握剛我說的這些內(nèi)容已經(jīng)足夠了。1.6復(fù)雜度增長趨勢圖:

最好情況時間復(fù)雜度、最壞時間復(fù)雜度、平均情況時間復(fù)雜度、均攤時間復(fù)雜度。一、復(fù)雜度分析的4個概念

1.最壞情況時間復(fù)雜度：代碼在最壞情況下執(zhí)行的時間復(fù)雜度。

2.最好情況時間復(fù)雜度：代碼在最理想情況下執(zhí)行的時間復(fù)雜度。

3.平均時間復(fù)雜度：代碼在所有情況下執(zhí)行的次數(shù)的加權(quán)平均值。

4.均攤時間復(fù)雜度：在代碼執(zhí)行的所有復(fù)雜度情況中絕大部分是低級別的復(fù)雜度，個別情況是高級別復(fù)雜度且發(fā)生具有時序關(guān)系時，可以將個別高級別復(fù)雜度均攤到低級別復(fù)雜度上?；旧暇鶖偨Y(jié)果就等于低級別復(fù)雜度。二、為什么要引入這4個概念？

1.同一段代碼在不同情況下時間復(fù)雜度會出現(xiàn)量級差異，為了更全面，更準(zhǔn)確的描述代碼的時間復(fù)雜度，所以引入這4個概念。

2.代碼復(fù)雜度在不同情況下出現(xiàn)量級差別時才需要區(qū)別這四種復(fù)雜度。大多數(shù)情況下，是不需要區(qū)別分析它們的。三、如何分析平均、均攤時間復(fù)雜度？

1.平均時間復(fù)雜度

代碼在不同情況下復(fù)雜度出現(xiàn)量級差別，則用代碼所有可能情況下執(zhí)行次數(shù)的加權(quán)平均值表示。

2.均攤時間復(fù)雜度

兩個條件滿足時使用：1）代碼在絕大多數(shù)情況下是低級別復(fù)雜度，只有極少數(shù)情況是高級別復(fù)雜度；2）低級別和高級別復(fù)雜度出現(xiàn)具有時序規(guī)律。均攤結(jié)果一般都等于低級別復(fù)雜度。1、數(shù)組

線性表:

線性表就是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu).每個現(xiàn)行表上的數(shù)據(jù)最多只有前和后兩個方向.常見的線性表結(jié)構(gòu)：數(shù)組，鏈表、隊(duì)列、棧等。

什么是數(shù)組:

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

連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)(隨機(jī)訪問的前提)

優(yōu)點(diǎn)：兩限制使得具有隨機(jī)訪問的特性缺點(diǎn)：刪除，插入數(shù)據(jù)效率低

數(shù)組怎么根據(jù)下標(biāo)隨機(jī)訪問的？

通過尋址公式：a[i]_address=base_address+i*data_type_size

其中data_type_size表示數(shù)組中每個元素的大小,base_address是首元素地址,i數(shù)組下標(biāo)。

為何數(shù)組插入和刪除低效：插入：

若有一元素想往int[n]的第k個位置插入數(shù)據(jù)，需要在k-n的位置往后移。

最好情況時間復(fù)雜度O(1)

如果數(shù)組中的數(shù)據(jù)不是有序的，也就是無規(guī)律的情況下，可以直接把第k個位置上的數(shù)據(jù)移到最后，然后將插入的數(shù)據(jù)直接放在第k個位置上。最壞情況復(fù)雜度為O(n)

平均負(fù)責(zé)度為O(n)2.低效的插入和刪除

1）插入：從最好O(1)最壞O(n)平均O(n)

2）插入：數(shù)組若無序，插入新的元素時，可以將第K個位置元素移動到數(shù)組末尾，把心的元素，插入到第k個位置，此處復(fù)雜度為O(1)。

3）刪除：從最好O(1)最壞O(n)平均O(n)

4）多次刪除集中在一起，提高刪除效率

記錄下已經(jīng)被刪除的數(shù)據(jù)，每次的刪除操作并不是搬移數(shù)據(jù)，只是記錄數(shù)據(jù)已經(jīng)被刪除，當(dāng)數(shù)組沒有更多的存儲空間時，再觸發(fā)一次真正的刪除操作。即JVM標(biāo)記清除垃圾回收算法。

2、鏈表

什么是鏈表

1.和數(shù)組一樣，鏈表也是一種線性表。

2.從內(nèi)存結(jié)構(gòu)來看，鏈表的內(nèi)存結(jié)構(gòu)是不連續(xù)的內(nèi)存空間，是將一組零散的內(nèi)存塊串聯(lián)起來，從而進(jìn)行數(shù)據(jù)存儲的數(shù)據(jù)結(jié)構(gòu)。

3.鏈表中的每一個內(nèi)存塊被稱為節(jié)點(diǎn)Node。節(jié)點(diǎn)除了存儲數(shù)據(jù)外，還需記錄鏈上下一個節(jié)點(diǎn)的地址，即后繼指針next。

鏈表的特點(diǎn)

1.插入、刪除數(shù)據(jù)效率高O(1)級別（只需更改指針指向即可），隨機(jī)訪問效率低O(n)級別（需要從鏈頭至鏈尾進(jìn)行遍歷）。

2.和數(shù)組相比，內(nèi)存空間消耗更大，因?yàn)槊總€存儲數(shù)據(jù)的節(jié)點(diǎn)都需要額外的空間存儲后繼指針。常用鏈表

1.單鏈表

1）每個節(jié)點(diǎn)只包含一個指針，即后繼指針。

2）單鏈表有兩個特殊的節(jié)點(diǎn)，即首節(jié)點(diǎn)和尾節(jié)點(diǎn)。為什么特殊？用首節(jié)點(diǎn)地址表示整條鏈表，尾節(jié)點(diǎn)的后繼指針指向空地址null。

3）性能特點(diǎn)：插入和刪除節(jié)點(diǎn)的時間復(fù)雜度為O（1），查找的時間復(fù)雜度為O(n)。

2.循環(huán)鏈表

1）除了尾節(jié)點(diǎn)的后繼指針指向首節(jié)點(diǎn)的地址外均與單鏈表一致。

2）適用于存儲有循環(huán)特點(diǎn)的數(shù)據(jù)，比如約瑟夫問題。

3.雙向鏈表

1）節(jié)點(diǎn)除了存儲數(shù)據(jù)外，還有兩個指針分別指向前一個節(jié)點(diǎn)地址（前驅(qū)指針prev）和下一個節(jié)點(diǎn)地址（后繼指針next）。

2）首節(jié)點(diǎn)的前驅(qū)指針prev和尾節(jié)點(diǎn)的后繼指針均指向空地址。

3）性能特點(diǎn)：

和單鏈表相比，存儲相同的數(shù)據(jù)，需要消耗更多的存儲空間。

插入、刪除操作比單鏈表效率更高O(1)級別。以刪除操作為例，刪除操作分為2種情況：給定數(shù)據(jù)值刪除對應(yīng)節(jié)點(diǎn)和給定節(jié)點(diǎn)地址刪除節(jié)點(diǎn)。對于前一種情況，單鏈表和雙向鏈表都需要從頭到尾進(jìn)行遍歷從而找到對應(yīng)節(jié)點(diǎn)進(jìn)行刪除，時間復(fù)雜度為O(n)。對于第二種情況，要進(jìn)行刪除操作必須找到前驅(qū)節(jié)點(diǎn)，單鏈表需要從頭到尾進(jìn)行遍歷直到p->next=q，時間復(fù)雜度為O(n)，而雙向鏈表可以直接找到前驅(qū)節(jié)點(diǎn)，時間復(fù)雜度為O(1)。

對于一個有序鏈表，雙向鏈表的按值查詢效率要比單鏈表高一些。因?yàn)槲覀兛梢杂涗浬洗尾檎业奈恢胮，每一次查詢時，根據(jù)要查找的值與p的大小關(guān)系，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)。4.雙向循環(huán)鏈表：

首節(jié)點(diǎn)的前驅(qū)指針指向尾節(jié)點(diǎn)，尾節(jié)點(diǎn)的后繼指針指向首節(jié)點(diǎn)。選擇數(shù)組還是鏈表？

1.插入、刪除和隨機(jī)訪問的時間復(fù)雜度

數(shù)組：插入、刪除的時間復(fù)雜度是O(n)，隨機(jī)訪問的時間復(fù)雜度是O(1)。

鏈表：插入、刪除的時間復(fù)雜度是O(1)，隨機(jī)訪問的時間復(fù)雜端是O(n)。

2.數(shù)組缺點(diǎn)

1）若申請內(nèi)存空間很大，比如100M，但若內(nèi)存空間沒有100M的連續(xù)空間時，則會申請失敗，盡管內(nèi)存可用空間超過100M。

2）大小固定，若存儲空間不足，需進(jìn)行擴(kuò)容，一旦擴(kuò)容就要進(jìn)行數(shù)據(jù)復(fù)制，而這時非常費(fèi)時的。

3.鏈表缺點(diǎn)

1）內(nèi)存空間消耗更大，因?yàn)樾枰~外的空間存儲指針信息。

2）對鏈表進(jìn)行頻繁的插入和刪除操作，會導(dǎo)致頻繁的內(nèi)存申請和釋放，容易造成內(nèi)存碎片，如果是Java語言，還可能會造成頻繁的GC（自動垃圾回收器）操作。

4.如何選擇？

數(shù)組簡單易用，在實(shí)現(xiàn)上使用連續(xù)的內(nèi)存空間，可以借助CPU的緩沖機(jī)制預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高，而鏈表在內(nèi)存中并不是連續(xù)存儲，所以對CPU緩存不友好，沒辦法預(yù)讀。

如果代碼對內(nèi)存的使用非?？量?，那數(shù)組就更適合。應(yīng)用

1.如何分別用鏈表和數(shù)組實(shí)現(xiàn)LRU緩沖淘汰策略？

1）什么是緩存？

緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)，在硬件設(shè)計、軟件開發(fā)中都有著非廣泛的應(yīng)用，比如常見的CPU緩存、數(shù)據(jù)庫緩存、瀏覽器緩存等等。

2）為什么使用緩存？即緩存的特點(diǎn)

緩存的大小是有限的，當(dāng)緩存被用滿時，哪些數(shù)據(jù)應(yīng)該被清理出去，哪些數(shù)據(jù)應(yīng)該被保留？就需要用到緩存淘汰策略。

3）什么是緩存淘汰策略？

指的是當(dāng)緩存被用滿時清理數(shù)據(jù)的優(yōu)先順序。

4）有哪些緩存淘汰策略？

常見的3種包括先進(jìn)先出策略FIFO（FirstIn，F(xiàn)irstOut）、最少使用策略LFU（LeastFrenquentlyUsed）、最近最少使用策略LRU（LeastRecentlyUsed）。

5）鏈表實(shí)現(xiàn)LRU緩存淘汰策略

當(dāng)訪問的數(shù)據(jù)沒有存儲在緩存的鏈表中時，直接將數(shù)據(jù)插入鏈表表頭，時間復(fù)雜度為O(1)；當(dāng)訪問的數(shù)據(jù)存在于存儲的鏈表中時，將該數(shù)據(jù)對應(yīng)的節(jié)點(diǎn)，插入到鏈表表頭,時間復(fù)雜度為O(n)。如果緩存被占滿，則從鏈表尾部的數(shù)據(jù)開始清理，時間復(fù)雜度為O(1)。

6）數(shù)組實(shí)現(xiàn)LRU緩存淘汰策略

方式一：首位置保存最新訪問數(shù)據(jù)，末尾位置優(yōu)先清理

當(dāng)訪問的數(shù)據(jù)未存在于緩存的數(shù)組中時，直接將數(shù)據(jù)插入數(shù)組第一個元素位置，此時數(shù)組所有元素需要向后移動1個位置，時間復(fù)雜度為O(n)；當(dāng)訪問的數(shù)據(jù)存在于緩存的數(shù)組中時，查找到數(shù)據(jù)并將其插入數(shù)組的第一個位置，此時亦需移動數(shù)組元素，時間復(fù)雜度為O(n)。緩存用滿時，則清理掉末尾的數(shù)據(jù)，時間復(fù)雜度為O(1)。

方式二：首位置優(yōu)先清理，末尾位置保存最新訪問數(shù)據(jù)

當(dāng)訪問的數(shù)據(jù)未存在于緩存的數(shù)組中時，直接將數(shù)據(jù)添加進(jìn)數(shù)組作為當(dāng)前最有一個元素時間復(fù)雜度為O(1)；當(dāng)訪問的數(shù)據(jù)存在于緩存的數(shù)組中時，查找到數(shù)據(jù)并將其插入當(dāng)前數(shù)組最后一個元素的位置，此時亦需移動數(shù)組元素，時間復(fù)雜度為O(n)。緩存用滿時，則清理掉數(shù)組首位置的元素，且剩余數(shù)組元素需整體前移一位，時間復(fù)雜度為O(n)。（優(yōu)化：清理的時候可以考慮一次性清理一定數(shù)量，從而降低清理次數(shù)，提高性能。）

2.如何通過單鏈表實(shí)現(xiàn)“判斷某個字符串是否為水仙花字符串”？（比如上海自來水來自海上）

1）前提：字符串以單個字符的形式存儲在單鏈表中。

2）遍歷鏈表，判斷字符個數(shù)是否為奇數(shù)，若為偶數(shù)，則不是。

3）將鏈表中的字符倒序存儲一份在另一個鏈表中。

4）同步遍歷2個鏈表，比較對應(yīng)的字符是否相等，若相等，則是水仙花字串，否則，不是。

六、設(shè)計思想

時空替換思想：“用空間換時間”與“用時間換空間”

當(dāng)內(nèi)存空間充足的時候，如果我們更加追求代碼的執(zhí)行速度，我們就可以選擇空間復(fù)雜度相對較高，時間復(fù)雜度小相對較低的算法和數(shù)據(jù)結(jié)構(gòu)，緩存就是空間換時間的例子。如果內(nèi)存比較緊缺，比如代碼跑在手機(jī)或者單片機(jī)上，這時，就要反過來用時間換空間的思路。

3、隊(duì)列

什么是隊(duì)列:隊(duì)列是一種受限的線性表數(shù)據(jù)結(jié)構(gòu),只支持兩個操作:入棧push()和出棧pop0,隊(duì)列跟非常相似,支持的操作也,很有限,最基本的操作也是兩個:入隊(duì)enqueue(),放一個數(shù)據(jù)到隊(duì)列尾部;出隊(duì)dequeue0),從隊(duì)列頭部取一個元素。

特點(diǎn):1.隊(duì)列跟棧一樣,也是一種抽象的數(shù)據(jù)結(jié)構(gòu)。2.具有先進(jìn)先出的特性,支持在隊(duì)尾插入元素,在隊(duì)頭刪除元素。

實(shí)現(xiàn):隊(duì)列可以用數(shù)組來實(shí)現(xiàn),也可以用鏈表來實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的隊(duì)列叫作順序隊(duì)列,用鏈表實(shí)現(xiàn)的隊(duì)列叫作鏈?zhǔn)疥?duì)列。

基于數(shù)組的隊(duì)列:實(shí)現(xiàn)思路:實(shí)現(xiàn)隊(duì)列需要兩個指針:一個是head指針,指向隊(duì)頭;一個是tail指針,指向隊(duì)尾。你可以結(jié)合下面這幅圖來理解。當(dāng)a,b,c,d依次入隊(duì)之后,隊(duì)列中的head指針指向下標(biāo)為0的位置,tail指針指向下標(biāo)為4的位置。

當(dāng)我們調(diào)用兩次出隊(duì)操作之后,隊(duì)列中head指針指向下標(biāo)為2的位置,tail指針仍然指向下標(biāo)為4的位置.

隨著不停地進(jìn)行入隊(duì)、出隊(duì)操作,head和tail都會持續(xù)往后移動。當(dāng)tail移.,動到最右邊,即使數(shù)組中還有空閑空間,也無法繼續(xù)往隊(duì)列中添加數(shù)據(jù)了。這個問題該如何解決呢?在出隊(duì)時可以不用搬移數(shù)據(jù)。如果沒有空閑空間了,我們只需要在入隊(duì)時,再集中觸,發(fā)一次數(shù)據(jù)的搬移操作。當(dāng)隊(duì)列的tail指針移動到數(shù)組的最右邊后,如果有新的數(shù)據(jù)入隊(duì),我們可以將head到tail之間的數(shù)據(jù),整體搬移到數(shù)組中0到tail-head的位置。

基于鏈表的實(shí)現(xiàn):

需要兩個指針:head指針和tail指針,它們分別指向鏈表的第一個結(jié),點(diǎn)和最后一個結(jié)點(diǎn)。如圖所示,入隊(duì)時,tail->next=newnode,tail=tail->next:出隊(duì)時,head=head->next.

循環(huán)隊(duì)列:我們剛才用數(shù)組來實(shí)現(xiàn)隊(duì)列的時候,在tail==n時,會有數(shù)據(jù)搬移操作,這樣入隊(duì)操作性能就會受到影響。那有沒有辦法能夠避免數(shù)據(jù)搬移呢?我們來看看循環(huán)隊(duì)列的解決思路。循環(huán)隊(duì)列,顧名思義,它長得像一個環(huán)。原本數(shù)組是有頭有尾的,是一條直線。現(xiàn)在我們把首尾相,連,板成了一個環(huán)。我畫了一張圖,你可以直觀地感受一下。

我們可以看到,圖中這個隊(duì)列的大小為8,當(dāng)前head-4,tail-7,當(dāng)有一個新的元素a入隊(duì)時,.我們放入下標(biāo)為7的位置。但這個時候,我們并不把tail更新為8,而是將其在環(huán)中后移一位,到下標(biāo)為0的位置。當(dāng)再有一個元素b入隊(duì)時,我們將b放入下標(biāo)為0的位置,然后tail加1更新為1,所以,在a,b依次入隊(duì)之后,循環(huán)隊(duì)列中的元素就變成了下面的樣子:

隊(duì)列為空的判斷條件是head==tail,但隊(duì)列滿的判斷條件就稍微有點(diǎn)復(fù)雜了。我畫了一張隊(duì)列滿的圖,你可以看一下,試著總結(jié)一下規(guī)律,

就像我圖中畫的隊(duì)滿的情況,tail=3,head-4,n=8,所以總結(jié)一下規(guī)律就是:(3+1)%8-4,多畫幾張隊(duì)滿的圖,你就會發(fā)現(xiàn),當(dāng)隊(duì)滿時,(tail+1)%n=head..你有沒有發(fā)現(xiàn),當(dāng)隊(duì)列滿時,圖中的tail指向的位置實(shí)際上是沒有存儲數(shù)據(jù)的。所以,循環(huán)隊(duì)列會浪費(fèi)一個數(shù)組的存儲空間。解決浪費(fèi)一個存儲空間的思路:定義一個記錄隊(duì)列大小的值size，當(dāng)這個值與數(shù)組大小相等時，表示隊(duì)列已滿，當(dāng)tail達(dá)到最底時，size不等于數(shù)組大小時，tail就指向數(shù)組第一個位置。當(dāng)出隊(duì)時，size—，入隊(duì)時size++阻塞隊(duì)列和并發(fā)隊(duì)列(應(yīng)用比較廣泛)阻塞隊(duì)列其實(shí)就是在隊(duì)列基礎(chǔ)上增加了阻塞操作。簡單來說,就是在隊(duì)列為空的時候,從隊(duì)頭取數(shù),據(jù)會被阻塞。因?yàn)榇藭r還沒有數(shù)據(jù)可取,直到隊(duì)列中有了數(shù)據(jù)才能返回;如果隊(duì)列已經(jīng)滿了,那么插入數(shù)據(jù)的操作就會被阻塞,直到隊(duì)列中有空閑位置后再插入數(shù)據(jù),然后再返回。

你應(yīng)該已經(jīng)發(fā)現(xiàn)了,上述的定義就是一個"生產(chǎn)者-消費(fèi)者模型"!是的,我們可以使用阻塞隊(duì)列,輕松實(shí)現(xiàn)一個"生產(chǎn)者-消費(fèi)者模型"!這種基干陰寒隊(duì)列實(shí)現(xiàn)的"生產(chǎn)者-消費(fèi)者模型",可以有效地協(xié)調(diào)生產(chǎn)和消費(fèi)的速度。當(dāng)"生產(chǎn),者"生產(chǎn)數(shù)據(jù)的速度過快,"消費(fèi)者"來不及消費(fèi)時,存儲數(shù)據(jù)的隊(duì)列很快就會滿了。這個時候,生產(chǎn)者就阻塞等待,直到"消費(fèi)者"消費(fèi)了數(shù)據(jù),"生產(chǎn)者"才會被喚醒繼續(xù)"生產(chǎn)而且不僅如此,基于阻塞隊(duì)列,我們還可以通過協(xié)調(diào)"生產(chǎn)者"和"消費(fèi)者"的個數(shù),來提高數(shù)據(jù),的處理效率。比如前面的例子,我們可以多配置幾個"消費(fèi)者",來應(yīng)對一個"生產(chǎn)者"

小結(jié):隊(duì)列最大的特點(diǎn)就是先進(jìn)先出,主要的兩個操作是入隊(duì)和出隊(duì)。它既可以用數(shù)組來實(shí)現(xiàn),也可以用鏈表來實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的叫順序隊(duì)列,用鏈表實(shí)現(xiàn)的叫鏈?zhǔn)疥?duì)列。長在數(shù)組實(shí)現(xiàn)隊(duì)列的時候,會有數(shù)據(jù)搬移操作,要想解決數(shù)據(jù)搬移的問題,我們就,需要像環(huán)一樣的循環(huán)隊(duì)列。要想寫出沒有bug的循環(huán)隊(duì)列實(shí)現(xiàn)代碼,關(guān)鍵要確定好隊(duì)空和隊(duì)滿的,判定條件。阻塞隊(duì)列、并發(fā)隊(duì)列,底層都還是隊(duì)列這種數(shù)據(jù)結(jié)構(gòu),只不過在之上附加了很多其他功能。阻塞隊(duì)列就是入隊(duì)、出隊(duì)操作可以陰寒,并發(fā)隊(duì)列就是隊(duì)列的操作多線程安全。

4、遞歸算法

一、什么是遞歸？1.遞歸是一種非常高效、簡潔的編碼技巧，一種應(yīng)用非常廣泛的算法，比如DFS深度優(yōu)先搜索、前中后序二叉樹遍歷等都是使用遞歸。

2.方法或函數(shù)調(diào)用自身的方式稱為遞歸調(diào)用，調(diào)用稱為遞，返回稱為歸。

3.基本上，所有的遞歸問題都可以用遞推公式來表示，比如

f(n)=f(n-1)+1;

f(n)=f(n-1)+f(n-2);

f(n)=n*f(n-1);二、為什么使用遞歸？遞歸的優(yōu)缺點(diǎn)？1.優(yōu)點(diǎn)：代碼的表達(dá)力很強(qiáng)，寫起來簡潔。

2.缺點(diǎn)：空間復(fù)雜度高、有堆棧溢出風(fēng)險、存在重復(fù)計算、過多的函數(shù)調(diào)用會耗時較多等問題。三、什么樣的問題可以用遞歸解決呢？一個問題只要同時滿足以下3個條件，就可以用遞歸來解決：

1.問題的解可以分解為幾個子問題的解。何為子問題？就是數(shù)據(jù)規(guī)模更小的問題。

2.問題與子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣

3.存在遞歸終止條件四、如何實(shí)現(xiàn)遞歸？1.遞歸代碼編寫

寫遞歸代碼的關(guān)鍵就是找到如何將大問題分解為小問題的規(guī)律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼。

2.遞歸代碼理解

對于遞歸代碼，若試圖想清楚整個遞和歸的過程，實(shí)際上是進(jìn)入了一個思維誤區(qū)。

那該如何理解遞歸代碼呢？如果一個問題A可以分解為若干個子問題B、C、D，你可以假設(shè)子問題B、C、D已經(jīng)解決。而且，你只需要思考問題A與子問題B、C、D兩層之間的關(guān)系即可，不需要一層層往下思考子問題與子子問題，子子問題與子子子問題之間的關(guān)系。屏蔽掉遞歸細(xì)節(jié)，這樣子理解起來就簡單多了。

因此，理解遞歸代碼，就把它抽象成一個遞推公式，不用想一層層的調(diào)用關(guān)系，不要試圖用人腦去分解遞歸的每個步驟。遞歸的關(guān)鍵是終止條件

五、遞歸常見問題及解決方案1.警惕堆棧溢出：可以聲明一個全局變量來控制遞歸的深度，從而避免堆棧溢出。

2.警惕重復(fù)計算：通過某種數(shù)據(jù)結(jié)構(gòu)來保存已經(jīng)求解過的值，從而避免重復(fù)計算。六、如何將遞歸改寫為非遞歸代碼？籠統(tǒng)的講，所有的遞歸代碼都可以改寫為迭代循環(huán)的非遞歸寫法。如何做？抽象出遞推公式、初始值和邊界條件，然后用迭代循環(huán)實(shí)現(xiàn)。5、排序

一、排序方法與復(fù)雜度歸類

（1）幾種最經(jīng)典、最常用的排序方法：冒泡排序、插入排序、選擇排序、快速排序、歸并排序、計數(shù)排序、基數(shù)排序、桶排序。

（2）復(fù)雜度歸類

冒泡排序、插入排序、選擇排序O(n^2)

快速排序、歸并排序O(nlogn)

計數(shù)排序、基數(shù)排序、桶排序O(n)二、如何分析一個“排序算法”？

<1>算法的執(zhí)行效率

1.最好、最壞、平均情況時間復(fù)雜度。

2.時間復(fù)雜度的系數(shù)、常數(shù)和低階。

3.比較次數(shù)，交換（或移動）次數(shù)。

<2>排序算法的穩(wěn)定性

1.穩(wěn)定性概念：如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變。

2.穩(wěn)定性重要性：可針對對象的多種屬性進(jìn)行有優(yōu)先級的排序。

3.舉例：給電商交易系統(tǒng)中的“訂單”排序，按照金額大小對訂單數(shù)據(jù)排序，對于相同金額的訂單以下單時間早晚排序。用穩(wěn)定排序算法可簡潔地解決。先按照下單時間給訂單排序，排序完成后用穩(wěn)定排序算法按照訂單金額重新排序。

<3>排序算法的內(nèi)存損耗

原地排序算法：特指空間復(fù)雜度是O(1)的排序算法。常見的排序算法:

冒泡排序

冒泡排序只會操作相鄰的兩個數(shù)據(jù)。每次冒泡操作都會對相鄰的兩個元素進(jìn)行比較，看是否滿足大小關(guān)系要求，如果不滿足就讓它倆互換。代碼:publicint[]bubbleSort(int[]a){

intn=a.length;

if(n<=1){

returna;

}

for(inti=0;i<n;i++){

//提前退出冒泡循環(huán)的標(biāo)志

booleanflag=false;

for(intj=0;j<n-i-1;j++){

if(a[j]>a[j+1]){//

inttemp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

flag=true;//表示有數(shù)據(jù)交換

}

if(!flag){

break;//沒有數(shù)據(jù)交換(說明已排好序無需再進(jìn)行冒泡),提前退出

}

}

}

returna;

}四、插入排序

插入排序?qū)?shù)組數(shù)據(jù)分成已排序區(qū)間和未排序區(qū)間。初始已排序區(qū)間只有一個元素，即數(shù)組第一個元素。在未排序區(qū)間取出一個元素插入到已排序區(qū)間的合適位置，直到未排序區(qū)間為空。代碼:publicint[]insertionSort(int[]a){

intn=a.length;

if(n<=1)returna;

for(inti=1;i<n;i++){

intvalue=a[i];

intj=i-1;

for(;j>=0;j--){

if(a[j]>value){

a[j+1]=a[j];//移動數(shù)據(jù)

}else{

break;

}

}

a[j+1]=value;//插入數(shù)據(jù)

}

returna;

}五、選擇排序

選擇排序?qū)?shù)組分成已排序區(qū)間和未排序區(qū)間。初始已排序區(qū)間為空。每次從未排序區(qū)間中選出最小的元素插入已排序區(qū)間的末尾，直到未排序區(qū)間為空。

代碼:publicint[]selectionSort(int[]a){

intn=a.length;

for(inti=0;i<a.length-1;i++){

for(intj=i+1;j<a.length;j++){

//交換

if(a[i]>a[j]){

inttemp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

}

returna;

}

六、歸并排序如果要排序一個數(shù)組,我們先把數(shù)組從中間分成前后兩部分,然后對前后兩部分分別排序,再將排好序的兩部分合并在一起,這樣整個數(shù)組就都有序了。

實(shí)現(xiàn)思路:

merge-sort(p...r)表示,給下標(biāo)從p到r之間的數(shù)組排序。我們將這個排序問題轉(zhuǎn)化為了兩個子問,題,merge_sort(p...q)和merge-sort(q+1..r),其中下標(biāo)q等于p和r的中間位置,也就是,(p+r)/2,當(dāng)下標(biāo)從p到q和從q+1到r這兩個子數(shù)組都排好序之后,我們再將兩個有序的子數(shù)組合并在一起,這樣下標(biāo)從p到r之間的數(shù)據(jù)就也排好序了。代碼://歸并排序算法,a是數(shù)組，n表示數(shù)組大小

publicstaticvoidmergeSort(int[]a,intn){

mergeSortInternally(a,0,n-1);

}

//遞歸調(diào)用函數(shù)

privatestaticvoidmergeSortInternally(int[]a,intp,intr){

//遞歸終止條件

if(p>=r)return;

//取p到r之間的中間位置q

intq=(p+r)/2;

//分治遞歸

mergeSortInternally(a,p,q);

mergeSortInternally(a,q+1,r);

//將A[p...q]和A[q+1...r]合并為A[p...r]

merge(a,p,q,r);

}

privatestaticvoidmerge(int[]a,intp,intq,intr){

inti=p;

intj=q+1;

intk=0;//初始化變量i,j,k

int[]tmp=newint[r-p+1];//申請一個大小跟a[p...r]一樣的臨時數(shù)組

//1排序

while(i<=q&&j<=r){

if(a[i]<=a[j]){

tmp[k++]=a[i++];//i++等于i:=i+1

}else{

tmp[k++]=a[j++];

}

}

//2判斷哪個子數(shù)組中有剩余的數(shù)據(jù)

intstart=i;

intend=q;

if(j<=r){

start=j;

end=r;

}

//3將剩余的數(shù)據(jù)拷貝到臨時數(shù)組tmp

while(start<=end){

tmp[k++]=a[start++];

}

//4將tmp中的數(shù)組拷貝回a[p...r]

for(i=0;i<=r-p;++i){

a[p+i]=tmp[i];

}

}

merge是這樣執(zhí)行的:

代碼分析:

七、快速排序快排的思想:

如果要排序數(shù)組中下標(biāo)從p到r之間的一組數(shù)據(jù),我們選擇p到r之間的任意一個數(shù)據(jù)作為pivot(分區(qū)點(diǎn))。我們遍歷p到r之間的數(shù)據(jù),將小于pivot的放到左邊,將大于pivot的放到右邊,將pivot放到中間。經(jīng)過這一步驟之后,數(shù)組p到r之間的數(shù)據(jù)就被分成了三個部分,前面p到q-1之間都是小于pivot的,中間是pivot,后面的q+1到r之間是大于pivot的。八、線性排序:

時間復(fù)雜度O(n)我們把時間復(fù)雜度是線性的排序算法叫作線性排序(Linearsort)常見的線性算法有:

桶排序、計數(shù)排序、基數(shù)排序特點(diǎn):非基于比較的排序算法

桶排序

桶排序,顧名思義,會用到“桶",核心思想是將要排序的數(shù)據(jù)分到幾個有序的桶里,每個桶里的數(shù)據(jù)再單獨(dú)進(jìn)行排序。桶內(nèi)排完序之后,再把每個桶里的數(shù)據(jù)按照順序依次取出,組成的序列就是有序的了。對排序的數(shù)據(jù)要求苛刻:1,要排序的數(shù)據(jù)需要很容易就能劃分成m個桶,并且,桶與桶之間有著天然的大小順序。2,數(shù)據(jù)在各個桶之間的分布是比較均勻的。3,桶排序比較適合用在外部排序中。所謂的外部排序就是數(shù)據(jù)存儲在外部磁盤中,數(shù)據(jù)量比較大,內(nèi)存有限，無法將數(shù)據(jù)全部加載到內(nèi)存中。

計數(shù)排序計數(shù)排序只能用在數(shù)據(jù)范圍不大的場景中,如果數(shù)據(jù)范圍k比要排序的數(shù)據(jù)n大很多,就不適合用計數(shù)排序了。計數(shù)排序只能給非負(fù)整數(shù)排序,如果要排序的數(shù)據(jù)是其他類型的,要將其在不改變