排序算法之：循环排序（Cyclic Sort）的进阶应用——原地重排数组使得“数组元素与索引的差值映射”保持特定顺序

题目描述

给定一个包含 n 个元素的数组 nums，其中的元素是 0 到 n-1 的排列（即包含从 0 到 n-1 的所有整数，每个整数恰好出现一次）。你的目标是在 O(n) 时间复杂度和 O(1) 额外空间复杂度内，原地重新排列这个数组，使得对于任意索引 i，满足 nums[i] = i。这本质上就是将数组排序为升序。但如果我们修改条件，要求你重排数组，使得对于任意索引 i，满足 nums[i] = (i + k) mod n，其中 k 是一个给定的非负整数（循环偏移），该如何实现？

更一般地，如果我们允许数组元素是 0 到 n-1 的一个排列，但要求重排后满足一个更通用的映射关系：nums[i] = f(i)，其中 f 是一个从索引集合 {0, 1, ..., n-1} 到其自身的双射（一一对应），如何设计一个通用的原地 O(n) 算法？

问题简化：我们先从基础问题开始：已知 nums 是 0 到 n-1 的一个排列，请通过交换操作，将其排序为升序（即满足 nums[i] = i）。

解题过程

第一步：理解基础循环排序（Cycle Sort）原理

循环排序是一种原地、不稳定的排序算法，特别适用于当数组元素是已知范围内的连续整数排列时。它的核心思想是利用元素值与目标索引之间的对应关系，通过一系列“环”将每个元素放置到正确位置，每个环内部通过循环交换完成。

对于一个排列，排序到 nums[i] = i 的算法步骤如下：

1. 遍历数组，对于每个索引 i：
   a. 如果 nums[i] 已经等于 i，说明该元素已在正确位置，跳过。
   b. 否则，设当前元素值为 x = nums[i]。它的正确位置应该是索引 x（因为最终 nums[x] 应该等于 x）。所以我们希望将 x 放到索引 x 处。
   c. 但索引 x 处当前可能有其他元素 y。我们交换 nums[i] 和 nums[x]，将 x 放到了正确位置，此时 y 被换到了索引 i 处。
   d. 现在检查被换过来的新元素 y，它的正确位置应该是索引 y。重复步骤 c，直到将要放置的元素值等于当前索引 i 处的期望值（即形成了一个环的闭合）。
2. 完成一个环的放置后，继续遍历下一个索引。

示例：nums = [3, 2, 0, 1]

• i=0: nums[0]=3, 正确位置是索引3。交换 nums[0] 和 nums[3] → [1, 2, 0, 3]。新元素1在索引0，正确位置是索引1。交换 nums[0] 和 nums[1] → [2, 1, 0, 3]。新元素2在索引0，正确位置是索引2。交换 nums[0] 和 nums[2] → [0, 1, 2, 3]。此时 nums[0]=0，环闭合。注意，这个环包含了索引0,3,1,2。
• 继续 i=1: nums[1]=1，已就位。
• i=2, i=3 也已就位。排序完成。

关键观察：每个元素最多被移动两次（一次被交换出去，一次被交换进来），总交换次数为 n - c，其中 c 是排列中的环的个数。时间复杂度 O(n)，空间复杂度 O(1)（除了循环变量）。

第二步：推广到循环偏移（nums[i] = (i + k) mod n）

现在，我们不再要求 nums[i] = i，而是要求 nums[i] = (i + k) mod n，其中 k 是给定的常数。这意味着我们希望数组最终是一个循环移位序列。例如，n=5, k=2，则目标数组应为 [2,3,4,0,1]。

如何利用循环排序的思想？我们需要重新定义“正确位置”。对于索引 i，其目标值应为 (i + k) mod n。但注意，数组元素是 0 到 n-1 的一个排列，所以每个值都会出现。我们可以反过来考虑：对于当前位于索引 i 的元素值 x，它应该被放置到哪个索引 j 才能满足最终 nums[j] = (j + k) mod n = x？解方程得到 j = (x - k + n) mod n（因为 j 在 0 到 n-1 之间）。

因此，算法调整为：

1. 遍历 i 从 0 到 n-1：
   a. 设 x = nums[i]。
   b. 计算 x 的目标位置 j = (x - k + n) % n。
   c. 如果 j == i，说明已在正确位置，跳过。
   d. 否则，进行环内交换：将 x 交换到索引 j 处，然后处理被交换过来的新元素，直到环闭合。

注意：因为每个环是独立的，我们需要确保每个元素只被处理一次。可以通过一个辅助布尔数组 visited 来标记，但这需要 O(n) 额外空间。为了保持 O(1) 空间，我们可以利用一个性质：当 n 和 k 互质时，整个排列构成一个环；否则，会形成 gcd(n, k) 个环，每个环的长度为 n / gcd(n, k)。我们可以分别处理每个环的起始点。

O(1) 空间的实现策略：

• 计算 d = gcd(n, k)。这将有 d 个环。
• 对于每个环起始索引 start = 0, 1, ..., d-1：
  1. 将 start 索引的元素值记为 x = nums[start]。
  2. 计算其目标位置 next = (x - k + n) % n。
  3. 当 next != start 时：
     • 交换 nums[start] 和 nums[next]（实际上是将 x 放到 next，把 next 原来的值拿到 start）。
     • 更新 x 为交换后位于 start 的新值。
     • 重新计算 next = (x - k + n) % n。
  4. 当 next == start 时，将 x 赋给 nums[start]（实际上在交换中已经完成），这个环处理完毕。

