算法+數據結構=程序，今天就來說說遞歸+排序+查找，再加上樹與圖

著名數據專家沃斯曾說：算法+數據結構=程序

上次講了數據結構

這回就講講算法

復雜度

復雜度分析，是貫徹數據結構和算法中的一項基礎技能，學習數據結構和算法的目的，無非就是要寫出占用空間更小、運行時間更短的代碼。

時間復雜度

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

• 表示代碼執行時間隨數據規模增長的 變化趨勢（注意只是表示「變化趨勢」）
• 由于只是表示變化趨勢，一般計算復雜度時，會忽略低階、常量、系數

1. 幾種常見的時間復雜度量級：
   
   

   image.png

多項式量級：

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

非多項式量級：(n越多，執行時間急劇上升，性能低)

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

1. 加法法則和乘法法則

• 加法法則：總復雜度等于量級最大的那段代碼的復雜度
• 乘法法則：嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積

1. 平均時間復雜度：

• 也叫加權平均時間復雜度或者期望時間復雜度。
• 要會計算：最好、最壞、平均時間

1. 均攤時間復雜度

• 特殊的平均時間復雜度
• 相當于算法有規律可循，計算時間時，可以把一次耗時多的操縱的時間，均攤給多次耗時少的操縱。

算法

1. 遞歸

可以用遞歸的條件：

1. 一個問題的解可以分解為幾個子問題的解
2. 這個問題與分解之后的子問題，除了數據規模不同，求解思路完全一樣
3. 存在遞歸終止條件

寫遞歸算法的思路：

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

遞歸代碼的弊端：

1. 堆棧溢出
2. 可能會重復計算
3. 函數調用耗時多
4. 空間復雜度高

2. 排序

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

1. 執行效率

• 最好時間復雜度
• 最壞時間復雜度
• 平均時間復雜度
• 時間復雜度的系數、常數 、低階（因為排序的數據規模一般不會非常大）
• 比較、交換的次數

1. 額外內存消耗（內存消耗為O(1)的稱為原地排序）
2. 穩定性，是否是穩定排序（即如果待排序的序列中存在值相等的元素，經過排序之后，相等元素之間原有的先后順序不變）

按時間復雜度分類：

1. O(n2)： 冒泡排序、插入排序、選擇排序
2. O(nlogn)：歸并排序、快速排序
3. O(n) ：桶排序、計數排序、基數排序 （條件苛刻，適用于部分場景）

2.1 冒泡排序

原理： 從下往上，逐次比較兩個相鄰的數據，如果下面的數據比上面的數據大，則把這兩個數據的位置互換。

image.png

image.png

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

2.2 插入排序

原理： 分為已排區域和未排區域，每次拿未排區域中的第一個數，插入到已排區域中正確的位置。

image.png

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

2.3 選擇排序

原理： 分為已排區域和未排區域，每次從未排區域中選取最小的數，放到已排區域的最后面。

image.png

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

2.4 歸并排序

原理： 歸并排序的核心思想還是蠻簡單的。如果要排序一個數組，我們先把數組從中間分成前后兩部分，然后對前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個數組就都有序了。

image.png

• 非原地排序，空間復雜度為O(n)
• 穩定排序
• 利用分治遞歸思想
• 遞推公式：  merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
• 最好、最壞、平均時間復雜度都是 O(nlogn)
  
  

  image.png

2.5 快速排序

image.png

image.png

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

2.6 桶排序

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

image.png

桶排序的時間復雜度為什么是 O(n) 呢？我們一塊兒來分析一下。如果要排序的數據有 n 個，我們把它們均勻地劃分到 m 個桶內，每個桶里就有 k=n/m 個元素。每個桶內部使用快速排序，時間復雜度為 O(k * logk)。m 個桶排序的時間復雜度就是 O(m * k * logk)，因為 k=n/m，所以整個桶排序的時間復雜度就是 O(n*log(n/m))。當桶的個數 m 接近數據個數 n 時，log(n/m) 就是一個非常小的常量，這個時候桶排序的時間復雜度接近 O(n)。

苛刻的條件：

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

2.7 計數排序

