按奇偶重排数组为什么适合用对撞指针？

简化版

按奇偶重排数组可以用对撞指针原地完成。

左指针找不应该在左侧的奇数，右指针找不应该在右侧的偶数，然后交换。

每次交换后继续向中间收缩，直到左右指针相遇。

详细版

目标是让偶数在前、奇数在后，不要求保持相对顺序。

设置 left = 0、right = n - 1。当 nums[left] 是偶数时，左指针右移；当 nums[right] 是奇数时，右指针左移。若左边是奇数、右边是偶数，就交换两者。

这个过程类似快速排序的 partition，只不过分区条件是奇偶性。

时间复杂度 O(n)，空间复杂度 O(1)。如果题目要求稳定排序，就不能简单交换，需要额外空间或更复杂的原地稳定算法。

完整版教学

一、这题本质是数组分区

题目不是要完整排序，而是把数组按条件分成两段：前面满足偶数，后面满足奇数。只要分区正确，段内顺序无所谓。因为目标弱于排序，所以不需要 O(n log n)，线性扫描就够。

记忆钩子：只分两类，不排大小，先想 partition。

二、对撞指针的不变量

用两个指针从两端向中间走：

[0, left) 已经是偶数区
(right, n-1] 已经是奇数区
[left, right] 是未知区

每一步都扩大已处理区域。如果左端已经是偶数，它属于正确区域；如果右端已经是奇数，它也属于正确区域。只有左奇右偶时，两边都放错了，交换一次能同时修复两个位置。

三、为什么交换是安全的

当 nums[left] 是奇数，nums[right] 是偶数时，左边元素应该去右区，右边元素应该去左区。交换后两个位置都满足目标区域要求。因为题目不要求稳定性，交换不会破坏答案定义。

左侧元素	右侧元素	操作
偶数	任意	`left++`
任意	奇数	`right--`
奇数	偶数	交换

这个策略保证每轮至少移动一个指针。

四、代码模板

实现如下：

function sortArrayByParity(nums) {
  let left = 0
  let right = nums.length - 1
  while (left < right) {
    while (left < right && nums[left] % 2 === 0) left++
    while (left < right && nums[right] % 2 === 1) right--
    if (left < right) {
      ;[nums[left], nums[right]] = [nums[right], nums[left]]
      left++
      right--
    }
  }
  return nums
}

内部两个 while 用来跳过已经在正确区域的元素。交换后移动指针，是因为交换来的两个位置已经处理完。

五、和快速排序 partition 的关系

快速排序 partition 按照“是否小于 pivot”分区，本题按照“是否为偶数”分区。两者都不关心分区内部顺序，只关心左区和右区是否满足条件。理解这个关系后，遇到负数/正数、0/非0、满足条件/不满足条件的原地分区题，都能复用。

partition(nums, predicate)
左侧：predicate 为 true
右侧：predicate 为 false

这就是更一般的抽象。

六、常见误区与追问

误区：使用完整排序。 排序能得到结果但成本更高，也改变了不必要的相对大小关系。
误区：交换后不移动指针。 已经修复的位置继续参与判断，可能造成重复工作。
误区：忽略稳定性要求。 如果要求偶数和奇数内部相对顺序不变，普通交换法不适用。
追问：如果要求奇偶交替排列怎么办？ 那是另一类题，需要按下标奇偶位置放元素，不是简单前后分区。
追问：负数取模怎么办？ JavaScript 中 -3 % 2 是 -1，判断奇偶更稳可用 Math.abs(x % 2) 或 x % 2 !== 0。

这些点说明你知道分区题的适用边界。

七、加强记忆

按奇偶重排记成“左找错的奇数，右找错的偶数，交换”。整个过程中左侧已处理区全是偶数，右侧已处理区全是奇数，中间是未知区。只要题目不要求稳定性，对撞指针就是最省空间的线性方案。若题目要求保序，就要主动说明需要换方案。

简化版

详细版