第二章算法入门学习新得
2.1 插入排序
插入排序算法流程
INSECTION SORT（A）
1 for j = 2 to length[A]
2 do key = A[j]
3 Insert A[j] into the sortedsequence A[1…j-1]
4 i= j-1
5 while i > 0 and A[i] > key
6 do A[i+1] = A[i]
7 i= i-1
8 A[i+1]= key
算法思想：将待排序数组A分为有序区与无序区，初始有序区只有第一元素（故j = 2）,将有序区不断增长而无序区不断减短（每次变化一个元素）。有序区增长与无序区减短通过查找无序区中第一个元素在有序区的位置，进行插入来完成。
算法复杂度：一般考虑最坏情况，即输入逆序情况下，每次查找都需要查找有序区所有元素，通过等差数列求和可以知道时间复杂度为O（n2），额外空间仅第2步需要一个key来存储待插入元素。
2.2 分治法
算法思想：分治法是将同一问题划分为同样或相似的子问题，只要划分使问题规模不断变小，最终会划分成多个常数时间可以解决的基本子问题。将基本子问题解决，再不断合并组成更大的子问题从而最终得到原问题的解。
这里有2点我认为比较重要，一是要理解算法的思路，二是划分必须使问题规模不断变小从而得到最小规模问题（基本子问题是函数的出口）。
合并排序：将数组分为前后两段，如果前面一段和后面一段都是已排序的，并且我们能通过一个合并算法得到完整的排序数组就解决了数组的排序。将整个数组多次二分（logN次），每个子数组都只有一个元素，此时初始情况每个数组都是排序的。将两个数组合并即得到规模为2的数组，最终得到规模为N的原数组。
合并的算法MERGE（A, p, q ,r）
1. n1 = q-p+1
2. n2 = r-q
3. create arrays L[1..n1+1] andR[1..n2+1]
4. for i = 1 to n1
5. do L[i] = A[p+i-1]
6. for j = 1 to n2
7. do R[j] = A[q+j]
8. L[n1+1] = +inf
9. R[n2+1] = +inf //哨兵
10. i =1
11. j = 1
12. for k = p to r
13. do if L[i] =< R[j]
14. then A[k] = L[i]
15. i = i+1
16. Else A[k] = R[j]
17. j = j-1