排序算法之：循环不变式在圈排序（Cycle Sort）中的正确性证明 题目描述 圈排序（Cycle Sort）是一种基于环分解的原地排序算法，其核心思想是通过将每个元素一次性放置到它在最终有序数组中的正确位置，从而最小化写操作次数。该算法特别适用于需要减少内存写入次数的场景（如闪存存储设备）。现在，请你证明圈排序的正确性——即通过定义并验证其循环不变式，确保算法能够正确排序任意数组。 解题过程 1. 算法回顾 圈排序的步骤如下： 初始化一个指针 i （从 0 到 n-2 遍历）。 对于每个位置 i ，设当前元素为 item = arr[i] 。 计算 item 在最终有序数组中的正确位置 pos ，即统计数组中比 item 小的元素个数（若有重复元素，需处理稳定性，但标准圈排序不保证稳定）。 若 pos 等于 i ，说明 item 已在正确位置，继续下一个 i 。 否则，将 item 与 arr[pos] 交换，并重复步骤 3-4，直到形成一个环（即某次交换后 pos == i ）。 完成当前环后，移动至下一个 i 。 2. 定义循环不变式 对于外层循环的每次迭代（处理位置 i 时），定义循环不变式如下： 不变式 P ：子数组 arr[0..i-1] 中的每个元素已位于其最终正确位置，且剩余子数组 arr[i..n-1] 包含未处理的元素，但可通过后续环分解正确排序。 3. 初始状态验证 初始时 i = 0 ，子数组 arr[0..-1] 为空，默认满足“所有元素在正确位置”。剩余数组 arr[0..n-1] 包含全部未处理元素，符合不变式。 4. 迭代过程维护 假设 ：在迭代开始（处理位置 i ）时，不变式 P 成立。 处理位置 i ： 若 arr[i] 已在正确位置（ pos == i ），则直接令 i++ 。此时 arr[0..i-1] 仍满足有序且位置正确， arr[i] 新加入已处理部分，不变式保持。 若 arr[i] 不在正确位置，则通过环分解将其归位： 内层循环通过交换将 arr[i] 移动到正确位置 pos ，同时将原 arr[pos] 作为新 item 继续处理。 关键点：每次交换均将至少一个元素（当前 item ）放置到其最终位置，且不会破坏已处理子数组的顺序（因为已处理子数组中的元素不再被移动）。 终止条件 ：当内层循环完成一个环（即回到起始位置 i ）时，环中所有元素均被放置到正确位置，此时 i++ ，不变式 P 仍成立。 5. 终止与正确性 终止性 ：外层循环执行 n-1 次（最后一位自动有序），内层环分解保证每个元素仅处理一次，故算法必终止。 结果正确性 ：终止时 i = n-1 ，由不变式 P 可知 arr[0..n-2] 已有序，且 arr[n-1] 是剩余最大元素，故整个数组有序。 6. 实例演示 以数组 [4, 2, 3, 1] 为例： i=0 ： item=4 ，正确位置 pos=3 ，交换后为 [1, 2, 3, 4] ，继续处理 item=1 （ pos=0 ，形成环）。 i=1 ： item=2 已在正确位置（ pos=1 ）。 i=2 ： item=3 已在正确位置（ pos=2 ）。 最终得到有序数组 [1, 2, 3, 4] ，且每一步均满足不变式。 总结 通过循环不变式证明了圈排序的正确性：算法在每次迭代后均保持已处理部分有序，且通过环分解逐步将剩余元素归位，最终实现整体排序。