本文是王爭老師的《算法與數據結構之美》的學習筆記，詳細內容請看王爭的專欄?。有不懂的地方指出來，我做修改。

數據結構與算法思維導圖

數據結構指的是“一組數據的存儲結構”，算法指的是“操作數據的一組方法”。
數據結構是為算法服務的，算法是要作用再特定的數據結構上的。

最常用的數據結構預算法:

• 數據結構：數組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Tire樹
• 算法： 遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態規劃、字符串匹配算法

1 ?算法的復雜度

1.1大O復雜度表示法

?公式:

T(n)表示代碼執行的時間; n表示數據規模的大小; f(n) 表示每行代碼執行的次數總和。因為這是一個公式， 所以用f(n)來表示。公式中的O,表示代碼的執行時間T(n)與f(n)表達式成正比。

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

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

1.2.復雜度分析法則

1）單段代碼看高頻：比如循環。
2）多段代碼取最大：比如一段代碼中有單循環和多重循環，那么取多重循環的復雜度。
3）嵌套代碼求乘積：比如遞歸、多重循環等
4）多個規模求加法：比如方法有兩個參數控制兩個循環的次數，那么這時就取二者復雜度相加。

1.3 時間復雜度分析

• 只關注循環執行次數最多的一段代碼
• 加法法則：總復雜度等于量級最大的那段代碼的復雜度
• 乘法法則：嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積

1.4 幾種常見時間復雜度實例分析

多項式階：隨著數據規模的增長，算法的執行時間和空間占用，按照多項式的比例增長。包括，
O(1)（常數階）、O(logn)（對數階）、O(n)（線性階）、O(nlogn)（線性對數階）、O(n^2)（平方階）、O(n^3)（立方階）
非多項式階：隨著數據規模的增長，算法的執行時間和空間占用暴增，這類算法性能極差。包括，
O(2^n)（指數階）、O(n!)（階乘階）

• O(1) :

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

• O(logn)、O(nlogn)

i=1; while(i<=n) {i = i*2; }

x=log2n，所以，這段代碼的時間復雜度就是 O(log2n)

• O(m+n)、O(m*n)

int cal(int m, int n) {int sum_1=0;int i=1;for(;i<m;++i){sum_1 = sum_1 + i;}int sum_2 = 0;int j=1;for (;j<n;++j){sum_2 = sum_2 + j;}return sum_1 + sum_2;}

從代碼中可以看出，m和n是表示兩個數據規模。我們無法事先評估m和n誰的量級大，所以我們在表示復雜度的時候，就不能簡單地利用加法法則，省略掉其中一個。所以，上面代碼的時間復 雜度就是0(m+n)。

針對這種情況，原來的加法法則就不正確了，我們需要將加法規則改為: T1(m) + T2(m) = O(f(m) + g(n))。但是乘法法則繼續有效: T1(m)*T2(n) = O(f(m) * f(n))。

1.5 空間復雜度分析

表示算法的存儲空間與數據規模之間的增長關系。

void print(int n) {inti=0;int[] a = new int[n];for (i; i <n; ++i) {a[i] =i* i;}for(i=n-1;i>=0;--i){print out a[i]} }

跟時間復雜度分析一樣，我們可以看到，第2行代碼中，我們申請了一個空間存儲變量i,但是它是常最階的，跟數據規模n沒有關系，所以我們可以忽略。第3行申請了一個大小為n的int類型數組，除此之外，剩下的代碼都沒有占用更多的空間，所以整段代碼的空間復雜度就是O(n)。

我們常見的空間復雜度就是O(1)、O(n)、 O(n2), 像O(logn)、O(nlogn) 這樣的對數階復雜度平時都用不到。而且，空間復雜度分析比時間復雜度分析要簡單很多。所以，對于空間復雜度，掌握剛我說的這些內容已經足夠了。

1.6 復雜度增長趨勢圖:

最好情況時間復雜度、最壞時間復雜度、平均情況時間復雜度、均攤時間復雜度。

