排序算法之：循环排序（Cyclic Sort）的进阶应用——原地将数组元素按符号重排（正负交替）

题目描述：
给定一个整数数组 nums，它包含正整数、负整数和零，且正数与负数的数量相等（或者可能相差一个，但本题假设相等以便于构造结果）。要求在不使用额外数组的条件下，原地重排数组，使得数组的元素按照“正数、负数、正数、负数……”的顺序交替排列，并且相同符号之间的相对顺序保持不变。若正数与负数的数量不相等，则将多余的元素放在数组末尾，同时保持这些多余元素的相对顺序不变。

例如：
输入：[3, 1, -2, -4, 5, -6]
输出：[3, -2, 1, -4, 5, -6]
解释：正数 [3, 1, 5] 和负数 [-2, -4, -6] 数量相等，交替排列时正数顺序为 3, 1, 5，负数顺序为 -2, -4, -6，交替得到 [3, -2, 1, -4, 5, -6]。

第一步：问题分析与思路形成

这个问题的核心在于“交替排列”和“保持相对顺序”。如果允许使用额外空间，可以很容易地分别收集正数和负数，然后交替写入原数组。但题目要求原地操作，这增加了难度。

一种巧妙的思路是利用 循环排序（Cyclic Sort）的思想，但需要针对“交替排列”设计循环链。我们注意到，每个元素最终都有一个“目标位置”。如果我们能计算每个元素的正确位置，并逐个放置元素，就能实现原地重排。

关键观察：
假设正数有 pos_count 个，负数有 neg_count 个。定义“符号索引”：

• 所有正数应该放在偶数索引（0, 2, 4, ...），所有负数应该放在奇数索引（1, 3, 5, ...）。
• 对于一个正数，它在正数序列中的顺序是 pos_idx（从0开始），那么它的目标索引为 2 * pos_idx。
• 对于一个负数，它在负数序列中的顺序是 neg_idx，目标索引为 2 * neg_idx + 1。

因此，我们可以先遍历一次数组，统计正数和负数的数量，并记录每个正数和负数的“顺序索引”。然后再次遍历，根据上述公式计算每个元素的目标位置，进行原地放置。但原地放置时直接交换可能会破坏尚未处理的元素的顺序，因此需要一种方法保证每个元素只被移动一次。

第二步：引入“循环排序”的变种策略

循环排序的经典应用是：当数组元素范围在 [1, n] 时，通过将每个元素放到其值减1的位置上，实现排序。这里的变种是：每个元素的目标位置不是由它的值决定，而是由它的“符号类别”和“在该类别中的顺序”决定。

我们可以这样设计：

1. 遍历数组，对每个元素，判断它应该去的目标位置。
2. 如果当前位置不是目标位置，则将该元素交换到目标位置。
3. 但交换后，目标位置原来的元素可能也需要被移动，因此继续处理这个新元素，直到形成一个循环——即某个元素应该被放回当前处理的起始位置。

难点：如何在原地维护每个正数/负数在其类别中的顺序索引？
我们可以“动态”维护：用一个指针 next_pos_idx 和 next_neg_idx 分别记录下一个正数和下一个负数的放置位置。当遇到一个正数时，它应该放在 2 * next_pos_idx；遇到负数时放在 2 * next_neg_idx + 1。放置后递增对应的索引。

但是，如果直接交换，可能会打乱未处理区域。因此，我们需要一种方法，确保每个循环内的元素被正确旋转到目标位置。

第三步：详细算法步骤

我们采用“双缓冲区”循环重排的变种。由于正数和负数的目标位置是交错的，可以这样处理：

1. 用两个指针 pos_idx = 0 和 neg_idx = 0 分别表示下一个待放置的正数和负数的“逻辑位置”。
2. 从左到右遍历数组，对于每个位置 i：
   • 如果 i 是偶数，这个位置应该放正数。如果当前 nums[i] 已经是正数且符合顺序（即它是下一个该放的正数），则递增 pos_idx，继续。
   • 否则，我们需要从后面的位置找到一个“应该放在这个位置的正数”，将它交换过来。但为了保持相对顺序，这个正数必须是“下一个未放置的正数”。
3. 类似地，如果 i 是奇数，这个位置应该放负数。

但实际上，这种“找下一个”的操作可能涉及多次交换，容易出错。更稳健的方法是采用 循环引导的重排 步骤：

算法框架：

• 首先，分离正数和负数到两个数组（但为了原地，我们用两个指针模拟）。
• 然后，将两个数组“交织”到原数组。但原地交织需要复杂的旋转操作。

一个已知的高效原地算法是 “三步骤旋转法”：

1. 将数组重排为“所有正数在前，所有负数在后”，并保持各自顺序。这可以通过类似“稳定分区”的算法实现（例如使用循环旋转）。
2. 然后，用双指针从正数区和负数区的开头交替取元素，通过“块旋转”将元素放到正确位置。

但是，这种方法实现较复杂。我们采用一种更直观的 “循环分类放置” 方法（基于论文中的“完美洗牌”变种）：

具体步骤：

1. 统计正数个数 pos_count，负数个数 neg_count。

2. 确定循环数 cycle_count = min(pos_count, neg_count)。

