插入排序的分析（INSERTIOM-SORT）

一、插入排序如同扑克牌排序

排序伪代码如下 A为目标数组

for j = 2 to A.lenth
    key = A[ j ]
    i = j - 1
    while i > 0 and A[i] > key
        A[i + 1] = A[ i ]
        i--
    A[i + 1] = key

想象自己摸牌的时候，假设左手拿牌，右手摸牌，左手的牌最大的在右边，小的在左边（3, 4, …, Q，K, A, 2）已排序。 假设A为最终摸到的所有牌的集合[ A₁ - A_n ]，按摸牌的顺序排列，j 为 第 j 次摸牌，key = A[ j ] 代表右手摸到的牌(第 j 次摸的牌)，i 为左手中要与右手摸到的牌 key 比较的牌的位置（从最大的牌开始比较），刚开始 i = j - 1 等于左手的总牌数，A[ i ] 就是左手最大的牌（因为左手是已拍好序的牌），如果 i > 0 && 左手最大的牌 A[ i ]比摸到的牌 key 大，则 A[ i ]这张牌要往后移一位 A[i + 1] = A[ i ]（因为 key 这张牌肯定要插在前面某个位置）, i 要指向前一张牌 i - -（左手倒数第二张牌）, 再继续让左手倒数第二张牌 A[ i ] 与右手摸到的牌 key 比，直到摸到牌 key 比 A[ i ] 大或者 i 指向 0（代表左手没有牌可以和摸的牌比了），这时候把摸到的牌 key 放到与之比较的牌 A[ i ] 的后面 A[i + 1] = key （i = 0 时, A [1] = key 实际就是放在左手第一张）。

循环不变式的三条性质

初始化

第一层执行循环体之前，结果是正确的。 或者说 不执行循环体的时候，结果是正确的

保持

某次循环体执行之前结果是正确的，那么下次循环体执行之前也为真，也就是执行完这次循环体结果还是正确的

终止

在循环体终止时，终止条件成立的时候就是完成算法目标的时候，所以这个性质有助于判断该算法是正确