Insertion sort(直接插入排序)
pseudocode:
insertion sort （a，n)
for j = 2 to n
key = a[j]
i = j -1
while i>0 && a[i] >key
a[i+i] = a[i]
i = i-1
a[i+1] = key
关于o 标记法
数学上： o(g(n)) = {f(n): 存在正常数c1,c2,n0使得对于所有的n>=n0 都有 0<=c1*g(n)<=f(n)<=c2*g(n) }
工程学上： 削减低阶元素；忽略系数
例如： 3N^3 + 90n^2 - 5n +100 = o(n^3)
最坏时间复杂度：最坏情况下，对于每个j都需要排j次: t(n)=∑o(j) =o(n^2)
平均时间复杂度： t(n)=∑o(j/2) =o(n^2)
Merge srot (归并排序）
pseudocode
merge sort a(1,....,n)
if n = 1 ,done
recursively sort a(1,n/2)and a(n/2+1,n)
merge the two sort list
归并排序的时间复杂度分析首先，先针对每一步进行单独分析:
if n = 1 ,done o(1)
recursively sort a(1,n/2)and a(n/2+1,n) 2T(n/2)
merge the two sort list o(n)
于是归并排序的时间复杂度为：T(n) = o(1) + 2T(n/2) + o(n)
忽略o(1), 因此归并排序的时间复杂度现在转化为 求解： T(n)= 2T(n/2) + c*n 要求c>0
转化为地归树为
cn
/ \
T(n/2) T(n/2)
进一步
cn
/ \
cn/2 cn/2
/ \ / \
T(n/4) T(n/4) T(n/4) T(n/4)
最终
cn
/ \
cn/2 cn/2 树的深度为lgn
/ \ / \
cn/4 cn/4 cn/4 cn/4
.... .... ... ....
o(1) 共有n个叶子节点，因此 对于叶子节点来说时间复杂度为o(n)
在求最坏时间复杂度时，将树的每一层近似的看成与叶子节点的时间复杂度相同，因此求解归并排序的时间复杂度为 o(nlgn) | 
转播
