排序

• 空間複雜度
  • 最基本是O(N^2)
  • best case是O(N)
  • average case是O(N log N)

1. quick sort
   • 每輪sort O(N) 總共log N輪
   • 找到pivot值，依大小丟到其左右邊
     • 注意丟的方法 2ptr
       • 左ptr指的是所有比pivot小的數組中最右邊的（最新被丟過來的）
       • 右ptr指的是還沒被分類的
       • 左-右中間是比pivot還大的數組
     • 如果有新的比pivot小的值，則把左ptr右邊一個位置與右ptr交換，然後左ptr++
   • 子數組重複動作直到
2. merge sort
   • 先一直把數組兩等分⇒子數組再兩等份...
   • 再慢慢合併
   • 合併時使用插入排序法
3. heap sort
   • build heap O(N/2 * constant) + heap sort O(N log N)
     • sort：N個數，每次heapify都logN ⇒ N log N
   • binary heap
     • complete binary tree
       • 大部分index從1開始
       • left child = 2*root index
       • right child = 2*root index + 1
     • max heap (or min heap)
       • root > left and root > right
     • heapify
       • 要root, left, right要找到最大值
       • 由上而下比較的過程，若有當前root不符合規定的，則與left, right中最大的節點交換，然後繼續往子節點去
   • sort
     1. get max heap tree
     2. root 與最後一個節點交換，並把最後一個節點的index排除（已經是最大值，沒問題，無需再排序）
     3. 當前的root作heapify
     4. 新的root重複2. 3.

搜尋

• 空間複雜度
  • 基本case是O(N)線性搜索
  • 最快是O(log N) 一直縮小一半的搜索空間
• 必須要數組先排序好

1. linear search
2. binary search
3. exponential search
4. interpolation search
5. fibonacci search