一、復雜度分析的4個概念
1.最壞情況時間復雜度：代碼在最壞情況下執行的時間復雜度。
2.最好情況時間復雜度：代碼在最理想情況下執行的時間復雜度。
3.平均時間復雜度：代碼在所有情況下執行的次數的加權平均值。
4.均攤時間復雜度：在代碼執行的所有復雜度情況中絕大部分是低級別的復雜度，個別情況是高級別復雜度且發生具有時序關系時，可以將個別高級別復雜度均攤到低級別復雜度上。基本上均攤結果就等于低級別復雜度。

二、為什么要引入這4個概念？
1.同一段代碼在不同情況下時間復雜度會出現量級差異，為了更全面，更準確的描述代碼的時間復雜度，所以引入這4個概念。
2.代碼復雜度在不同情況下出現量級差別時才需要區別這四種復雜度。大多數情況下，是不需要區別分析它們的。

三、如何分析平均、均攤時間復雜度？
1.平均時間復雜度
代碼在不同情況下復雜度出現量級差別，則用代碼所有可能情況下執行次數的加權平均值表示。
2.均攤時間復雜度
兩個條件滿足時使用：1）代碼在絕大多數情況下是低級別復雜度，只有極少數情況是高級別復雜度；2）低級別和高級別復雜度出現具有時序規律。均攤結果一般都等于低級別復雜度。

1、數組

線性表: ? 線性表就是數據排成像一條線一樣的結構.每個現行表上的數據最多只有前和后兩個方向.常見的線性表結構：數組，鏈表、隊列、棧等。

什么是數組:

?數組（Array）是一種線性表數據結構。它用一組連續的內存空間，來存儲一組具有相同類型的數據。

?連續的內存空間和相同類型的數據(隨機訪問的前提)。

優點：兩限制使得具有隨機訪問的特性缺點：刪除，插入數據效率低。

對內存空間要求高，需要一塊連續的內存空間。

• 數組怎么根據下標隨機訪問的？

通過尋址公式：a[i]_address = base_address + i * data_type_size
其中data_type_size表示數組中每個元素的大小,base_address 是首元素地址,i數組下標。

為何數組插入和刪除低效：

插入：
若有一元素想往int[n]的第k個位置插入數據，需要在k-n的位置往后移。
最好情況時間復雜度 O(1)

如果數組中的數據不是有序的，也就是無規律的情況下，可以直接把第k個位置上的數據移到最后，然后將插入的數據直接放在第k個位置上。

最壞情況復雜度為O(n)

平均負責度為O(n)

2. 低效的插入和刪除
1） 插入：從最好O(1) 最壞O(n) 平均O(n)
2） 插入：數組若無序，插入新的元素時，可以將第K個位置元素移動到數組末尾，把心的元素，插入到第k個位置，此處復雜度為O(1)。
3） 刪除：從最好O(1) 最壞O(n) 平均O(n)
4） 多次刪除集中在一起，提高刪除效率
記錄下已經被刪除的數據，每次的刪除操作并不是搬移數據，只是記錄數據已經被刪除，當數組沒有更多的存儲空間時，再觸發一次真正的刪除操作。即JVM標記清除垃圾回收算法。

2、鏈表

• 什么是鏈表

1.和數組一樣，鏈表也是一種線性表。
2.從內存結構來看，鏈表的內存結構是不連續的內存空間，是將一組零散的內存塊串聯起來，從而進行數據存儲的數據結構。
3.鏈表中的每一個內存塊被稱為節點Node。節點除了存儲數據外，還需記錄鏈上下一個節點的地址，即后繼指針next。

• 鏈表的特點

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

2.和數組相比，內存空間消耗更大，因為每個存儲數據的節點都需要額外的空間存儲后繼指針。

• 常用鏈表

1.單鏈表

1）每個節點只包含一個指針，即后繼指針。
2）單鏈表有兩個特殊的節點，即首節點和尾節點。為什么特殊？用首節點地址表示整條鏈表，尾節點的后繼指針指向空地址null。
3）性能特點：插入和刪除節點的時間復雜度為O（1），查找的時間復雜度為O(n)。

2.循環鏈表

1）除了尾節點的后繼指針指向首節點的地址外均與單鏈表一致。
2）適用于存儲有循環特點的數據，比如約瑟夫問題。

3.雙向鏈表

