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]走一遍初始left0, right3。nums[0]3是奇数nums[3]4是偶数条件满足交换后数组变成[4, 1, 2, 3]。接着判断nums[left]4是偶数left移到 1nums[right]3是奇数right移到 2。此时left1, right2nums[1]1是奇数nums[2]2是偶数交换后变成[4, 2, 1, 3]。left移到 2right移到 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]走一遍fast0nums[0]1奇数跳过。fast1nums[1]3奇数跳过。fast2nums[2]2偶数和nums[0]交换数组变[2, 3, 1, 4]slow1。fast3nums[3]4偶数和nums[1]交换数组变[2, 4, 1, 3]slow2。结果[2, 4, 1, 3]偶数顺序是2, 4和原数组一致稳定成立。这个版本我第一次见的时候有点懵因为“交换”这个动作看起来会打乱顺序但实际上被换到后面的元素都是奇数而奇数之间的顺序本来就不关心。偶数之间的顺序由fast的扫描顺序保证所以稳定性没被破坏。理解这一点你就真正吃透了这道题。4. 完整实操流程与多语言实现对照4.1 从零到一的解题步骤我把完整的解题流程拆成五步你可以照着走一遍。第一步明确输入输出。输入是一个整数数组输出是重排后的数组。先确认题目是否要求原地修改这决定了你能不能新建数组。第二步判断奇偶的写法。统一用x % 2 0判偶x % 2 ! 0判奇。不要用位运算x 1去炫技除非你确认输入都是非负整数因为负数在补码表示下 1的结果虽然也能判奇偶但可读性差团队协作时容易引起争议。第三步选解法。无稳定性要求选头尾夹逼有稳定性要求选快慢指针允许额外空间且追求代码最简选新建数组。第四步处理边界。空数组直接返回单元素数组直接返回全偶或全奇数组要保证不越界、不死循环。第五步验证。至少跑四组用例全偶、全奇、奇偶交替、已经合法。这四组能覆盖绝大多数边界。4.2 多语言实现对照不同语言写这道题细节差异还挺大的我整理成表格方便对照。语言交换写法判偶写法注意事项Pythona, b b, ax % 2 0元组交换天然安全Java临时变量三步交换x % 2 0数组是引用传递原地生效Cstd::swap(a, b)x % 2 0vector 传引用避免拷贝Goa, b b, ax % 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.0xO(n)稳定头尾夹逼0.7xO(1)不稳定快慢指针0.9xO(1)稳定头尾夹逼最快因为它平均只需要扫描一半的元素就能让两个指针相遇。快慢指针要完整扫一遍所以稍慢。新建数组虽然也是扫两遍但有额外的内存分配和拷贝开销反而最慢。这个数据告诉我们一个反直觉的结论省空间的解法不一定慢费空间的解法不一定快。头尾夹逼同时做到了最快和最省空间代价是牺牲稳定性。所以如果你的场景不需要稳定没有任何理由不用它。提示上面是相对值具体倍数跟语言、数据分布、机器都有关系不要当成绝对结论。但“头尾夹逼常数最小”这个趋势在大多数语言里都成立。5. 常见问题排查与避坑经验实录5.1 高频报错速查表我把这道题在刷题和面试中遇到的高频问题整理成表方便你对照排查。现象可能原因解决方向结果里奇数跑到前面判偶条件写反检查% 2 0是否用对死循环不结束交换后指针没移动确保每轮至少一个指针前移数组越界right初始值写成len(nums)应为len(nums) - 1负数判断出错用% 2 1判奇改用% 2 ! 0结果不稳定用了头尾夹逼换快慢指针版本部分元素没处理循环条件用了或提前退出检查left right5.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) 空间那个变种会逼着你重新思考分区的边界。