排序算法之：循环不变式在循环排序（Cyclic Sort）中的正确性证明 题目描述 循环排序（Cyclic Sort）是一种针对特定范围数据（例如元素为 1 到 n 的整数）的高效原地排序算法。其核心思想是通过将每个元素交换到其正确的位置，从而在一次遍历中完成排序。我们需要通过循环不变式来证明该算法的正确性，确保在每次迭代中，部分数组已排序，且最终整个数组有序。 解题过程 算法步骤概述 假设数组包含 n 个元素，取值范围是 1 到 n（或 0 到 n-1）。 遍历数组，对于当前索引 i，若元素 nums[ i] 不在其正确位置（即 nums[ i] ≠ i + 1），则将其与正确位置（索引 nums[ i ] - 1）的元素交换。 重复交换直到当前元素归位，再移动至下一索引。 定义循环不变式 循环不变式是： 在每次迭代开始时，子数组 nums[ 0..i-1] 已包含 1 到 i 的正确元素（即 nums[ j] = j + 1 对所有 j < i 成立） 。 初始化 ：当 i = 0 时，子数组为空，不变式成立。 保持 ： 若 nums[ i ] = i + 1，则 i 自增，不变式仍成立。 若 nums[ i] ≠ i + 1，则通过交换将 nums[ i] 放到正确位置（索引 nums[ i] - 1）。此操作确保该元素归位，且可能将其他元素移至更早位置，但不会破坏已排序部分（因为交换仅影响未处理区域）。重复直到 nums[ i] = i + 1，此时 i 自增，子数组 nums[ 0..i-1 ] 仍满足不变式。 终止 ：当 i = n 时，子数组 nums[ 0..n-1 ] 包含 1 到 n 的正确元素，数组完全有序。 正确性证明细节 交换操作的保守性 ：每次交换至少将一个元素放置到正确位置，且不会移动已处理部分的元素（因为正确位置索引始终 ≥ i）。 无重复处理 ：由于元素范围确定，每个元素有唯一正确位置，确保交换过程不会陷入无限循环。 时间复杂度 ：每个元素最多被交换一次归位，总操作次数为 O(n)。 边界情况处理 若数组包含重复元素，循环排序需调整（例如通过标记避免死循环），但本题假设元素唯一。 对于范围 0 到 n-1 的情况，正确位置为 nums[ i ] = i。 通过循环不变式的三步验证，可严格证明循环排序的正确性。