1）節點除了存儲數據外，還有兩個指針分別指向前一個節點地址（前驅指針prev）和下一個節點地址（后繼指針next）。
2）首節點的前驅指針prev和尾節點的后繼指針均指向空地址。
3）性能特點：
和單鏈表相比，存儲相同的數據，需要消耗更多的存儲空間。
插入、刪除操作比單鏈表效率更高O(1)級別。以刪除操作為例，刪除操作分為2種情況：給定數據值刪除對應節點和給定節點地址刪除節點。對于前一種情況，單鏈表和雙向鏈表都需要從頭到尾進行遍歷從而找到對應節點進行刪除，時間復雜度為O(n)。對于第二種情況，要進行刪除操作必須找到前驅節點，單鏈表需要從頭到尾進行遍歷直到p->next = q，時間復雜度為O(n)，而雙向鏈表可以直接找到前驅節點，時間復雜度為O(1)。
對于一個有序鏈表，雙向鏈表的按值查詢效率要比單鏈表高一些。因為我們可以記錄上次查找的位置p，每一次查詢時，根據要查找的值與p的大小關系，決定是往前還是往后查找，所以平均只需要查找一半的數據。

4.雙向循環鏈表：

首節點的前驅指針指向尾節點，尾節點的后繼指針指向首節點。

• 選擇數組還是鏈表？

1.插入、刪除和隨機訪問的時間復雜度
數組：插入、刪除的時間復雜度是O(n)，隨機訪問的時間復雜度是O(1)。
鏈表：插入、刪除的時間復雜度是O(1)，隨機訪問的時間復雜端是O(n)。

2.數組缺點
1）若申請內存空間很大，比如100M，但若內存空間沒有100M的連續空間時，則會申請失敗，盡管內存可用空間超過100M。
2）大小固定，若存儲空間不足，需進行擴容，一旦擴容就要進行數據復制，而這時非常費時的。
3.鏈表缺點
1）內存空間消耗更大，因為需要額外的空間存儲指針信息。
2）對鏈表進行頻繁的插入和刪除操作，會導致頻繁的內存申請和釋放，容易造成內存碎片，如果是Java語言，還可能會造成頻繁的GC（自動垃圾回收器）操作。
4.如何選擇？
數組簡單易用，在實現上使用連續的內存空間，可以借助CPU的緩沖機制預讀數組中的數據，所以訪問效率更高，而鏈表在內存中并不是連續存儲，所以對CPU緩存不友好，沒辦法預讀。
如果代碼對內存的使用非常苛刻，那數組就更適合。

• 應用

1.如何分別用鏈表和數組實現LRU緩沖淘汰策略？
1）什么是緩存？
緩存是一種提高數據讀取性能的技術，在硬件設計、軟件開發中都有著非廣泛的應用，比如常見的CPU緩存、數據庫緩存、瀏覽器緩存等等。
2）為什么使用緩存？即緩存的特點
緩存的大小是有限的，當緩存被用滿時，哪些數據應該被清理出去，哪些數據應該被保留？就需要用到緩存淘汰策略。
3）什么是緩存淘汰策略？
指的是當緩存被用滿時清理數據的優先順序。
4）有哪些緩存淘汰策略？
常見的3種包括先進先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frenquently Used）、最近最少使用策略LRU（Least Recently Used）。
5）鏈表實現LRU緩存淘汰策略
當訪問的數據沒有存儲在緩存的鏈表中時，直接將數據插入鏈表表頭，時間復雜度為O(1)；當訪問的數據存在于存儲的鏈表中時，將該數據對應的節點，插入到鏈表表頭,時間復雜度為O(n)。如果緩存被占滿，則從鏈表尾部的數據開始清理，時間復雜度為O(1)。
6）數組實現LRU緩存淘汰策略
方式一：首位置保存最新訪問數據，末尾位置優先清理
當訪問的數據未存在于緩存的數組中時，直接將數據插入數組第一個元素位置，此時數組所有元素需要向后移動1個位置，時間復雜度為O(n)；當訪問的數據存在于緩存的數組中時，查找到數據并將其插入數組的第一個位置，此時亦需移動數組元素，時間復雜度為O(n)。緩存用滿時，則清理掉末尾的數據，時間復雜度為O(1)。
方式二：首位置優先清理，末尾位置保存最新訪問數據
當訪問的數據未存在于緩存的數組中時，直接將數據添加進數組作為當前最有一個元素時間復雜度為O(1)；當訪問的數據存在于緩存的數組中時，查找到數據并將其插入當前數組最后一個元素的位置，此時亦需移動數組元素，時間復雜度為O(n)。緩存用滿時，則清理掉數組首位置的元素，且剩余數組元素需整體前移一位，時間復雜度為O(n)。（優化：清理的時候可以考慮一次性清理一定數量，從而降低清理次數，提高性能。）
2.如何通過單鏈表實現“判斷某個字符串是否為水仙花字符串”？（比如 上海自來水來自海上）
1）前提：字符串以單個字符的形式存儲在單鏈表中。
2）遍歷鏈表，判斷字符個數是否為奇數，若為偶數，則不是。
3）將鏈表中的字符倒序存儲一份在另一個鏈表中。
4）同步遍歷2個鏈表，比較對應的字符是否相等，若相等，則是水仙花字串，否則，不是。
六、設計思想
時空替換思想：“用空間換時間” 與 “用時間換空間”
當內存空間充足的時候，如果我們更加追求代碼的執行速度，我們就可以選擇空間復雜度相對較高，時間復雜度小相對較低的算法和數據結構，緩存就是空間換時間的例子。如果內存比較緊缺，比如代碼跑在手機或者單片機上，這時，就要反過來用時間換空間的思路。