計數排序其實是桶排序的一種特殊情況： 數據的訪問很小（例如年齡、考生的成績），桶的數量是有限的。 以給高考考生成績進行排名為例，考生的滿分是 900 分，最小是 0 分，對應901個桶，把全國的考生放入這901個桶，桶內的數據都是分數相同的考生，所以并不需要再進行排序。

特殊要求：

1. 只能用在數據范圍不大的場景中，如果數據范圍 k 比要排序的數據 n 大很多，就不適合用計數排序了
2. 計數排序只能給非負整數排序，如果要排序的數據是其他類型的，要將其在不改變相對大小的情況下，轉化為非負整數。如果要排序的數據中有負數，數據的范圍是 [-1000, 1000]，那我們就需要先對每個數據都加 1000，轉化成非負整數。如果考生成績精確到小數后一位，我們就需要將所有的分數都先乘以 10，轉化成整數。

2.8 基數排序

我們再來看這樣一個排序問題。假設我們有 10 萬個手機號碼，希望將這 10 萬個手機號碼從小到大排序，你有什么比較快速的排序方法呢？

我們之前講的快排，時間復雜度可以做到 O(nlogn)，還有更高效的排序算法嗎？桶排序、計數排序能派上用場嗎？手機號碼有 11 位，范圍太大，顯然不適合用這兩種排序算法。針對這個排序問題，有沒有時間復雜度是 O(n) 的算法呢？現在我就來介紹一種新的排序算法，基數排序。

剛剛這個問題里有這樣的規律：假設要比較兩個手機號碼 a，b 的大小，如果在前面幾位中，a 手機號碼已經比 b 手機號碼大了，那后面的幾位就不用看了。

借助穩定排序算法，這里有一個巧妙的實現思路。還記得我們第 11 節中，在闡述排序算法的穩定性的時候舉的訂單的例子嗎？我們這里也可以借助相同的處理思路，先按照最后一位來排序手機號碼，然后，再按照倒數第二位重新排序，以此類推，最后按照第一位重新排序。經過 11 次排序之后，手機號碼就都有序了。

手機號碼稍微有點長，畫圖比較不容易看清楚，我用字符串排序的例子，畫了一張基數排序的過程分解圖，你可以看下。

image.png

注意，這里按照每位來排序的排序算法要是穩定的，否則這個實現思路就是不正確的。因為如果是非穩定排序算法，那最后一次排序只會考慮最高位的大小順序，完全不管其他位的大小關系，那么低位的排序就完全沒有意義了。

根據每一位來排序，我們可以用剛講過的桶排序或者計數排序，它們的時間復雜度可以做到 O(n)。如果要排序的數據有 k 位，那我們就需要 k 次桶排序或者計數排序，總的時間復雜度是 O(k*n)。當 k 不大的時候，比如手機號碼排序的例子，k 最大就是 11，所以基數排序的時間復雜度就近似于 O(n)。

實際上，有時候要排序的數據并不都是等長的，比如我們排序牛津字典中的 20 萬個英文單詞，最短的只有 1 個字母，最長的我特意去 查了下，有 45 個字母，中文翻譯是塵肺病。對于這種不等長的數據，基數排序還適用嗎？

實際上，我們可以把所有的單詞補齊到相同長度，位數不夠的可以在后面補“0”，因為根據ASCII 值，所有字母都大于“0”，所以補“0”不會影響到原有的大小順序。這樣就可以繼續用基數排序了。

我來總結一下，基數排序對要排序的數據是有要求的：

1. 需要可以分割出獨立的“位”來比較，而且位之間有遞進的關系，如果 a 數據的高位比 b 數據大，那剩下的低位就不用比較了
2. 除此之外，每一位的數據范圍不能太大，要可以用線性排序算法來排序，否則，基數排序的時間復雜度就無法做到 O(n) 了。

3. 查找

3.1 二分查找法

1. 依賴于數組結構（數據量太大不適合用二分查找法，數據需要連續的存儲空間）
2. 數據必須是排好序的
3. 時間復雜度：O(logn)

樹與圖

樹與圖.png

最后

學習視頻內容可以看這里： https://zhuanlan.zhihu.com/p/96231226