示例：nums = [2,3,4,0,1], n=5, k=2。我们想得到 [2,3,4,0,1] 本身（即已满足条件）。验证：d = gcd(5,2)=1，一个环。start=0, x=2, next=(2-2+5)%5=0，已就位，无需交换。但如果我们有 nums = [4,0,1,2,3]（相当于左移了），k=2，目标应为 [2,3,4,0,1]。算法过程：

• d=1, start=0, x=4, next=(4-2+5)%5=2。交换 nums[0] 和 nums[2] → [1,0,4,2,3]，x 更新为1（现在在索引0），next=(1-2+5)%5=4。交换 nums[0] 和 nums[4] → [3,0,4,2,1]，x=3, next=(3-2+5)%5=1。交换 nums[0] 和 nums[1] → [0,3,4,2,1]，x=0, next=(0-2+5)%5=3。交换 nums[0] 和 nums[3] → [2,3,4,0,1]，x=2, next=(2-2+5)%5=0，环闭合。结果正确。

第三步：推广到任意双射 f

现在考虑更一般的情况：给定一个双射 f: {0,1,...,n-1} → {0,1,...,n-1}，要求重排数组使得 nums[i] = f(i)。数组元素是 0 到 n-1 的一个排列。我们需要计算每个元素的目标位置。

对于值 x，它应该被放置到索引 j，使得 f(j) = x。由于 f 是双射，其逆映射 f⁻¹ 存在。因此，目标位置 j = f⁻¹(x)。如果我们能高效计算逆映射，算法就可以进行。

算法步骤：

1. 预先计算逆映射 inv，使得 inv[x] = f⁻¹(x)，即值 x 应该被放置到的索引。这需要 O(n) 额外空间，如果我们允许 O(n) 空间，可以直接用循环排序：
   • 遍历 i，当 nums[i] 不在正确位置时，根据 inv[nums[i]] 找到目标位置，进行环内交换。
2. 但如果要求 O(1) 额外空间，则必须要求 f 具有某种结构，使得我们能在 O(1) 时间内计算任意 x 的 f⁻¹(x)。例如 f 是线性函数：f(i) = (ai + b) mod n，其中 a 与 n 互质，则逆映射可通过模逆元计算：j = ((x - b) a⁻¹) mod n，其中 a⁻¹ 是 a 模 n 的逆元。

例子：f(i) = (3i + 1) mod 5，n=5。数组 nums 是 0..4 的一个排列。我们希望重排后满足 nums[i] = (3i+1) mod 5。计算逆映射：解 j = (3i+1) mod 5 → 3i ≡ (j-1) mod 5。由于 3 模 5 的逆元是 2（因为 32=6≡1 mod 5），所以 i = 2*(j-1) mod 5。因此 inv[x] = (2*(x-1)) mod 5。有了这个公式，我们可以在 O(1) 空间下计算目标位置。

通用算法（已知逆映射计算方式）：

1. 对于每个环起始点 start（需要找出所有环的起点，可以通过一个循环变量 i 遍历，但跳过已处理环的元素。为了 O(1) 空间，我们可以利用已处理元素的索引标记，但会破坏数组。另一种方法是利用符号位标记，但要求数组元素非负且可修改符号，本题元素是 0 到 n-1，可以加上 n 来标记，但需谨慎避免超出范围。一个更安全的方法是用 Floyd 的环检测思想，但实现较复杂。在实际应用中，如果允许 O(n) 标记空间，用 visited 数组最清晰）。
2. 在 O(1) 空间限制下，我们可以采用“循环领袖”方法：对于每个 i，如果 i 是它所在环的最小索引，则从 i 开始处理这个环。判断 i 是否为最小索引，可以在环内移动时检查是否遇到比 i 小的索引，但这会增加复杂度。通常的 O(1) 空间实现依赖于 f 的特殊结构（如循环偏移）能直接知道环的个数和起点。

简化：在面试或编程题中，通常问题会设计成 f 具有简单结构，使得环易于处理。例如 f(i) = (i + k) mod n 或 f(i) = (a*i) mod n（a 与 n 互质）。

第四步：实现示例（循环偏移情况）

以下是实现循环偏移 k 的原地 O(n) 时间、O(1) 空间算法的 Python 代码：

def cyclic_shift_sort(nums, k):
    n = len(nums)
    if n == 0:
        return
    k %= n
    if k == 0:
        return  # 无需移动
    
    from math import gcd
    d = gcd(n, k)
    
    for start in range(d):
        # 处理以 start 为起点的环
        x = nums[start]
        current = start
        while True:
            # 计算当前值 x 应该去的位置
            next_idx = (x - k + n) % n
            if next_idx == start:
                # 环闭合，放置最后一个元素
                nums[current] = x
                break
            # 将 x 放到 next_idx，取出该位置原来的值
            nums[current], x = x, nums[next_idx]
            current = next_idx
        # 注意：此时 nums[start] 尚未正确赋值，但因为在环中 start 位置是最后被赋值的，
        # 我们需要在循环结束后将 x 赋给 nums[start]？实际上在上面的交换过程中，
        # 当 next_idx == start 时，我们将 x 赋给了 nums[current]，而 current 就是 start。
        # 所以无需额外步骤。

测试：

nums = [4,0,1,2,3]
cyclic_shift_sort(nums, 2)
print(nums)  # 输出 [2,3,4,0,1]

总结

通过这个题目，我们深入理解了循环排序的核心思想：利用元素值与目标索引的映射关系，通过环内交换实现原地排序。然后将其推广到循环偏移映射，并进一步探讨了任意双射下的挑战。关键在于计算逆映射和确定环的起点，以在 O(1) 空间内完成。这个技巧在处理排列类问题时非常有用，例如“恢复数组到有序”或“生成特定排列”等场景。