循环不变式证明算法的正确性

循环不变式主要用来辅助我们理解算法的正确性，对于循环不变式，必须证明它的三个性质（有些类似于数学归纳法的意味）：

初始化：它在循环的第一轮迭代开始之前，应该是正确的。

保持：如果在某一次循环迭代开始之前是正确的，那么在下一次迭代开始之前，它也应该保持正确（假设当循环变量等于k时符合，再看执行一遍循环体后是否还符合循环不变式）。

结束：当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的（这一步是和数学归纳法不同的一点，用循环不变式则更进一步，数学归纳法到这里就得出了一个关系式就结束，而用循环不变式，不但要先确保一个正确的关系式，还要看最后循环结束时，循环变量最后等于多少，根据循环不变式推导是否符合自己的要求。）。

编写循环时，找到让每次循环都成立的逻辑表达式很重要。这种逻辑表达式称为循环不变式（loop invariant）。循环不变式相当于用数学归纳法证明的“断言”。循环不变式用于证明程序的正确性。在编写循环时，思考一下“这个循环的循环不变式是什么”就能减少错误。

注意：好像每个循环都可以找到一个循环不变式，并通过这个循环不变式证明循环迭代的正确性。

插入排序算法的证明

对照循环不变式的原理，下面来试着对插入排序算法的正确性进行论证。

插入算法及其实现在此已经讲过：

INSERTION_SORT(A) pseudocode

for j<--- 2 to length[A]

do key<---A[j]

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

i<---j-1

while i>0 and A[i]>key

do A[i+1]<---A[i]

i<---i-1

A[i+1]<---key

初始化：在第一轮迭代开始之前，证明其正确性。此时j=2，A[1…j-1]中只有一个元素A[1]，显然，一个元素是已经排序的了。所以，证明了循环不变式在第一轮迭代之前是成立的。

保持：接下来要证明在每轮迭代中，循环不变式保持成立。迭代之前，假设A[1…j-1]是已经排好序的序列，待排序的元素A[j]依次与A[j-1]、A[j-2]进行比较，如果A[j-1]等大于A[j]，则依次将其向右移动一位A[i+1]<---A[i]，当遇到开始小于A[j]的元素时，则A[j]找到了合适的插入位置，插入之后，整个序列又是排好序的了。即在假设j成立的情况下，j+1也成立，循环不变式在迭代过程中保持成立。

终止：最后，分析一下循环结束时候的情况。当j=n+1时，循环结束，此时A[1…n]中已经有n个元素，且已经排好序，就是排好序的数组A[1…n]，所以算法正确。

原文：https://blog.csdn.net/mountzf/article/details/51866342