排序算法之：循环不变式在 Stooge Sort 中的正确性证明

题目描述
Stooge Sort（臭皮匠排序）是一种低效但有趣的递归排序算法。对于一个包含 n 个元素的数组 A[0..n-1]，其核心思想是递归地进行以下操作：

1. 如果 A[0] > A[n-1]，则交换这两个元素。
2. 如果当前子数组长度大于等于 3，则递归地将前 2/3 部分排序，再递归地将后 2/3 部分排序，最后再次递归地将前 2/3 部分排序。
   本题目要求使用循环不变式（Loop Invariant）的方法，严格证明 Stooge Sort 算法的正确性，即证明算法执行后，整个数组 A 会按非降序排列。

解题过程

第一步：理解 Stooge Sort 的递归过程
Stooge Sort 的伪代码如下（假设数组索引从 0 开始）：

StoogeSort(A, left, right):
    if A[left] > A[right]:
        swap(A[left], A[right])
    if right - left + 1 >= 3:
        t = (right - left + 1) / 3  // 计算 1/3 的长度
        StoogeSort(A, left, right - t)    // 排序前 2/3
        StoogeSort(A, left + t, right)    // 排序后 2/3
        StoogeSort(A, left, right - t)    // 再次排序前 2/3

注意：t 是子数组长度的 1/3，向下取整。例如，长度 5 时 t=1，前 2/3 是 A[0..3]，后 2/3 是 A[1..4]。递归的终止条件是子数组长度小于 3（长度 1 或 2 时，步骤 1 的比较交换足以保证有序）。

第二步：定义循环不变式（递归不变式）
由于 Stooge Sort 是递归算法，我们使用“递归不变式”（Recursion Invariant）来证明正确性，其思想与循环不变式类似，即在每次递归调用前后，子数组的某些性质保持不变。
对于任意一次调用 StoogeSort(A, l, r)，我们定义递归不变式为：

在调用开始和结束时，子数组 A[l..r] 的最大值不会出现在其前 1/3 部分（即索引 < l+t 的区域），且最小值不会出现在其后 1/3 部分（即索引 > r-t 的区域），同时整个子数组的最大值和最小值分别位于正确边界。

但更实用且易于证明的不变式是：

在每次递归调用 StoogeSort(A, l, r) 完成后，子数组 A[l..r] 会被完全排序（非降序）。

第三步：证明递归不变式在基础情况下成立
基础情况：子数组长度 len = r - l + 1 ≤ 2。

• len = 1：数组已排序，不变式成立。
• len = 2：算法比较 A[l] 和 A[r]，若 A[l] > A[r] 则交换，结果确保 A[l] ≤ A[r]。因此子数组有序，不变式成立。

第四步：证明递归情况
假设：对于任意长度小于 n 的子数组，StoogeSort 都能正确排序（归纳假设）。
现在考虑长度 n ≥ 3 的子数组 A[l..r]。设 t = ⌊(n)/3⌋，表示 1/3 长度（向下取整）。证明分四个阶段：

1. 第一阶段：比较交换边界
   执行 if A[l] > A[r]: swap(A[l], A[r])。这一步确保整个子数组的最小值不会大于最大值，但并未完全排序。

2. 第二阶段：排序前 2/3 部分 A[l .. r-t]
   注意：前 2/3 部分的长度为 n - t，因为 t ≤ n/3，所以 n - t ≥ 2n/3，其长度严格小于 n（当 n>2 时）。根据归纳假设，递归调用 StoogeSort(A, l, r-t) 完成后，A[l..r-t] 被排序。
   关键观察：此时，前 2/3 部分的最大值（记为 M1）位于 A[r-t] 位置。

3. 第三阶段：排序后 2/3 部分 A[l+t .. r]
   后 2/3 部分长度也是 n - t，同样小于 n。递归调用 StoogeSort(A, l+t, r) 完成后，A[l+t..r] 被排序。
   关键观察：此时，后 2/3 部分的最小值（记为 m2）位于 A[l+t] 位置。
   另外，由于 A[l..r-t] 已有序，且 A[r-t] 是前 2/3 的最大值，而 A[l+t] 是后 2/3 的最小值，但这两个子数组有重叠（重叠部分为 A[l+t .. r-t]），因此我们需要证明 M1 ≤ m2。
   实际上，在第二阶段结束后，A[r-t] 是前 2/3 的最大值，但第三阶段排序后 2/3 时，可能改变了 A[r-t] 的值（因为 A[r-t] 属于重叠部分）。不过，重叠部分的存在是关键。

4. 第四阶段：再次排序前 2/3 部分 A[l .. r-t]
   由于第三阶段可能破坏了前 2/3 部分的有序性，我们再次递归调用 StoogeSort(A, l, r-t)。完成后，A[l..r-t] 重新有序，且其最大值仍位于 A[r-t]。
   现在证明整个数组 A[l..r] 已排序：

   • 考虑整个数组分为三部分：X = A[l..l+t-1]（前 1/3），Y = A[l+t..r-t]（中间 1/3），Z = A[r-t+1..r]（后 1/3）。注意，当 n 不是 3 的倍数时，这些部分长度可能相差 1，不影响证明。
   • 在第四阶段后，X ∪ Y 有序（即前 2/3 有序）。
   • 在第三阶段后，Y ∪ Z 有序（即后 2/3 有序）。
   • 由于 Y 同时属于前 2/3 和后 2/3，且这两个子数组各自有序，可以推断：X 的所有元素 ≤ Y 的最小元素，且 Y 的最大元素 ≤ Z 的最小元素。
   • 具体地，前 2/3 的最大值在 A[r-t]（即 Y 的末尾），后 2/3 的最小值在 A[l+t]（即 Y 的开头）。由于 Y 自身有序（因为它是两个有序子数组的交集），所以整个数组有序。

第五步：归纳完成
由数学归纳法，对于任意长度的子数组，StoogeSort 调用后都能使其有序。因此，对整个数组 A[0..n-1] 调用后，数组完全排序，算法正确。

补充说明

1. 这个证明依赖于递归调用对更小长度的子数组正确的归纳假设。
2. 重叠部分 Y 的存在保证了前后两部分的衔接。
3. 尽管算法效率极低（时间复杂度约为 O(n^2.71)），但正确性是可以严格证明的。
4. 本证明中，递归不变式实际上是“每次调用后子数组有序”，这比最初描述的边界值不变式更直接且易于归纳。