原因:之所以会去看循环不变性，是突然想到，要如何证明自己的递归算法的正确性，于是看着看着就看到了循环不变式，问题就来了。

分析:
一直在想，作者想给我们传达什么意思，什么叫做不变，不变在哪里，因为书中只给出了这个所谓的循环不变式的三个性质，所以一直纳闷，作者是怎么定义这个循环不变式的，想了想说说自己的见解，也不知是不是就是作者要表达的意思。如理解有错，请指教。

Definition:所谓的循环不变式，是一个笼统的说法，是一个整体上观察的整体性质不变，如书中举的例子(插入排序)，其整体性质就是在插入之前，前面已经是排好顺序的了，这就是它不变的地方。也就是比如 5 2 4 6 1 3，再排序起初，5是排好序的（单5一个当然是排好序的），从第二开始拿出，插入之后，成为2 5，也是排好序的，接下来当第3个拿来时是4它前面也是排好序的了（2 5），所以能保证每次插入前都是排好序的。也就是说插入排序的不变，不变在，在待排结点之前前面的结点已经是排好序的了。


而循环不变式有三个性质(简单说，想了解自己看算法导论)：
1.初始正确。2.保持（其实也就是保持要解决问题的不变性）3.终止，即循环结束。
而证明上面的插入排序的正确性，关键是保证了，1，2的正确性，到3终止时，就能得出结果（这里就是全部排好序了）。个人觉得三个要证明第2个才是最重要的，第2而证明了，不久可以由终止条件推出结果了吗？反正书上是说第3个最重要。这是我的理解，对其“不变”所指意思的理解。

收到的鲜花

• demonleer 于 2012-08-09 09:08 送鲜花  10朵   附言：态度认真

算法有个基本的条件是有穷性。不能终止的算法不能称之为算法，这个可能是书上说第三点最重要的原因吧。可能这在理论上很重要，是区别递归算法与数学归纳的分界线。
一到无穷的世界里事情就变得比较复杂。比如说把限制条件放宽，放到理论高度上，允许构造无穷性的算型(我瞎起个名字，反正不能叫算法了)。已知一无穷长数列，试在其上应用插入排序，问是否能构得到有序数列？答案应该是肯定的。
但是冒泡排序可能就不行。因为冒泡排序的前提似乎是存在最大元，但这在一般的无穷数列里都不成立。 不过由于 有限数列存在最大元 是个定理，从而冒泡排序是一个正确的算法，但不是算型。

我瞎举的例子，其实我也没深入研究过算法的理论。不过这种理论性强的东西不用太在意，把精髓学到手就行了。有自己的理解是很好的。

收到的鲜花

• demonleer 于 2012-08-09 09:08 送鲜花  10朵   附言：优秀评论

个人觉得和归纳法证明的思想类似。