3. 对于每个循环 k（从0开始）：

   • 当前位置 i = 2 * k（偶数位，应放正数）。
   • 保存 nums[i] 到临时变量 temp。
   • 用循环将“应该放在 i 位置的元素”逐步移动到正确位置，直到回到起始位置。

   这里“应该放在 i 位置的元素”如何确定？
   我们需要知道当前 i 位置的“正确元素”是哪个。
   实际上，我们可以预先将正数和负数分别提取到两个列表（但这里要求原地，所以需要一种映射）。

由于实现细节较复杂，我们给出一个简化但清晰的 使用额外空间 版本，然后讨论如何去除额外空间。

第四步：实现（带额外空间的清晰版本）

def rearrange_alternating_with_extra(nums):
    pos = [x for x in nums if x > 0]
    neg = [x for x in nums if x < 0]
    # 假设正负数量相等，或忽略多余部分
    n = len(nums)
    pos_idx, neg_idx = 0, 0
    for i in range(n):
        if i % 2 == 0 and pos_idx < len(pos):
            nums[i] = pos[pos_idx]
            pos_idx += 1
        elif i % 2 == 1 and neg_idx < len(neg):
            nums[i] = neg[neg_idx]
            neg_idx += 1
    # 如果正负数不等，将多余元素放在末尾（此处省略，因为题目假设相等）
    return nums

第五步：尝试原地化（无额外空间）

原地化的关键是如何在不使用额外列表的情况下，获取“下一个正数”和“下一个负数”。我们可以通过 “标记已处理” 的方式模拟。

一个技巧：用“索引映射”来追踪每个元素的目标位置。对于每个位置 i，它的目标位置是：

• 如果 nums[i] > 0：目标位置 = 2 * (在正数中的顺序索引)。
• 如果 nums[i] < 0：目标位置 = 2 * (在负数中的顺序索引) + 1。

我们可以第一遍扫描，给每个正数和负数标记它们的“顺序索引”（用一个辅助数组存储目标索引）。然后第二遍执行循环排序，根据辅助数组将元素放到目标位置。但这需要 O(n) 额外空间。

为了真正原地，可以利用数字的正负性来存储“顺序索引”？但数字本身有正负，很难复用符号位。

第六步：一个可行的原地算法（基于循环旋转）

算法思路：

1. 用两个指针 pos = 0, neg = 0 分别指向下一个待放置的正数和负数位置（在原数组中）。
2. 从左到右遍历，如果当前位置 i 应该放正数但放着负数（或反之），则从后面找到下一个该符号的元素，将它旋转到当前位置。

具体步骤：

• 如果 i 是偶数，应该放正数：
  • 如果 nums[i] > 0，继续。
  • 否则，从 j = max(i+1, pos) 开始找下一个正数，找到后，将子数组 nums[i:j+1] 循环右移一位（这样正数移到 i，其余元素顺序后移）。
• 类似处理奇数位置。

此方法保持相对顺序，但时间复杂度可能较高（最坏 O(n^2)）。但可以优化：用指针 pos 和 neg 记录下一个可用正数/负数的位置，避免重复扫描。

第七步：优化到 O(n) 时间且 O(1) 空间的方法

实际上，这是一个经典的“数组交织”问题。已知有 O(n) 时间、O(1) 空间的算法，但实现复杂。其核心是 “循环领导算法”，利用数论性质确定每个元素的最终位置，然后进行环状替换。

但考虑到篇幅和可理解性，我们给出一个实用的 O(n) 时间、O(1) 空间 简化方案（假设正负数数量相等）：

1. 将数组重排为“正数在前，负数在后”，保持顺序（可用稳定分区算法，如“循环旋转”实现，O(n) 时间）。
2. 然后用双指针 p1 = 0, p2 = pos_count（正数区开始和负数区开始）。
3. 交换 p1+1 和 p2，然后 p1 += 2, p2 += 1，直到交织完成。

但交换会打乱顺序吗？
不会，因为每次交换将一个负数移到正数区中间，正数区未被交换的元素顺序不变，负数区顺序也不变。

示例：

正数区: [3, 1, 5]  负数区: [-2, -4, -6]
交换步骤：
1. 交换索引1和3： [3, -2, 5, 1, -4, -6]
2. 交换索引3和4： [3, -2, 5, -4, 1, -6]
3. 交换索引4和5： [3, -2, 5, -4, 1, -6]（实际上不需要，因为已经交替）

但结果中正数顺序是 3,5,1，不符合原顺序 3,1,5——这是因为交换破坏了正数区的顺序。
所以此简单交换法不满足“保持相对顺序”。

第八步：总结与扩展

该问题展示了循环排序思想在非数值排序场景下的灵活应用。虽然我们未能给出一个简短的完美原地算法，但解题过程涵盖了：

1. 问题分析：确定目标位置映射。
2. 循环排序思想：通过循环链将元素放置到正确位置。
3. 保持顺序的挑战：需要稳定操作。
4. 原地化尝试：通过指针和旋转减少空间使用。

实际面试或应用中，若允许 O(n) 空间，则使用分离再交织的方法；若严格要求原地，可查阅“完美洗牌”或“数组交织”的高效算法，它们基于数论和循环分解，实现较为复杂。

通过这个题目，你不仅能加深对循环排序的理解，还能学会将排序思想应用于更复杂的重排问题，并在空间限制下寻求最优解。