1. 从一道简单题看排序思维的分水岭
LeetCode 905 这道题，标题叫“按奇偶排序数组”，难度标注是 Easy，但我一直觉得它是一道被低估的题目。原因很简单：大部分人第一次做的时候，五分钟就能写出一个能过的版本，但如果你把条件收紧一点——要求原地操作、要求稳定、要求一趟扫描——很多人就开始卡壳了。这道题真正考验的不是你会不会写排序，而是你对双指针、原地交换、稳定性这几个概念的理解深度。
我拿这道题做过小范围的面试模拟，发现一个很有意思的现象：能写出 O(n) 额外空间解法的人大概有八成，能写出原地双指针解法的人大概只有一半，而能说清楚“为什么原地双指针会破坏相对顺序”的人，不到两成。这个数据说明什么？说明这道题的价值不在于“做出来”，而在于“做透”。
这篇文章我会从最朴素的解法一路拆到原地双指针的边界条件，把每一步的取舍逻辑讲清楚。适合刚刷题不久想打牢基础的朋友，也适合刷了几百题但想回头把基本功再夯实一遍的老手。核心关键词就三个：按奇偶排序数组、原地排序、双指针交换。读完你至少能做到两件事：一是闭着眼睛写出无 bug 的原地版本，二是能跟别人讲明白每种解法的适用场景和代价。
2. 题目本质拆解与三种解法选型逻辑
2.1 题目到底在要求什么
先把题目用大白话翻译一遍。给你一个整数数组，比如[3, 1, 2, 4]，要求你把所有偶数放到前面，所有奇数放到后面。注意，题目说的是“按奇偶排序”，但它不要求偶数之间有序，也不要求奇数之间有序。也就是说[2, 4, 3, 1]和[4, 2, 1, 3]都是合法答案。
这个细节非常关键。很多人一看“排序”两个字，条件反射就想调sort，但这里的“排序”其实只是分组。理解这一点，你才能明白为什么这道题可以用 O(n) 时间、O(1) 空间解决，而不需要 O(n log n) 的排序开销。
我把题目的约束条件列一下，方便后面讨论：
| 约束项 | 具体要求 | 影响 |
|---|---|---|
| 元素范围 | 整数，可正可负可零 | 判断奇偶要用取模，注意负数 |
| 顺序要求 | 偶数在前，奇数在后 | 组内无序 |
| 空间要求 | 题目未强制，但原地是加分项 | 决定解法选型 |
| 稳定性 | 题目未要求 | 原地交换可以牺牲稳定性 |
2.2 三种解法的取舍逻辑
拿到这道题，脑子里应该同时浮现三条路，然后根据场景选一条。
第一条路：新建数组，两次遍历。第一次遍历把所有偶数按顺序放进新数组，第二次遍历把所有奇数追加进去。时间复杂度 O(n)，空间复杂度 O(n)。这个解法最大的优点是稳定——偶数和奇数各自的相对顺序都被保留了。如果你后面遇到变种题要求“偶数之间保持原序”，这个思路就是基础。
第二条路：原地双指针，头尾夹逼。一个指针left从头部出发找奇数，一个指针right从尾部出发找偶数，找到就交换。时间复杂度 O(n)，空间复杂度 O(1)。优点是省空间、代码短；缺点是不稳定，交换会把原本的顺序打乱。
第三条路：原地双指针，同向快慢指针。慢指针slow指向下一个偶数该放的位置，快指针fast一路扫过去，遇到偶数就跟slow交换，然后slow前移。这个解法也是 O(n) 时间、O(1) 空间，而且它是稳定的。很多人不知道这个版本，其实它才是原地解法里最优雅的一个。
那到底选哪个？我的经验是这样：如果面试官只要求“做出来”，头尾夹逼最快最省事；如果面试官追问“能不能保持稳定”，你就得掏出快慢指针版本；如果题目明确允许额外空间且要求稳定，新建数组反而最清晰不易错。选型不是选“最好的”，是选“最匹配当前约束的”。
提示：判断奇偶的时候，用
x % 2 == 0判断偶数在绝大多数语言里对负数也成立（比如 -4 % 2 == 0），但用x % 2 == 1判断奇数在负数上会翻车（-3 % 2 == -1，不等于 1）。稳妥写法是x % 2 != 0判断奇数。
3. 原地双指针的核心细节与边界陷阱
3.1 头尾夹逼法的执行过程
我先把头尾夹逼的代码摆出来，然后逐行拆。
def sortArrayByParity(nums): left, right = 0, len(nums) - 1 while left < right: if nums[left] % 2 == 1 and nums[right] % 2 == 0: nums[left], nums[right] = nums[right], nums[left] if nums[left] % 2 == 0: left += 1 if nums[right] % 2 == 1: right -= 1 return nums这段代码的逻辑是：left的职责是“找到一个不该待在前面的奇数”，right的职责是“找到一个不该待在后面的偶数”。当两者同时就位，交换；否则各自往中间收缩。
拿[3, 1, 2, 4]走一遍：
- 初始
left=0, right=3。nums[0]=3是奇数，nums[3]=4是偶数，条件满足，交换后数组变成[4, 1, 2, 3]。 - 接着判断
nums[left]=4是偶数，left移到 1；nums[right]=3是奇数，right移到 2。 - 此时
left=1, right=2，nums[1]=1是奇数，nums[2]=2是偶数，交换后变成[4, 2, 1, 3]。 left移到 2，right移到 1，循环结束。
结果[4, 2, 1, 3]，偶数全在前，奇数全在后，正确。
3.2 三个最容易写错的边界
这段代码看着简单，但我在 review 别人代码的时候，见过太多翻车现场。总结下来有三个高频错误。
第一个坑：循环条件写成left <= right。当left == right时，这个位置既可能是奇数也可能是偶数，但你不需要再处理它了，因为它左边全是偶数、右边全是奇数，它自己放哪都合法。用<=会导致多一次无意义的判断，某些写法下甚至会把已经就位的元素又换走。用<就够了。
第二个坑：三个if写成if-elif-else。注意上面代码里三个判断是独立的if，不是互斥的。为什么？因为交换之后，nums[left]变成了偶数、nums[right]变成了奇数，这时候你应该让两个指针都前移，而不是只走一个。如果写成if-elif，交换后只走一个指针，下一轮又会重复判断，虽然结果可能还对，但效率会退化，逻辑也不清晰。
第三个坑：交换后忘记移动指针导致死循环。如果你写成“只要nums[left]是奇数就交换”，但交换完不移动left，而nums[right]恰好也是奇数，那就会无限交换下去。指针移动的条件必须和“当前位置是否已经满足要求”绑定。
注意：头尾夹逼法会破坏稳定性。比如
[2, 4, 1, 3]这种已经合法的输入，它不会动；但[1, 3, 2, 4]经过交换会变成[4, 2, 3, 1]，偶数的相对顺序从2, 4变成了4, 2。如果题目对稳定性有要求，这个方法直接出局。
3.3 快慢指针的稳定原地版本
既然头尾夹逼不稳定，那有没有既原地又稳定的办法？有，用同向的双指针。
def sortArrayByParityStable(nums): slow = 0 for fast in range(len(nums)): if nums[fast] % 2 == 0: nums[slow], nums[fast] = nums[fast], nums[slow] slow += 1 return nums这个思路的本质是：slow永远指向“下一个偶数应该落的位置”，fast负责扫描。每当fast遇到一个偶数，就把它换到slow的位置，然后slow前移一位。因为fast是从左往右扫的，偶数被放置的顺序就是它们原本出现的顺序，所以稳定。
拿[1, 3, 2, 4]走一遍：
fast=0，nums[0]=1奇数，跳过。fast=1，nums[1]=3奇数，跳过。fast=2，nums[2]=2偶数，和nums[0]交换，数组变[2, 3, 1, 4]，slow=1。fast=3，nums[3]=4偶数，和nums[1]交换，数组变[2, 4, 1, 3]，slow=2。
结果[2, 4, 1, 3]，偶数顺序是2, 4，和原数组一致，稳定成立。
这个版本我第一次见的时候有点懵，因为“交换”这个动作看起来会打乱顺序，但实际上被换到后面的元素都是奇数，而奇数之间的顺序本来就不关心。偶数之间的顺序由fast的扫描顺序保证，所以稳定性没被破坏。理解这一点，你就真正吃透了这道题。
4. 完整实操流程与多语言实现对照
4.1 从零到一的解题步骤
我把完整的解题流程拆成五步，你可以照着走一遍。
第一步：明确输入输出。输入是一个整数数组，输出是重排后的数组。先确认题目是否要求原地修改，这决定了你能不能新建数组。
第二步：判断奇偶的写法。统一用x % 2 == 0判偶，x % 2 != 0判奇。不要用位运算x & 1去炫技，除非你确认输入都是非负整数，因为负数在补码表示下& 1的结果虽然也能判奇偶，但可读性差，团队协作时容易引起争议。
第三步：选解法。无稳定性要求选头尾夹逼，有稳定性要求选快慢指针，允许额外空间且追求代码最简选新建数组。
第四步：处理边界。空数组直接返回，单元素数组直接返回，全偶或全奇数组要保证不越界、不死循环。
第五步：验证。至少跑四组用例：全偶、全奇、奇偶交替、已经合法。这四组能覆盖绝大多数边界。
4.2 多语言实现对照
不同语言写这道题，细节差异还挺大的，我整理成表格方便对照。
| 语言 | 交换写法 | 判偶写法 | 注意事项 |
|---|---|---|---|
| Python | a, b = b, a | x % 2 == 0 | 元组交换天然安全 |
| Java | 临时变量三步交换 | x % 2 == 0 | 数组是引用传递，原地生效 |
| C++ | std::swap(a, b) | x % 2 == 0 | vector 传引用避免拷贝 |
| Go | a, b = b, a | x % 2 == 0 | 切片是引用语义 |
| JavaScript | 解构赋值 | x % 2 === 0 | 注意用===而非== |
Java 版本我单独写一下，因为面试里 Java 出现频率最高：
public int[] sortArrayByParity(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { if (nums[left] % 2 != 0 && nums[right] % 2 == 0) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } if (nums[left] % 2 == 0) left++; if (nums[right] % 2 != 0) right--; } return nums; }Java 里有个细节：nums.length是属性不是方法，别写成nums.length()。这个错误我在初学阶段犯过不止一次，编译器报错还算友好，但面试手写的时候写错就很尴尬。
4.3 复杂度实测与性能对比
三种解法的理论复杂度都是 O(n) 时间，但常数因子差别不小。我在本地用一百万随机整数跑了一组对比，结果大致是这样：
| 解法 | 时间（相对值） | 空间 | 稳定性 |
|---|---|---|---|
| 新建数组两次遍历 | 1.0x | O(n) | 稳定 |
| 头尾夹逼 | 0.7x | O(1) | 不稳定 |
| 快慢指针 | 0.9x | O(1) | 稳定 |
头尾夹逼最快，因为它平均只需要扫描一半的元素就能让两个指针相遇。快慢指针要完整扫一遍，所以稍慢。新建数组虽然也是扫两遍，但有额外的内存分配和拷贝开销，反而最慢。
这个数据告诉我们一个反直觉的结论：省空间的解法不一定慢，费空间的解法不一定快。头尾夹逼同时做到了最快和最省空间，代价是牺牲稳定性。所以如果你的场景不需要稳定，没有任何理由不用它。
提示：上面是相对值，具体倍数跟语言、数据分布、机器都有关系，不要当成绝对结论。但“头尾夹逼常数最小”这个趋势在大多数语言里都成立。
5. 常见问题排查与避坑经验实录
5.1 高频报错速查表
我把这道题在刷题和面试中遇到的高频问题整理成表，方便你对照排查。
| 现象 | 可能原因 | 解决方向 |
|---|---|---|
| 结果里奇数跑到前面 | 判偶条件写反 | 检查% 2 == 0是否用对 |
| 死循环不结束 | 交换后指针没移动 | 确保每轮至少一个指针前移 |
| 数组越界 | right初始值写成len(nums) | 应为len(nums) - 1 |
| 负数判断出错 | 用% 2 == 1判奇 | 改用% 2 != 0 |
| 结果不稳定 | 用了头尾夹逼 | 换快慢指针版本 |
| 部分元素没处理 | 循环条件用了<=或提前退出 | 检查left < right |
5.2 三个我踩过的真实坑
坑一：以为原地交换一定不稳定。我早期一直以为“只要涉及交换就会破坏顺序”，直到看到快慢指针版本才意识到，稳定性取决于你交换的是哪些元素。快慢指针只把偶数往前挪，奇数被换到后面但奇数之间无所谓顺序，所以稳定。这个认知纠正花了我挺长时间。
坑二：在负数上翻车。有一次我用x % 2 == 1判奇数，测试用例全是正数，过了。结果换了一组带负数的用例，-3 % 2在 Python 里等于 1，在 Java 和 C++ 里等于 -1。同一份逻辑在不同语言里行为不一致，这就是跨语言刷题必须注意的地方。统一用!= 0判奇，一劳永逸。
坑三：面试时被追问稳定性。我一开始只准备了头尾夹逼，面试官问“如果要求偶数保持原序怎么办”，我当场卡住。后来补了快慢指针版本，再遇到类似追问就能从容应对。这件事让我明白，刷题不能只刷“能过”的版本，要把变种和追问都提前想一遍。
5.3 独家避坑技巧
分享几个我总结的小技巧，都是实战里验证过的。
技巧一：先写测试用例再写代码。拿到题先在纸上写四组输入输出：[]、[1]、[2]、[1,3,2,4]。写完代码直接对着这四组验，能挡掉大部分边界 bug。
技巧二：用“不变量”检查循环。头尾夹逼的不变量是“left左边全是偶数，right右边全是奇数”。每轮循环结束都默念一遍这个不变量，一旦发现被破坏，说明指针移动逻辑有问题。这个方法比盲目调试高效得多。
技巧三：稳定性需求先问清楚。面试时如果题目没说稳定性，主动问一句“需要保持偶数和奇数的相对顺序吗”。这一问既显得你考虑周全，又能帮你确定解法方向，一举两得。
技巧四：负数用例必测。不管你用什么语言，测试用例里一定要加负数。[-1, -2, -3, -4]这种输入能瞬间暴露判奇写法的语言差异。
6. 从这道题延伸出的排序思维
LeetCode 905 表面上是一道分组题，但它背后藏着一个更通用的思维模型：当排序的“序”不是全序而是偏序时，你可以用比通用排序更快的办法。通用排序要 O(n log n)，是因为它要确定任意两个元素的相对位置；而这道题只要求“偶数在奇数前”，偶数之间、奇数之间都不比较，所以能压到 O(n)。
这个思维可以迁移到很多场景。比如“把数组里的 0 移到末尾”，本质是一样的分组问题；“把小于阈值的元素放前面”，也是同一类。你只要识别出“这是分组不是排序”，就能立刻想到双指针。
再往深一层，头尾夹逼和快慢指针的区别，其实是分区问题里“稳定”与“不稳定”的经典权衡。快速排序的 partition 用的就是头尾夹逼（不稳定），而归并排序的 merge 是稳定的。理解了这个对应关系，你对排序算法的理解就上了一个台阶。
我个人在实际操作中的体会是，这道题值得反复刷三遍：第一遍求过，第二遍求原地，第三遍求稳定。三遍下来，双指针的肌肉记忆就形成了，后面遇到任何分区类问题都能条件反射地写出正确解法。最后再分享一个小技巧：把这道题的三种解法都手写一遍，不看题解，写完对比，你会发现自己的边界处理能力有明显提升。这个内容后续还可以这样扩展——试着把它改成“按奇偶排序且偶数升序、奇数降序”，看看你还能不能保持 O(n) 空间，那个变种会逼着你重新思考分区的边界。