3、隊列

什么是隊列:

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

特點:

1 . 隊列跟棧一樣,也是一種抽象的數據結構。

2. 具有先進先出的特性,支持在隊尾插入元素,在隊頭刪除元素。

實現:

隊列可以用數組來實現,也可以用鏈表來實現。

用數組實現的隊列叫作順序隊列,用鏈表實現的隊列叫作鏈式隊列。

基于數組的隊列:

實現思路:

實現隊列需要兩個指針:一個是head指針,指向隊頭;一個是tail指針,指向隊尾。你可以結合下面這幅圖來理解。當a,b,c,d依次入隊之后,隊列中的head指針指向下標為0的位置, tail指針指向下標為4的位置。

當我們調用兩次出隊操作之后,隊列中head指針指向下標為2的位置, tail指針仍然指向下標為4的位置.

隨著不停地進行入隊、出隊操作, head和tail都會持續往后移動。當tail移 . ,動到最右邊,即使數組中還有空閑空間,也無法繼續往隊列中添加數據了。這個問題該如何解決呢?

在出隊時可以不用搬移數據。如果沒有空閑空間了,我們只需要在入隊時,再集中觸 ,發一次數據的搬移操作。

當隊列的tail指針移動到數組的最右邊后,如果有新的數據入隊,我們可以將 head到tail之間的數據,整體搬移到數組中0到tail-head的位置。

基于鏈表的實現:?

需要兩個指針: head指針和tail指針,它們分別指向鏈表的第一個結,點和最后一個結點。

如圖所示,入隊時, tail->next= new node, tail = tail->next:出隊時, head = head->next.

循環隊列:

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

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

隊列為空的判斷條件是head == tail,但隊列滿的判斷條件就稍微有點復雜了。我畫了一張隊列滿的圖,你可以看一下,試著總結一下規律,

就像我圖中畫的隊滿的情況, tail=3, head-4, n=8,所以總結一下規律就是: (3+1)%8-4,多畫幾張隊滿的圖,你就會發現,當隊滿時, (tail+1)%n=head..你有沒有發現,當隊列滿時,圖中的tail指向的位置實際上是沒有存儲數據的。所以,循環隊列會浪費一個數組的存儲空間。

解決浪費一個存儲空間的思路:定義一個記錄隊列大小的值size，當這個值與數組大小相等時，表示隊列已滿，當tail達到最底時，size不等于數組大小時，tail就指向數組第一個位置。當出隊時，size—，入隊時size++

阻塞隊列和并發隊列(應用比較廣泛)

阻塞隊列其實就是在隊列基礎上增加了阻塞操作。

