算法，一直是我想去大公司路上的一块绊脚石，总觉得平时用不到，但是考试总要考，不管是否能用到，学习总归是好事，前不久买了本《算法导论》接下来的日子，我会把自己看到的关于算法东西写出来，用罗胖的话就是，读书是一件苦事，死磕自己，娱乐大家。

一、插入排序

先上伪代码：

INSERTION-SORT(A)

1.for j=2 to A.length

2.   key = A[j]

3.   //Insert A[j] into the sorted sequence A[1..j-1]

4.   i = j - 1

5.   while i > 0 and A[i] > key

6.       A[i+1] = A[i]

7.       i = i -1

8.     A[i+1] = key

听名字就容易理解，“插入”就像排队一样，最起码你前面有一个人，你插队插在他前面，才叫插入。因此，for循环就从j=2（本文是根据读《算法导论》编写，因此下标统一从1开始），也就是第二个数开始。排序肯定涉及到交换，交换肯定涉及到中间变量，第二行key就是这个中间变量。从队尾的前一个开始比较，因此第四行：i = j - 1,交换的条件要满足不能超过数组的一个，而且待排序的数要比前面的值大才能交换。接下来就是插入排序的精髓：尾部和倒数第二个交换后，之前的尾部（也就是现在的倒数第二个数）还是待排序（此时表示排序完成），因此它要和倒数第三个数进行比较，这时的待比较的下标就变为i = i-1，第7行和第8行应该可以换位置，只不过如果换位置A[i+1] = key就要变为A[i] = key.

ok，这就是插入排序了，过程就像打扑克的起牌过程，手里的牌由少变多，依次插入。