算法+數(shù)據(jù)結(jié)構(gòu)=程序，今天就來說說遞歸+排序+查找，再加上樹與圖

著名數(shù)據(jù)專家沃斯曾說：算法+數(shù)據(jù)結(jié)構(gòu)=程序

上次講了數(shù)據(jù)結(jié)構(gòu)

這回就講講算法

復雜度

復雜度分析，是貫徹數(shù)據(jù)結(jié)構(gòu)和算法中的一項基礎(chǔ)技能，學習數(shù)據(jù)結(jié)構(gòu)和算法的目的，無非就是要寫出占用空間更小、運行時間更短的代碼。

時間復雜度

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

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

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

   image.png

多項式量級：

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

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

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

1. 加法法則和乘法法則

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

1. 平均時間復雜度：

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

1. 均攤時間復雜度

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

算法

1. 遞歸

可以用遞歸的條件：

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

寫遞歸算法的思路：

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

遞歸代碼的弊端：

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

2. 排序

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

1. 執(zhí)行效率

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

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

按時間復雜度分類：

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

2.1 冒泡排序

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

image.png

image.png

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

2.2 插入排序

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

image.png

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

2.3 選擇排序

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

image.png

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

2.4 歸并排序

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

image.png

• 非原地排序，空間復雜度為O(n)
• 穩(wě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

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

2.6 桶排序

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

image.png

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

苛刻的條件：

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

2.7 計數(shù)排序

計數(shù)排序其實是桶排序的一種特殊情況： 數(shù)據(jù)的訪問很?。ɡ缒挲g、考生的成績），桶的數(shù)量是有限的。 以給高考考生成績進行排名為例，考生的滿分是 900 分，最小是 0 分，對應(yīng)901個桶，把全國的考生放入這901個桶，桶內(nèi)的數(shù)據(jù)都是分數(shù)相同的考生，所以并不需要再進行排序。

特殊要求：

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

2.8 基數(shù)排序

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

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

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

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

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

image.png

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

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

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

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

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

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

3. 查找

3.1 二分查找法

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

樹與圖

樹與圖.png

最后

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