插入排序

《算法导论》第一部分中并没有详细讲解某一种算法，而是以讲解算法这个概念，而插入排序是讲解算法基础的例子。

输入： n 个数的一个序列 <a1, a2, ..., an>。
输出： 输入序列的一个排列 <a1', a2', ..., an'>

因为算法很简单，就直接上代码：

A = [2, 5, 1, 3, 7, 6]

def instertion_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key: # compare nums[j] and key
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key # set nums[j + 1] is key
    return nums


if __name__ == '__main__':
    print(instertion_sort(A))

下午看完了第二章第二节之后，晚上尝试完全凭记忆敲这段代码，结果还是出了两个问题，就是我打注释的两个地方。

第一个是 while 的判断条件，j 的临界条件是不小于 0，可能因为导论的数组是从 1 开始的，进过我已经意识到了，在写 range 的时候就意识到了，但是我手写的时候依然写的是 j > 0，可能只是下意识的担心越界。

第二个地方就是 nums[j + 1] = key，我一开始的时候写的是，nums[i] = key，这个应该是纯粹脑残了，因为 while 以 key 为基准，对前 i 个数字排排坐，而 key 最后落座在哪里，是通过 while 循环跑出来的，也就是说是和 j 的值相关。

循环不变式

对于循环不变式这个概念，导论引入的的确有点突兀，不过在看了一些人有趣的解释之后也算是明白了（比如知乎的这个讨论：https://www.zhihu.com/question/26700198 ）

循环不变式是验证循环正确性的一种方法，关注循环体中的主要的属性（比如在插入排序中 nums[0...i-1] 这段数字是保持递增的属性），如果这种属性能在开始循环时，循环中，结束循环后，都一直保持，那么我们就认为这个循环是正常工作的。

在算法导论中尝试使用数学归纳法来验证这个循环：

初始化： 循环得第一次迭代之前，它为真
保持： 如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真
终止： 在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

因为这三个状态（开始，进行，结束），nums[0...i-1] 始终保持了递增这一个属性，因此验证了插入排序这个算法的正确性。