簡單來說,就是在隊列為空的時候,從隊頭取數 , 據會被阻塞。因為此時還沒有數據可取,直到隊列中有了數據才能返回;如果隊列已經滿了,那么插入數據的操作就會被阻塞,直到隊列中有空閑位置后再插入數據,然后再返回。

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

小結:

隊列最大的特點就是先進先出,主要的兩個操作是入隊和出隊。

它既可以用數組來實現,也可以用鏈表來實現。用數組實現的叫順序隊列,用鏈表實現的叫鏈式隊列。

長在數組實現隊列的時候,會有數據搬移操作,要想解決數據搬移的問題,我們就,需要像環一樣的循環隊列。要想寫出沒有bug的循環隊列實現代碼,關鍵要確定好隊空和隊滿的,判定條件。

阻塞隊列、并發隊列,底層都還是隊列這種數據結構,只不過在之上附加了很多其他功能。阻塞隊列就是入隊、出隊操作可以陰寒,并發隊列就是隊列的操作多線程安全。

4、遞歸算法

一、什么是遞歸？

1.遞歸是一種非常高效、簡潔的編碼技巧，一種應用非常廣泛的算法，比如DFS深度優先搜索、前中后序二叉樹遍歷等都是使用遞歸。
2.方法或函數調用自身的方式稱為遞歸調用，調用稱為遞，返回稱為歸。
3.基本上，所有的遞歸問題都可以用遞推公式來表示，比如
f(n) = f(n-1) + 1;?
f(n) = f(n-1) + f(n-2);
f(n)=n*f(n-1);

二、為什么使用遞歸？遞歸的優缺點？

1.優點：代碼的表達力很強，寫起來簡潔。
2.缺點：空間復雜度高、有堆棧溢出風險、存在重復計算、過多的函數調用會耗時較多等問題。

三、什么樣的問題可以用遞歸解決呢？

一個問題只要同時滿足以下3個條件，就可以用遞歸來解決：
1.問題的解可以分解為幾個子問題的解。何為子問題？就是數據規模更小的問題。
2.問題與子問題，除了數據規模不同，求解思路完全一樣
3.存在遞歸終止條件

四、如何實現遞歸？

1.遞歸代碼編寫
寫遞歸代碼的關鍵就是找到如何將大問題分解為小問題的規律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼。
2.遞歸代碼理解
對于遞歸代碼，若試圖想清楚整個遞和歸的過程，實際上是進入了一個思維誤區。
那該如何理解遞歸代碼呢？如果一個問題A可以分解為若干個子問題B、C、D，你可以假設子問題B、C、D已經解決。而且，你只需要思考問題A與子問題B、C、D兩層之間的關系即可，不需要一層層往下思考子問題與子子問題，子子問題與子子子問題之間的關系。屏蔽掉遞歸細節，這樣子理解起來就簡單多了。
因此，理解遞歸代碼，就把它抽象成一個遞推公式，不用想一層層的調用關系，不要試圖用人腦去分解遞歸的每個步驟。

遞歸的關鍵是終止條件
五、遞歸常見問題及解決方案

1.警惕堆棧溢出：可以聲明一個全局變量來控制遞歸的深度，從而避免堆棧溢出。
2.警惕重復計算：通過某種數據結構來保存已經求解過的值，從而避免重復計算。

六、如何將遞歸改寫為非遞歸代碼？

籠統的講，所有的遞歸代碼都可以改寫為迭代循環的非遞歸寫法。如何做？抽象出遞推公式、初始值和邊界條件，然后用迭代循環實現。

5、排序

一、排序方法與復雜度歸類
（1）幾種最經典、最常用的排序方法：冒泡排序、插入排序、選擇排序、快速排序、歸并排序、計數排序、基數排序、桶排序。
（2）復雜度歸類
冒泡排序、插入排序、選擇排序 O(n^2)
快速排序、歸并排序 O(nlogn)
計數排序、基數排序、桶排序 O(n)

