[算法]-插入排序

　　以下是插入排序的伪代码，只用来表示算法的核心思想

 1   定义一个数组A[1..n],长度为n的序列。使用插入排序算法，将数组A进行排序;
 2     
 3     insertion-sort:
 4         for j=2 to A.length
 5         　　key = A[j]
 6         　　// 将A[j] 插入到已经排序的队列A[1..j-1]
 7         　　i=j-1
 8         　　while i>0 and A[i] > key
 9             　　A[i+1] = A [i]
10             　　i=i-1
11         　　A[i+1] = key

　　第一次看这个逻辑，比较难以理解是从 8 到 11行；

　　假设数组A现在是这样 [*,*,*,x,y,y,y]
　　* 表示已经排序的数,
　　x 表示正在进行操作的数,
　　y 表示未排序的数.

　　第8-11行就是将x插入到已经排序的序列[*,*,*] 中，由于是新插入一个元素，所有比x大的元素都会向后顺延一个位置，并且由于i的初始值是j-1,所以即使最大的i再+1,也不过是等于j，总的进行排序的元素个数就是从1到j，没有超出范围。第11行的A[i+1]=key，是由于跳出while时，i执行了一次减1操作，所以比实际要插入的位置要小1，因此第11行要进行加1操作.