插入排序与循环不变式

2017/6/29 posted in  算法&数据结构

插入排序

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

输入: 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] 始终保持了递增这一个属性,因此验证了插入排序这个算法的正确性。