如何通过归纳法推导排序算法的循环不变量并分析时间复杂度？

伪代码实现 #

Input: array A[0 . . . n − 1]

i ← 0
while i < n do
    if i = 0 or A[i] ≥ A[i − 1] then:
       i ← i + 1
    else
       swap A[i] and A[i − 1]
       i ← i − 1

一、基于循环不变量的正确性证明 #

给定循环不变量：当变量i首次递增到新值i=k时，数组的前k个元素按升序排列。我们用数学归纳法分三步证明算法正确性：

1. 初始化（基础情况） #

当i首次递增到k=1时，前1个元素仅包含A[0]，单个元素天然满足升序排列，循环不变量成立。

2. 归纳保持（归纳步骤） #

假设当i首次递增到k时，数组的前k个元素A[0..k-1]是升序排列的。现在分析从i=k到i首次递增到k+1的过程：

• 若i=k时，A[k] ≥ A[k-1]（k≥1），则直接将i递增到k+1。此时前k+1个元素A[0..k]是升序的前k个元素加上不小于末尾的A[k]，显然满足升序，循环不变量保持。
• 若A[k] < A[k-1]，则交换A[k]与A[k-1]，并将i递减到k-1。此时前k个元素中，刚交换后的A[k-1]（原A[k]）可能小于A[k-2]，因此会继续触发循环中的交换逻辑：i不断递减、交换相邻元素，直到i=0或当前元素≥前一个元素，随后i开始递增。当i最终再次递增到k时，前k个元素会重新恢复升序（较小的元素已被移动到合适位置，不会破坏之前的升序结构）；当i继续递增到k+1时，前k+1个元素必然是升序的，循环不变量保持。

3. 终止条件 #

当循环终止时，i=n。根据循环不变量，此时数组的前n个元素（即整个数组A[0..n-1]）按升序排列，算法完成排序，正确性得证。

二、时间复杂度分析 #

1. 最好情况 #

当输入数组已经是升序排列时，每次循环都会直接执行i ← i+1，循环总共执行n次，每次操作都是O(1)，因此时间复杂度为O(n)。

2. 最坏情况 #

当输入数组是严格降序排列时，每个元素都需要向前“冒泡”到最前面的正确位置。例如，第k个元素（从0开始计数）需要交换k次，再从位置0重新递增到k+1。总操作次数为1+2+...+(n-1) = n(n-1)/2，属于O(n²)级别，因此最坏时间复杂度为O(n²)。

3. 平均情况 #

对于随机排列的数组，每个元素的平均移动次数为O(n)，总共有n个元素，因此平均时间复杂度同样为O(n²)。

内容的提问来源于stack exchange，提问作者CluelessStudent