礼拜一、二翘掉，不然Hashing就看完了，唉。
有错请指教。
知道怎么写Algo，就知道怎么操作，举个例子便能知道Stability。
知道怎么写Recursive time fcn，就知道时间复杂度。
Thm:
- Binary Search
- 给定 n笔records，求 比较过程之Decision Tree决策树
- 给定 n笔records，求 最多比较次数
Decision Tree高度，即高度最小化的BT
- 给定 要找的数，求 比较次数
- 用Decision Tree来描述sorting(采用comparison-based skill)之比较过程
Decision Tree是BT，non-leaf是比较node，leaf是排序结果
- 给定 n笔records，求 最多比较次数
Ω(n*log n)，即 Decision Tree高度-1 >= ([log n!]+1)-1 ≒ n*log n
- Selection Problem
- Find min & max 找min & max
T(n) = 3n/2
用递回，n笔需要，2笔比1次决定大小，n-2笔找好大小的分别跟2笔大小再比1次，
算recursion time fcn
- Select ith smallest item among unsorted n data n个找第i小资料
用quick sort，只要找一边。
- avg, best O(n)
- worst O(n^2)，可用middle of three or medium of mediums选pk改善
假设k为偶数(k为奇数要微调)
T(n) = O(n) + O(n) + T(n/k) + O(n) + T(3n/4+k)
k >= 5 O(n)，k < 5 O(n*log n)
1. 每k个组一group，将n个data切成n/k个group，
除一个可能不足每个group有k个data O(n)
2. 每个group各自排序(n/k)*O(k^2) = O(k*n) = O(n)
3. 每个group第k/2个data是该group之median，共n/k个median，
递回找出n/k个medians之median(n/k个找第n/2k个小资料)作为pk T(n/k)
4. 用q=Partition(A,p,r)在A[p],A[r]间把pk放到正确位置A[q]，O(n)
5. i=pk直接回传，i比pk小 select(A,p,q-1,i)，i比pk大 select(A,q+1,r,i-k)
(至少有一半的groups(1/2)*(n/k)-1 pk所在的group -1 不足k个data的group)
*(k/2)
= n/4-k 个比pk大的data
所以有3n/4+k个比pk小的data
最差花T(3n/4+k)，要从3n/4+k个找第i小的资料
Search Algo:
- Linear Search (iterative)
- with sentinel哨兵
Array or Link list(Data movement较Array少)
O(n)，(1+...+n)/n = (n+1)/2
- Binary Search (iterative or recursive)
Data Comparison较Linear Search少
divide and conquer, prune and search
Array
O(log n)
Sort Algo:
初等
- Insertion Sort (插入前面排好的，顺便排)
适合资料量少(Internal Sort)
Stable
Sorting in-place
time(comparison) avg O(n^2) ~ O(n)
space O(1)，r, A[0]=-∞
- Binary Insertion Sort
time(comparison, movement) O(n^2)
- Linear Insertion Sort
time(comparison, movement) O(n^2)
- Selection Sort (右边剩下，找最小交换至左)
适合大型纪录(一笔纪录由很多字段组成)，因为每一回合顶多SWAP一次
Unstable
Sorting in-place
可以用或不用if(检查是否是min，来决定是否用SWAP)
time O(n^2)
space O(1)，min, temp in SWAP fcn
- Bubble Sort (由左而右两两交换，最大升最高 or 由右而左两两交换，最小降最低)
Stable
Sorting in-place
time avg O(n^2) ~ O(n)
space O(1)，flag(检查有无SWAP), temp in SWAP fcn
- Shell Sort (n/2^k型 或 2^k-1型 或 自订型)
Unstable
Sorting in-place
time avg O(n^2) ~ 一般O(n^(3/2))
space O(1)，flag, temp in SWAP fcn