• 快速union要畫分支圖合并

• 快速find要列表找到代替的點

• 希爾排序knuth序列是 13-4-1，sedewick序列是（1，5，19，41）,橫向長度=h（13-->4->1),然后縱向?qū)τ诿恳涣胁迦肱判颉?/p>

• 計數(shù)排序的計數(shù)數(shù)組中的每一個數(shù)都是加上之前的數(shù)就是位置數(shù)組

• merge-sort就是分裂成每個元素再按照大小合并

• 快速排序找到一個pivot然后從左右找依次比pivot小的數(shù)和大的數(shù)排序，遞歸這個步驟

• 復(fù)雜度展開要展開遞歸方程找規(guī)律

• huffman代碼是貪心算法，每次都找最小的合并，畫出二叉樹，左0右1，每一個子葉是字母

• pre-order是先根再左右子樹，

• in-order是先遍歷先左子樹再根再右子樹

• post-order是先左右子樹最后根

• 最少需要preorder和inorder才能找到原BST，最后用post-order驗證

• BST從葉插入左小右大，刪除節(jié)點要找到前序或者后繼

• BST從根部插入要旋轉(zhuǎn)，插入的反方向旋轉(zhuǎn)，向R/L旋轉(zhuǎn)就把子樹的R/L換成父樹的L/R

• interval-BSt從葉插入左小右大，標(biāo)明子樹的最大值

• interval-bst尋找，哪邊的max大于[a,b]中的a就向哪邊遞歸

• 一次hash如果collision就+1

         ***平方hash***
         第幾次collision就（j+i^2)mod k，j是第一次collision的值
         ***二次hash ***
        h1=k mod 19
        h2=1+k mod 97 
         h(k)=((k mod 19)+(1+k mod 97))mod 19 注意這里沒有乘以collision的次數(shù)
             比如(45%19+1+45%97)%19=  15
                 collision!
                 (15%19+1+45%97)%19=4 ok
  

• heapsort每次都要保證最大堆，按順序插入，先左后右
  priority queen刪除最大的節(jié)點要先把最大的節(jié)點和最小的額節(jié)點交換后刪除，然后再進(jìn)行最大堆整理

• DFS按照字母表順序深入搜索，遞歸時返回的每一步都檢查是否有新的路線
  被指向的和指出的(A,B)比：

  / |A | B
  ----|----|----
  T | > | < |
  B | < | >|
  F | > | > |
  C | < | < |

圖算法：

• acyslic無環(huán)意思就是DFS沒有B標(biāo)記

最短路徑算法

• Dijkstra是每次都找權(quán)重最小的邊松弛，直到所有定點都被松弛
• bellman是對每條邊松弛知道不再變化

最小生成樹算法

• prim算法是劃線每次都找最短的
• kruskal是找出所有最短的邊，直到再找一個就會連成環(huán)

• Kosaraju強(qiáng)連通分量，畫一個反向圖進(jìn)行DFS得出（discover，endprocessing），在原圖根據(jù)endpro遞減順序來進(jìn)行DFS，每一塊DFS開始都是一個SCC

對于DAG的拓?fù)渑判?/h4>

1. 從 DAG 圖中選擇一個 沒有前驅(qū)（即入度為0）的頂點并輸出。
2. 從圖中刪除該頂點和所有以它為起點的有向邊。

重復(fù) 1 和 2 直到當(dāng)前的 DAG 圖為空或當(dāng)前圖中不存在無前驅(qū)的頂點為止。后一種情況說明有向圖中必然存在環(huán)。