循环排序（Cyclic Sort）

题目描述
给定一个长度为 n 的数组，其中的元素是范围在 [1, n] 内的整数，且每个整数只出现一次。请设计一个算法，将数组排序为升序。要求时间复杂度为 O(n)，空间复杂度为 O(1)（除了排序本身占用的额外空间，允许修改原数组）。

示例
输入：[4, 3, 2, 1]
输出：[1, 2, 3, 4]

输入：[3, 1, 2, 5, 4]
输出：[1, 2, 3, 4, 5]

解题过程

步骤 1：理解核心思想
循环排序的核心思想是利用“元素值与其目标索引的对应关系”。对于范围在 [1, n] 且不重复的数组，每个元素 x 在排序后应该位于索引 x-1 的位置（因为数组索引从 0 开始）。
例如，元素 3 应该放在索引 2 的位置。

步骤 2：算法流程

1. 遍历数组，对于每个位置 i：

   • 如果当前元素 nums[i] 不在它应该在的位置（即 nums[i] ≠ i+1），则将其与它正确位置（nums[i]-1）的元素交换。
   • 交换后，新的元素可能仍不在正确位置，因此需要继续检查当前位置 i，直到 nums[i] 等于 i+1 才移动到下一个位置。

2. 重复上述过程直到整个数组有序。

为什么能保证 O(n) 时间复杂度？
每次交换都会将一个元素放到正确位置，而每个元素最多被交换一次（一旦放对位置就不再移动），所以总交换次数不超过 n-1 次，时间复杂度为 O(n)。

步骤 3：示例推导
以 [3, 1, 2, 5, 4] 为例：

• i=0：nums[0]=3，正确位置应为索引 2（因为 3 应放在索引 2）。交换 nums[0] 和 nums[2]：
  [2, 1, 3, 5, 4]
  此时 nums[0]=2，正确位置是索引 1，交换 nums[0] 和 nums[1]：
  [1, 2, 3, 5, 4]
  现在 nums[0]=1（正确），i 移到下一个位置。

• i=1：nums[1]=2（正确），继续。

• i=2：nums[2]=3（正确），继续。

• i=3：nums[3]=5，正确位置应为索引 4，交换 nums[3] 和 nums[4]：
  [1, 2, 3, 4, 5]
  此时 nums[3]=4（正确），继续。

• i=4：nums[4]=5（正确），排序完成。

步骤 4：代码实现要点

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        correct_index = nums[i] - 1  # 元素 nums[i] 应该在的位置
        if nums[i] != nums[correct_index]:
            nums[i], nums[correct_index] = nums[correct_index], nums[i]
        else:
            i += 1  # 只有当前元素已在正确位置时才移动指针
    return nums

关键细节

• 交换时不能直接移动指针 i，因为交换到当前位置的新元素可能仍需处理。
• 只有当 nums[i] 等于 i+1 时，才递增 i。

总结
循环排序是解决“元素范围已知且不重复”类排序问题的高效方法，通过利用索引与值的映射关系，以最小交换次数达到 O(n) 时间复杂度的排序效果。