数据结构与算法 / 系统课时
循环不变式
循环不变式
循环不变式是在指定的迭代检查点持续成立的性质。它描述目前已经处理到哪里以及这一部分满足什么条件。要证明整个算法正确,还要说明退出时为何得到后置条件,以及循环为何会退出。 MIT《计算机科学的数学》不变式资料
学习目标
- 写出检查点、循环条件、不变式和后置条件。
- 用初始化与保持证明退出时的结果性质,并给出终止理由。
- 对插入排序同时证明非递减、元素守恒和原输入保持不变。
四个检查点
- 初始化。 首次检查循环条件前,不变式成立,即使循环体一次都不会执行。
- 保持。 假设某轮开始前不变式和循环条件成立,证明执行一轮后不变式仍成立。
- 退出推出结果。 把不变式与循环条件为假结合,得到目标后置条件。
- 证明终止。 找一个每轮严格下降且有下界的整数,或给出等价的有限步理由。只有退出推导只能说明若终止就正确。

插入排序的外层不变式
给定整数列表,排序返回新列表,要求按非递减顺序包含原来每个元素和它的出现次数。先复制输入,把 j 定义为已处理前缀的长度。每次检查外层条件前,满足 0 ≤ j ≤ n,a[:j] 已按非递减顺序排列,且与原始输入的前 j 个元素有相同的多重集合。后缀 a[j:] 仍与原输入对应后缀相同。 MIT 插入排序课程资料
- 初始化。
j=min(1,n)。空前缀或单元素前缀已排序,复制后元素和后缀都匹配。 - 保持。 保存
key=a[j]。从有序前缀的右端向左,把连续大于key的元素右移一个位置。当左侧为空或遇到不大于key的元素时,将key放在空位。插入点两侧保持顺序,保存的key加回后元素守恒;暂时的重复位置只发生在内部右移时。下一段后缀不受影响,令j←j+1后外层不变式仍成立。 - 退出。 外层条件
j<n不成立时,由j≤n得j=n。已排序前缀覆盖整个输出,元素次数保持不变。 - 终止。 外层剩余量
n-j每轮减 1。内层索引i每次右移后也减 1,降到 −1 后短路停止,不会读a[-1]。
用断言检查状态
把下面程序保存为 insertion_sort_demo.py,使用 Python 3.11 或以上运行。可选检查在外层迭代边界验证有序、元素次数及后缀。它用于调试样例。Python 可在优化模式关闭断言,且这里的切片、计数和排序会增加执行成本,性能实验应关闭检查。 Python Counter 多重集合接口
python
from collections import Counter
def insertion_sort(values: list[int], *, check: bool = False) -> list[int]:
a = values.copy()
n = len(a)
j = min(1, n)
while True:
if check:
assert 0 <= j <= n
assert a[:j] == sorted(a[:j])
assert Counter(a[:j]) == Counter(values[:j])
assert a[j:] == values[j:]
if j == n:
return a
key = a[j]
i = j - 1
while i >= 0 and a[i] > key:
a[i + 1] = a[i]
i -= 1
a[i + 1] = key
j += 1
if __name__ == "__main__":
data = [5, 2, 4, 6, 1, 3, 2]
print("原始数组:", data)
print("排序结果:", insertion_sort(data, check=True))
assert insertion_sort([], check=True) == []text
原始数组: [5, 2, 4, 6, 1, 3, 2]
排序结果: [1, 2, 2, 3, 4, 5, 6]程序用 while True 加返回实现每次先做检查再判断退出,j==n 正好对应证明中 j<n 为假。关闭检查时,逆序且各值不同的输入需要移动 次;复制的输出列表占用随输入长度增长的空间。不要把调试模式中的额外切片或排序开销计入核心步骤。 MIT 插入排序课程资料
本课练习
给非空列表的最大值扫描写出前缀不变式与剩余量。再暂时注释排序中插回 key 的赋值语句,用 [2,1] 观察有序检查与元素次数检查哪个发现问题。下一章从输入规模和基本操作开始分析算法成本。
按自己的节奏,确认真正理解。