题目描述
思路解析
一句话答案：LeetCode 905 按奇偶排序数组：允许任意顺序，就用对撞双指针在原地分区——左指针遇偶右移、右指针遇奇左移、左奇右偶就交换，一趟分好，时间 O(n)、空间 O(1)。
把偶数全挪到奇数前面，要返回什么才算数
给一个整数数组 nums，重排它，让所有偶数排在所有奇数前面，返回满足条件的任一数组即可；偶数、奇数各自谁先谁后都不管。题面 nums=[3,1,2,4]，输出 [4,2,1,3]，其实 [2,4,3,1] 也算对，只要偶在前奇在后。再看 nums=[0]，单个元素直接返回 [0]。「任一」是重点：不排序、也不强求稳定。
先分两个表再拼起来，差在哪儿
扫一遍 nums，偶数进一个表、奇数进另一个表，最后两表拼回去，答案就有了。逻辑没错，时间也是 O(n)，可这一路白开了两个和 nums 一样长的表，多花 O(n) 额外空间。题目只要偶在前奇在后、不追究具体顺序，这份空间能省掉。
凭什么两个指针相向走一趟就能分好
既然允许任意顺序，就不必搬新表，直接在原数组上把偶数拨到左、奇数拨到右。摆两个指针：i 从最左、j 从最右，相向往中间走。i 只要停在偶数上就往右迈、j 只要指着奇数就往左退；只有 i 指奇数、j 指偶数、两边都站错时才交换，双双归位后再各进一步。一头一尾对着夹，中间没分好的窗口越缩越小，碰上就分完。在原数组上按一个判定拆成两段，就是对撞双指针原地分区。
左指针右指针，各自碰到什么才动
每一轮先看 i：nums[i] 是偶数（nums[i] % 2 == 0）就站对，i 右移；不是偶数，再看 j，nums[j] 是奇数（nums[j] % 2 == 1）也站对，j 左移；两条都不满足，只剩 i 指奇数、j 指偶数这一种，交换 nums[i] 与 nums[j]，随后 i 右移、j 左移。循环条件是 i 比 j 小，等两者相遇或错开就停下返回 nums。判断先后有讲究：先放过站对的偶数、再退走站对的奇数，剩下的才是「左奇右偶」那种一换解决俩的情形；右边站对的奇数别硬换，否则会把归位的奇数又拖回窗口。
[3,1,2,4] 分两步落位，一步一步看
起手 i 指向下标 0、j 指向下标 3。nums[0]=3 奇数，i 不动；nums[3]=4 偶数、非奇数，j 也不退；落到交换，nums[0] 和 nums[3] 对调，数组变成 [4,1,2,3]，i 到下标 1、j 到下标 2。第二轮 nums[1]=1 奇、nums[2]=2 偶，又交换，nums[1] 和 nums[2] 对调，数组成 [4,2,1,3]，i 到下标 2、j 到下标 1。这时 i 比 j 大，循环停，返回 [4,2,1,3]——偶数 4、2 在前，奇数 1、3 在后，偶在前奇在后就对了。
循环条件用 i 小于等于 j，会白空转一轮
i 和 j 合起来只把数组从两头扫过一遍，时间 O(n)；全程只多用 i、j 两个下标、就地交换，空间 O(1)。几种边界都不触发交换、原样返回就对：单元素如 nums=[0]，i 和 j 起手同位，条件 i 比 j 小不成立，一轮不进直接返回；全是偶数则 i 右移到头、全是奇数则 j 左移到头，都不交换。收尾一个爱写错的点：循环写成 i 小于等于 j，等 i、j 落到同一元素上还会多进一轮，对已定的位置空转，改成 i 比 j 小才干净。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「左偶就 i++、右奇就 j--、左奇右偶就交换」，下面每一帧都在套它。
双指针就位：i（左指针）站在下标 0，j（右指针）站在下标 7。中间紫色窗口是还没分好的区域。我们要让窗口里的偶数都流到左边、奇数都流到右边。
先看左指针。nums[0] = 3 是奇数，奇数该去右边，这一位站错了，先记着它，再去看右指针。
再看右指针。nums[7] = 7 也是奇数，而奇数本来就该待在右边，这一位其实是站对的。
左边奇数虽然站错，但右边是个已经站对的奇数，没法跟它换。所以先把右指针 j 往左收一格，把这个奇数定下来。
j 退到下标 6。下标 7 的 7 归入右边的奇数区（蓝色）。左指针那个奇数下一轮再处理。
先看左指针。nums[0] = 3 是奇数，按规矩它该去右边，是个站错位的。
再看右指针。nums[6] = 8 是偶数，按规矩它该来左边，也是个站错位的。两个刚好反着。
这是最划算的一步：左边的奇数和右边的偶数一交换，两个就都各就各位了。准备交换。
换完：下标 0 变成偶数 8，下标 6 变成奇数 3，都站对了。于是 i 右移到 1、j 左移到 5，窗口同时缩小两头。
先看左指针。nums[1] = 2 是偶数，偶数本来就该待在左边，这一位已经站对了。
既然左指针指的是偶数、位置正确，就不用动它，直接让 i 往右迈一步，去检查下一个。
i 走到下标 2。下标 1 的 2 正式归入左边的偶数区（绿色）。继续看新的左指针。
先看左指针。nums[2] = 1 是奇数，奇数该去右边，这一位站错了，先记着它，再去看右指针。
再看右指针。nums[5] = 5 也是奇数，而奇数本来就该待在右边，这一位其实是站对的。
左边奇数虽然站错，但右边是个已经站对的奇数，没法跟它换。所以先把右指针 j 往左收一格，把这个奇数定下来。
j 退到下标 4。下标 5 的 5 归入右边的奇数区（蓝色）。左指针那个奇数下一轮再处理。
先看左指针。nums[2] = 1 是奇数，按规矩它该去右边，是个站错位的。
再看右指针。nums[4] = 6 是偶数，按规矩它该来左边，也是个站错位的。两个刚好反着。
这是最划算的一步：左边的奇数和右边的偶数一交换，两个就都各就各位了。准备交换。
换完：下标 2 变成偶数 6，下标 4 变成奇数 1，都站对了。于是 i 右移到 3、j 左移到 3，窗口同时缩小两头。
两个指针在下标 3 撞上了，中间再没有未处理的元素，循环停止。此刻左边四个全是偶数、右边四个全是奇数。
分区完成：绿色 8、2、6、4 都是偶数，蓝色 1、5、3、7 都是奇数。偶在前、奇在后，这就是一个合法答案。
边界先想清：单元素、全偶、全奇，三种都不会发生交换，原样返回即可。
两个高频追问：一是和快排 partition 同源，二是稳定性与空间的取舍。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def sortArrayByParity(self, nums: List[int]) -> List[int]: i, j = 0, len(nums) - 1 while i < j: if nums[i] % 2 == 0: i += 1 elif nums[j] % 2 == 1: j -= 1 else: nums[i], nums[j] = nums[j], nums[i] i, j = i + 1, j - 1 return nums复杂度
- 时间：O(n)，i 与 j 合起来只把数组扫过一遍
- 空间：O(1)，原地交换，只用 i、j 两个下标
易错点
面试追问把动画讲成自己的话
追问这题和「快速排序的分区（partition）」有什么关系？
追问如果还要求偶数之间保持原有相对顺序（稳定）怎么办？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
按奇偶排序数组 II
LeetCode 922 · 简单 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题