通過(guò)提升速度來(lái)解決其他方式無(wú)法解決的問(wèn)題，是研究算法的設(shè)計(jì)和性能的主要原因之一。結(jié)合python代碼看，容易理解。
研究新問(wèn)題時(shí)，最好的方法是先實(shí)現(xiàn)一個(gè)能想到的最簡(jiǎn)單程序，當(dāng)它成為瓶頸時(shí)再繼續(xù)改進(jìn)它。
1 排序
考慮：比較次數(shù)、交換次數(shù)；
排序的主要原因：在有序的數(shù)組中查找一個(gè)元素比在無(wú)序的數(shù)組中查找簡(jiǎn)單的多。通用排序算法是最重要的。
電話黃頁(yè)按姓氏排序；歌曲按作家名或歌曲名排序；搜索引擎按搜索結(jié)果的重要性排序；矩陣工具按對(duì)稱矩陣的真實(shí)特征值排序。只要數(shù)組是有序的，很多其他任務(wù)也更容易完成。
1）選擇排序
不斷地選擇剩余元素之中的最小者
2）插入排序
保持當(dāng)前索引左邊的所有元素都是有序的，適用于部分有序的數(shù)組
改進(jìn)：在內(nèi)循環(huán)中將較大的元素都向右移動(dòng)，而不總是交換兩個(gè)元素？
3）希爾排序
基于插入排序，使數(shù)組中任意間隔為h的元素都是有序的
shell sort，權(quán)衡了子數(shù)組的規(guī)模和有序性；子數(shù)組部分有序的程度取決于遞增序列的選擇，透徹理解希爾排序的性能至今仍是挑戰(zhàn)。對(duì)于給定的遞增序列，運(yùn)行時(shí)間達(dá)不到平方級(jí)別，比插入和選擇排序要快的多，并且數(shù)組越大優(yōu)勢(shì)越大。
4）歸并排序
以索引來(lái)切分，遞歸地將數(shù)組分成兩半來(lái)排序，然后將結(jié)果歸并起來(lái)；缺點(diǎn)是所需的額外空間和數(shù)組長(zhǎng)度成正比
歸并排序是一種漸進(jìn)最優(yōu)的基于比較排序的算法。持續(xù)改進(jìn)：小規(guī)模子數(shù)組切換到插入排序；測(cè)試數(shù)組是否已經(jīng)有序；不將元素復(fù)制到輔助數(shù)組。
由頂向下實(shí)現(xiàn)：1.分成兩邊，挨個(gè)遍歷、比較，放入輔助數(shù)組；2.有一邊已經(jīng)遍歷完，那么剩下的都放入輔助數(shù)組。
5）快速排序
以數(shù)組內(nèi)容來(lái)切分，將數(shù)組分成兩部分，將兩部分獨(dú)立排序，遞歸地調(diào)用；優(yōu)點(diǎn)是原地排序，對(duì)歸并排序的補(bǔ)充
優(yōu)勢(shì)：內(nèi)循環(huán)簡(jiǎn)潔，將數(shù)組元素與定值比較；比較次數(shù)少，平均而言切分元素都能落在數(shù)組的中間。持續(xù)改進(jìn)：小規(guī)模子數(shù)組切換到插入排序；三取樣切分；熵最優(yōu)的排序，比如包含大量重復(fù)元素。
二叉排序樹：其左子樹小于根結(jié)點(diǎn)的值，右子樹大于根結(jié)點(diǎn)的值，思路就是特殊的快速排序；中序遍歷，左子樹、根結(jié)點(diǎn)、右子樹；前序遍歷，根結(jié)點(diǎn)、左子樹、右子樹；后序遍歷，左子樹、右子樹、根結(jié)點(diǎn)。
排序遞歸、遍歷遞歸！不管怎樣都是從根節(jié)點(diǎn)開始！
6）堆排序
兩個(gè)階段：1.構(gòu)造堆，線性時(shí)間；2.在下沉排序階段，迭代地“刪除最小元素”，得到排序結(jié)果
優(yōu)先隊(duì)列、最大堆：其子結(jié)點(diǎn)全都小于根結(jié)點(diǎn)
對(duì)數(shù)組進(jìn)行原地排序，不需要額外空間。
2 查找
存儲(chǔ)鍵值對(duì)，支持兩種操作：查找get和插入put；需要實(shí)現(xiàn)高效的符號(hào)表（字典）。
提供接口：void put/Value get/void delete/boolean contains/boolean isEmpty/int size/Iterable keys
除了順序查找外，都是先按某種方法排序，再使用相應(yīng)的規(guī)則查找。最常見：二分查找。
1）二叉查找樹
最大/小鍵max/min；向上/下取整ceiling/floor；數(shù)量size；查找select；排名rank；刪除delete（最難）/遍歷keys
在二叉查找樹中，所有操作在最壞情況下所需的時(shí)間都和樹的高度成正比；
隨機(jī)鍵構(gòu)造的二叉查找樹的平均高度為lgN；基于二叉查找樹的符號(hào)表。
2）紅黑樹
2-3查找樹：一個(gè)結(jié)點(diǎn)保存多個(gè)鍵；查找和插入訪問(wèn)的結(jié)點(diǎn)必然不超過(guò)lgN個(gè)。
紅黑樹（平衡二叉查找樹）：紅鏈接將兩個(gè)2-結(jié)點(diǎn)連起來(lái)構(gòu)成一個(gè)3-結(jié)點(diǎn)，黑鏈接是2-3樹中的普通鏈接。
3）散列表
用算術(shù)操作將鍵轉(zhuǎn)化為數(shù)組的索引，來(lái)訪問(wèn)數(shù)組中的鍵值對(duì)。在時(shí)間和空間上找到了權(quán)衡，不限制內(nèi)存的話，直接將鍵作為數(shù)組的索引；不限制時(shí)間的話，使用無(wú)序數(shù)組進(jìn)行順序查找；而且不必重寫代碼，調(diào)整散列算法的參數(shù)就可以在時(shí)間和空間上做出取舍。
散列函數(shù)：將被查找的鍵轉(zhuǎn)化為數(shù)組的索引。最好滿足三個(gè)條件：一致性，等價(jià)的鍵產(chǎn)生相等的值；高效性，計(jì)算簡(jiǎn)便；均勻性，均勻地散列所有鍵。
處理碰撞沖突：當(dāng)兩個(gè)或多個(gè)鍵都散列到相同索引值的情況。拉鏈法，使用鏈表的每個(gè)結(jié)點(diǎn)存儲(chǔ)散列值為該元素的索引的鍵值對(duì)，首先根據(jù)散列值找到對(duì)應(yīng)的鏈表，然后沿著鏈表順序查找對(duì)應(yīng)的鍵。
3 圖
圖算法Graph：沿著連接能否從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)？有多少結(jié)點(diǎn)和指定的結(jié)點(diǎn)相連？?jī)蓚€(gè)結(jié)點(diǎn)間最短的連接是哪一條？
廣泛應(yīng)用：1）地圖，最短路徑；2）網(wǎng)頁(yè)信息，頁(yè)面、超鏈接、搜索引擎；3）任務(wù)調(diào)度，任務(wù)、限制條件；4）商業(yè)交易，客戶、交易；5）社交，人、朋友關(guān)系；6）軟件，類和模塊、調(diào)用關(guān)系
1）無(wú)向圖
路徑，u-v-w-x；環(huán)，u-v-w-x-u
查找頂點(diǎn)Search(Graph G, int s):boolean marked(int v)/int count()
查找路徑Paths(Graph G, int s):boolean hasPathTo(int v)/Iterable pathTo(int v)
連通分量CC(Graph G):boolean connected(int v, int w)/int count()/int id(int v)
深度優(yōu)先搜索：遞歸遍歷所有頂點(diǎn)；將頂點(diǎn)標(biāo)記為“已訪問(wèn)”，然后訪問(wèn)它的所有未被標(biāo)記過(guò)的鄰接點(diǎn)；結(jié)果是數(shù)組，所需的時(shí)間和路徑的長(zhǎng)度成正比。
廣度優(yōu)先搜索：找出單點(diǎn)最短路徑，顯式地使用隊(duì)列，以保存所有已經(jīng)被標(biāo)記過(guò)，但其鄰接表還未被檢查過(guò)的頂點(diǎn)；將頂點(diǎn)標(biāo)記為“已訪問(wèn)”，然后將它的所有未被標(biāo)記過(guò)的鄰接點(diǎn)加入隊(duì)列；結(jié)果是數(shù)組，表示s到每個(gè)與s連通的頂點(diǎn)的最短路徑，所需的時(shí)間在最壞情況下和V+E成正比。
