算法，一直是我想去大公司路上的一块绊脚石，总觉得平时用不到，但是考试总要考，不管是否能用到，学习总归是好事，前不久买了本《算法导论》接下来的日子，我会把自己看到的关于算法东西写出来，用罗胖的话就是，读书是一件苦事，死磕自己，娱乐大家。
一、插入排序
先上伪代码：
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，这就是插入排序了，过程就像打扑克的起牌过程，手里的牌由少变多，依次插入。
