排序算法之：循环不变式在 Cocktail Shaker Sort 中的正确性证明 题目描述 Cocktail Shaker Sort（鸡尾酒摇动排序）是冒泡排序的一种变体，它通过双向交替遍历数组来优化元素移动效率。我们需要使用 循环不变式 方法，严格证明该排序算法的正确性，即证明算法执行后数组一定按非降序（或非升序）排列。 解题过程 1. 算法原理回顾 Cocktail Shaker Sort 的核心操作分为两个阶段，交替进行： 从左向右扫描 ：比较相邻元素 arr[j] 与 arr[j+1] ，若逆序则交换，将最大值“冒泡”到右侧正确位置。 从右向左扫描 ：比较相邻元素 arr[j] 与 arr[j-1] ，若逆序则交换，将最小值“沉淀”到左侧正确位置。 每一轮双向扫描后，排序范围的左右边界各收缩一个位置。 2. 定义循环不变式 设数组为 arr[0...n-1] ，排序方向为非降序。在算法执行过程中，维护以下循环不变式： 不变式 L（左侧已排序） ：在从左向右扫描结束后，当前扫描范围的 最右端 元素是剩余未排序部分的最大值，且其位置已固定。 不变式 R（右侧已排序） ：在从右向左扫描结束后，当前扫描范围的 最左端 元素是剩余未排序部分的最小值，且其位置已固定。 全局不变式 G ：每一轮完整的双向扫描（先左→右，再右→左）结束后，数组的 最左端 和 最右端 各有一个元素被放置到最终正确位置，且这两个位置之间的子数组仍满足未排序状态。 3. 初始化阶段 初始时，左右边界为 left = 0 ， right = n-1 。 由于尚未进行任何排序操作，不变式 L 和 R 在边界位置尚未建立，但全局不变式 G 的初始条件自然满足（因为整个数组均为“未排序”）。 4. 保持阶段 假设在第 k 轮双向扫描开始时，左边界为 l ，右边界为 r ，且前 k-1 轮已正确将 l-1 个最小元素和 r+1 个最大元素放置到最终位置。 步骤 4.1 从左向右扫描 遍历 j 从 l 到 r-1 ，比较并交换 arr[j] 与 arr[j+1] 。 不变式 L 的保持 ：扫描结束时，最大值会通过连续交换被推到 arr[r] 。由于这是剩余子数组中的最大值，因此 arr[r] 已处于最终位置。 此时，右边界可安全地收缩为 r-1 。 步骤 4.2 从右向左扫描 遍历 j 从 r-1 到 l+1 ，比较并交换 arr[j-1] 与 arr[j] 。 不变式 R 的保持 ：扫描结束时，最小值会通过连续交换被推到 arr[l] 。由于这是剩余子数组中的最小值，因此 arr[l] 已处于最终位置。 此时，左边界可安全地收缩为 l+1 。 步骤 4.3 全局不变式 G 的保持 本轮双向扫描后， arr[l] 和 arr[r] 已处于最终正确位置，且子数组 arr[l+1...r-1] 仍为未排序部分。 下一轮扫描将在 l+1 和 r-1 之间进行，重复上述过程。 5. 终止条件 当左边界 l 与右边界 r 相遇（即 l >= r ）时，说明所有元素已处理完毕。根据不变式 G，每一轮双向扫描均固定了一个最小和一个最大元素，因此当边界重合时，整个数组已排序。 6. 正确性结论 通过循环不变式的初始化、保持和终止三个阶段的严格证明，我们得出 Cocktail Shaker Sort 能够正确将数组按非降序排列。该证明方法确保了算法在任意输入下的可靠性，同时揭示了其双向扫描机制对冒泡排序的改进本质。