二、如何分析一個“排序算法”？
<1>算法的執行效率
1. 最好、最壞、平均情況時間復雜度。
2. 時間復雜度的系數、常數和低階。
3. 比較次數，交換（或移動）次數。
<2>排序算法的穩定性
1. 穩定性概念：如果待排序的序列中存在值相等的元素，經過排序之后，相等元素之間原有的先后順序不變。
2. 穩定性重要性：可針對對象的多種屬性進行有優先級的排序。
3. 舉例：給電商交易系統中的“訂單”排序，按照金額大小對訂單數據排序，對于相同金額的訂單以下單時間早晚排序。用穩定排序算法可簡潔地解決。先按照下單時間給訂單排序，排序完成后用穩定排序算法按照訂單金額重新排序。
<3>排序算法的內存損耗
原地排序算法：特指空間復雜度是O(1)的排序算法。

常見的排序算法:

冒泡排序

冒泡排序只會操作相鄰的兩個數據。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關系要求，如果不滿足就讓它倆互換。

代碼:

public int[] bubbleSort(int[] a) {int n = a.length;if (n<=1) {return a;}for (int i = 0; i < n; i++) {//提前退出冒泡循環的標志boolean flag = false;for (int j = 0; j < n-i-1; j++) {if (a[j]>a[j+1]) {//int temp = a[j];a[j] = a[j+1];a[j+1] = temp;flag = true;//表示有數據交換}if (!flag) {break; //沒有數據交換(說明已排好序無需再進行冒泡),提前退出}}}return a;}

四、插入排序

插入排序將數組數據分成已排序區間和未排序區間。初始已排序區間只有一個元素，即數組第一個元素。在未排序區間取出一個元素插入到已排序區間的合適位置，直到未排序區間為空。

代碼:

public int[] insertionSort(int[] a) {int n = a.length;if (n<=1) return a;for (int i = 1; i < n; i++) {int value = a[i];int j = i-1;for (; j >=0; j--) {if (a[j] > value) {a[j+1] = a[j];//移動數據}else {break;}}a[j+1] = value;//插入數據}return a;}

五、選擇排序

選擇排序將數組分成已排序區間和未排序區間。初始已排序區間為空。每次從未排序區間中選出最小的元素插入已排序區間的末尾，直到未排序區間為空。
代碼:

public int[] selectionSort(int[] a) {int n = a.length;for (int i = 0; i < a.length - 1; i++) {for (int j = i+1; j < a.length; j++) {//交換if (a[i] > a[j]) {int temp = a[i];a[i] = a[j];a[j] = temp;}}}return a;}

六、歸并排序

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

?實現思路:

merge-sort(p...r)表示,給下標從p到r之間的數組排序。我們將這個排序問題轉化為了兩個子問 ,題, merge_sort(p...q)和merge-sort(q+1..r),其中下標q等于p和r的中間位置,也就是, (p+r)/2,當下標從p到q和從q+1到r這兩個子數組都排好序之后,我們再將兩個有序的子數組合并在一起,這樣下標從p到r之間的數據就也排好序了。

代碼:

// 歸并排序算法, a是數組，n表示數組大小public static void mergeSort(int[] a, int n) {mergeSortInternally(a, 0, n-1);}// 遞歸調用函數private static void mergeSortInternally(int[] a, int p, int r) {// 遞歸終止條件if (p >= r) return;// 取p到r之間的中間位置qint q = (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);}private static void merge(int[] a, int p, int q, int r) {int i = p;int j = q+1;int k = 0; // 初始化變量i, j, kint[] tmp = new int[r-p+1]; // 申請一個大小跟a[p...r]一樣的臨時數組// 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 判斷哪個子數組中有剩余的數據int start = i;int end = q;if (j <= r) {start = j;end = r;}// 3 將剩余的數據拷貝到臨時數組tmpwhile (start <= end) {tmp[k++] = a[start++];}// 4 將tmp中的數組拷貝回a[p...r]for (i = 0; i <= r-p; ++i) {a[p+i] = tmp[i];}}

merge是這樣執行的:

代碼分析:

七、快速排序

快排的思想: ? ?如果要排序數組中下標從p到r之間的一組數據,我們選擇p到r之間的任意一個數據作為pivot (分區點) 。我們遍歷p到r之間的數據,將小于pivot的放到左邊,將大于pivot的放到右邊,將pivot放到中間。經過這一步驟之后,數組p到r之間的數據就被分成了三個部分,前面p到q-1之間都是小于pivot的,中間是pivot,后面的q+1到r之間是大于pivot的。

快排利用的分而治之的思想

八、線性排序:

時間復雜度O(n)

我們把時間復雜度是線性的排序算法叫作線性排序(Linear sort)常見的線性算法有:?桶排序、計數排序、基數排序

特點:

非基于比較的排序算法?

桶排序

桶排序,顧名思義,會用到“桶" ,核心思想是將要排序的數據分到幾個有序的桶里,每個桶里的數據再單獨進行排序。桶內排完序之后,再把每個桶里的數據按照順序依次取出,組成的序列就是有序的了。

對排序的數據要求苛刻:

1, 要排序的數據需要很容易就能劃分成m個桶,并且,桶與桶之間有著天然的大小順序。

2 ,數據在各個桶之間的分布是比較均勻的。

3 ,桶排序比較適合用在外部排序中。所謂的外部排序就是數據存儲在外部磁盤中,數據量比較大,內存有限，無法將數據全部加載到內存中。

計數排序

計數排序只能用在數據范圍不大的場景中,如果數據范圍k比要排序的數據n大很多,就不適合用計數排序了。

計數排序只能給非負整數排序,如果要排序的數據是其他類型的,要將其在不改變相對大小的情況下,轉化為非負整數。

代碼:

// 計數排序，a是數組，n是數組大小。假設數組中存儲的都是非負整數。public static void countingSort(int[] a) {int n = a.length;if (n <= 1) return;// 查找數組中數據的范圍int max = a[0];for (int i = 1; i < n; ++i) {if (max < a[i]) {max = a[i];}}// 申請一個計數數組c，下標大小[0,max]int[] c = new int[max + 1];for (int i = 0; i < max + 1; ++i) {c[i] = 0;}// 計算每個元素的個數，放入c中for (int i = 0; i < n; ++i) {c[a[i]]++;}// 依次累加for (int i = 1; i < max + 1; ++i) {c[i] = c[i-1] + c[i];}// 臨時數組r，存儲排序之后的結果int[] r = new int[n];// 計算排序的關鍵步驟了，有點難理解for (int i = n - 1; i >= 0; --i) {int index = c[a[i]]-1;r[index] = a[i];c[a[i]]--;}// 將結果拷貝會a數組for (int i = 0; i < n; ++i) {a[i] = r[i];}}

散列表

什么是散列表:

散列表用的是數組支持按照下標隨機訪問數據的特性,所以散列表其實就是數組的一種擴展,由數組演化而來。可以說,如果沒有數組,就沒有散列表。

原理:

散列表用的就是數組支持按照下標隨機訪問的時候,時間復雜度是0(1)的特性。我們通過散列函數把元素的鍵值映射為下標,然后將數據存儲在數組中對應下標的位置。當我們按照鍵值查詢元素時,我們用同樣的散列函數,將鍵值轉化數組標標,從對應的數組下標的位置取數據。

散列函數的設計要求:

散列函數計算得到的散列值是一個非負整數;.

如果key1 = key2,那hash(key1) == hash(key2);

如果key1 !=?key2,那hash(key1) ?!=??hash(key2),

散列函數的設計不能太復雜,散列函數生成值要盡可能隨機并且均勻分布

如果不符合3 那么就出現了散列沖突,散列沖突是無法避免的

解決散列沖突的方法有兩種:?

開放尋址法(open addressing)和鏈表法(chaining)

開放尋址法:如果出現了散列沖突,我們就重新探測一個空閑位置,將其插入。

裝在因子: ?散列表中一定比例的空閑槽位。公式:?散列表的裝載因子 = 填入表中的元素個數 / 散列表的長度

裝載因子越大,說明空閑位置越少,沖突越多,散列表的性能會下降。

鏈表法:

鏈表法是一種更加常用的散列沖突解決辦法,相比開放尋址法,它要簡單很多。我們來看這個圖,在散列表中,每個"桶(bucket) "或者"槽(slot) "會對應一條鏈表,所有散列值相同的元素我們都放到相同槽位對應的鏈表中。

總結

以上是生活随笔為你收集整理的数据结构与算法学习笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。