數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)（青島大學(xué)-王卓）
Dijistra算法（最短路徑）
- 初始化
- 選擇
- 更新
- 頂點(diǎn)進(jìn)入S集合，T集合中移除
折半查找
適用于有序表
分塊查找
①建立索引表，分塊記錄每一塊的最大值
②在索引表中查找，確定是在哪一塊
③塊內(nèi)進(jìn)行順序查找
平均查找長(zhǎng)度：ASL=Lb+Lw（索引表+塊內(nèi)）
Lb = log2(n+1)（n：s總元素/每一塊的元素 = 塊）
Lw = (s/2)（s：總元素）
樹表的查找
二叉排序樹
左子樹小于根、右子樹大于等于根
中序遍歷是遞增有序的序列
遞歸查找
最多比較次數(shù)：數(shù)的深度
平均查找長(zhǎng)度：和數(shù)的形態(tài)有關(guān)，O(log2n)
二叉排序樹插入：都在葉結(jié)點(diǎn)上，修改指針，不需要移動(dòng)元素
二叉排序樹生成：依次插入，重復(fù)元素不插入
輸入序列不同，生成的二叉樹不一樣，查找效率也不一樣
二叉排序樹刪除：
- 刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)：直接刪掉就行
- 刪除的結(jié)點(diǎn)是根結(jié)點(diǎn)：如果只存在左孩子或者右孩子，就用孩子替換它；
- 刪除的結(jié)點(diǎn)有兩個(gè)孩子的結(jié)點(diǎn)：
- 右子樹中的最小的結(jié)點(diǎn)代替這個(gè)被刪的結(jié)點(diǎn)，將右子樹中最小的結(jié)點(diǎn)刪除；
- 左子樹中找到最大的結(jié)點(diǎn)，并刪除這個(gè)結(jié)點(diǎn)，將這個(gè)結(jié)點(diǎn)的值放在被刪的結(jié)點(diǎn)里面
平衡二叉樹（AVL）
平衡因子：左子樹與右子樹的高度差
BF = 結(jié)點(diǎn)左子樹的高度 - 結(jié)點(diǎn)右子樹的高度
BF = -1、0、1（就是平衡二叉樹）
失衡二叉樹的分析與調(diào)整（四種類型）
LL型、LR型、RL型、RR型
①降低樹的高度
②保持二叉排序樹的性質(zhì)（左<根<右）
- LL型
- B結(jié)點(diǎn)帶左子樹C一起上升
- A結(jié)點(diǎn)成為B的右孩子
- 原來的B結(jié)點(diǎn)的右子樹作為A的左子樹
散列表
基本思想：記錄的存儲(chǔ)位置與關(guān)鍵字之間存在的對(duì)應(yīng)關(guān)系
hash函數(shù)
看下面這個(gè)散列表：
根據(jù)散列函數(shù)來查找：H(key) = k
優(yōu)點(diǎn)：查找效率高
缺點(diǎn)：空間效率低
例如：H(k) = k mod n（n：元素個(gè)數(shù)+1）
沖突：k1≠k2 但是H(k2)=H(k2)
減少?zèng)_突：優(yōu)化散列函數(shù)
散列函數(shù)的構(gòu)造方法需要考慮的問題：
- 執(zhí)行速度
- 關(guān)鍵字的長(zhǎng)度
- 散列表的大小
- 關(guān)鍵字的分布情況
- 查找頻率
直接定值法：關(guān)鍵字構(gòu)成某種線性函數(shù)
解決沖突：如果找到的地址已經(jīng)存儲(chǔ)了值了，就移動(dòng)到下一個(gè)地址
解決沖突的方法：
除留余數(shù)法：Hi = (Hash(key)+di) mod m（di為增量序列）
- 線性探測(cè)法：di為1，2，...m-1
- 二次探測(cè)法：di為1^2，-1^2，2^2，-2^2，...，q^2
- 偽隨機(jī)探測(cè)法：di為偽隨機(jī)數(shù)序列
例如：{47,7,29,11,16,92,22,8,3}【線性探測(cè)法】
m=11 散列函數(shù)為：Hash(key) = key mod 11
鏈地址法：余數(shù)相同的鏈接在一個(gè)單鏈表上（頭插法）
例如：{19,14,23,1,68,20,84,27,55,11,10,79}
優(yōu)點(diǎn)：非同義詞不會(huì)沖突，無聚集現(xiàn)象；適用表長(zhǎng)不確定。
散列表的查找ASL：每個(gè)元素查找的次數(shù)之和 / 元素總個(gè)數(shù)
排序
排序方法的分類
- 存儲(chǔ)介質(zhì)：內(nèi)部排序（內(nèi)存）、外部排序（內(nèi)+外）
- 比較器個(gè)數(shù)：串行排序（單處理）、并行排序（多）
- 主要操作：比較排序（插入、交換、選擇、歸并）、基數(shù)排序
- 輔助空間：原地排序（不需要額外的空間）、非原地排序（需要輔助空間）
- 穩(wěn)定性：穩(wěn)定排序（直接插入排序，相等元素排序后不變）、非穩(wěn)定排序（簡(jiǎn)單選擇排序，相等元素排序后改變）
- 自然性：自然排序（有序快）、非自然排序（有序慢）
按排序依據(jù)原則
- 插入排序：直接插入排序(順序)、折半插入排序(二分)、希爾排序(縮小增量)
- 交換排序：冒泡排序、快速排序
- 選擇排序：簡(jiǎn)單選擇排序、堆排序
- 歸并排序：2-路歸并排序
- 基數(shù)排序
排序算法的好壞
- 時(shí)間效率
- 空間效率
- 穩(wěn)定性
插入排序
插入排序：在有序序列中插入一個(gè)元素，保持序列有序
1.直接插入排序：順序查找插入的位置，還可以使用哨兵模式
算法效率：比較+移動(dòng)
2. 二分插入排序：查找插入位置時(shí)采用折半查找法，使用哨兵。
3. 希爾排序：分割若干個(gè)子序列，分別進(jìn)行直接插入排序；定義遞減的增量序列，比如5、3、1，最后一個(gè)增量必須為1
交換排序
交換排序：兩兩比較，如果發(fā)生逆序就交換
1.冒泡排序：每一趟不斷將記錄兩兩比較，并按“前小后大”規(guī)則交換
2.快速排序：任取一個(gè)元素為中心，所有比它小的元素一律前放，比它大的元素一律后放，形成左右子表（交替式逼近法，遞歸）；
選擇排序
1.簡(jiǎn)單選擇排序：在等待排序的數(shù)據(jù)中選出最大(小)的元素放在其最終位置。
例如：直接選出最小的 放在第一個(gè)位置
2.堆排序：
小根堆：根都小于等于左右結(jié)點(diǎn)
大根堆：根都大于等于左右結(jié)點(diǎn)
完全二叉樹的非葉子結(jié)點(diǎn)（位置i）：i > n/2
無序序列建立成一個(gè)堆： 將元素直接排成堆 然后再調(diào)整
歸并排序
歸并排序：將兩個(gè)或者兩個(gè)以上的有序序列“歸并”為一個(gè)有序序列。
1.二路歸并排序
排序完成需要log2n次。
基數(shù)排序
1. 基數(shù)排序：分配+收集
排序總結(jié)
