1. 题目解析两个版本的差异在哪里1.1 这个题到底在考什么这道题在《剑指Offer》里通常对应面试题21有的整理版本里会标成第68题题号对不上很正常别因为这个影响心态。题面很简单输入一个整数数组要求调整数组中数字的顺序让所有奇数排在所有偶数前面。比如输入 [1,2,3,4]输出可以是 [1,3,2,4] 或 [3,1,2,4]只要是奇数整体在前、偶数整体在后就算对。一句话提炼的话这是一个“按奇偶性做类别分区”的数组重排问题。但题目标的“(二)”很关键它意味着要求比基础版更高——版本一只要求奇数在前偶数在后不care奇数内部和偶数内部的相对顺序版本二额外要求调整之后奇数之间的先后顺序不能变偶数之间的先后顺序也不能变。也就是说如果原数组是 [1,2,5,4,8,7,6]版本一只管输出 [1,5,7,2,4,8,6] 这类结果版本二则必须输出 [1,5,7,2,4,8,6]这里 1、5、7 的相对顺序和 2、4、8、6 的相对顺序都和原数组保持一致。很多人在牛客、力扣上刷这道题时拿到的题面其实是两个版本的合集。力扣原题 LCOF 21 通常只要求“不保证稳定”但有些公司的笔试题会专门加一句“要求保持原有相对顺序”。面试的时候经常是先让你写不稳定版本再追问一句“如果要求稳定怎么办”。所以这两个版本都得熟练掌握而且脑子里要清楚哪一个解法是稳定的哪一个是不稳定的为什么。1.2 版本一与版本二的核心区别我用一句话先给结论版本的差别本质上是“只分区”和“分区且保持稳定”的差别。稳定这个词在排序领域的意思是如果两个元素的值相同或者说在当前比较规则下“等价”那么排序后它们的相对位置不能变。放到这道题里两个奇数之间并没有大小关系但我们仍然要求数组在调整之前哪个奇数排在前面调整之后它还得排在前面。偶数同理。这个差异直接影响了算法选择版本一不要求稳定可以用首尾双指针一趟遍历时间复杂度 O(n)额外空间 O(1)代码极其简洁版本二要求稳定单靠“一头一尾”两个指针解决不了。哪怕你换用快慢指针同向走也只能保证“当前扫描过的奇数被依次放在前面”但偶数内部顺序容易被打乱。想要稳定要么开额外数组要么借助类似插入排序原地挪动时间或空间上总得付一点代价。所以别把这两个版本混为一谈。面试官问“你还能优化吗”“你还能原地吗”实际上就是在考察你清不清楚这个稳定性的约束条件。下面我按版本逐一拆解各种解法代码用 Python 为主关键处补充 C/Java 版本思路。2. 不稳定解法双指针从两端逼近2.1 首尾双指针的思路版本一的经典做法是双指针从数组两端同时向中间扫描。左指针指向数组开头右指针指向数组末尾然后做三件事左指针往右走直到遇到一个偶数停下来右指针往左走直到遇到一个奇数停下来交换这两个位置的数左指针继续往右走右指针继续往左走。重复这个过程直到左指针和右指针相遇数组就调整完了。每次交换都把“左边不该出现的偶数”和“右边不该出现的奇数”各自送到对方的位置上所以一趟走完奇数全部集中在左侧偶数全部集中在右侧。一个容易理解的生活类比想象一班学生按学号坐在教室老师要求“男生坐左边女生坐右边”但不要求男生内部按学号排。最简单高效的办法就是左边走到第一个女生时停住右边走到第一个男生时停住让他们俩换座位一直重复直到所有人归位。交换的过程中不关心同性别之间的先后顺序所以特别快。2.2 复杂度分析和为什么它不稳定这个解法的时间复杂度是 O(n)因为左右指针加起来一共遍历了数组一遍每个元素最多被交换一次。额外空间只需要一个临时变量O(1)。从工程角度讲这已经是最优的时间空间组合了。但注意它不稳定。为什么因为交换操作会直接改变奇数和偶数内部原本的相对位置。举个例子输入 [2,1,3,4]初始左指针在 2偶数右指针在 4偶数右指针继续左移到 3奇数交换 2 和 3得到 [3,1,2,4]左指针右移到 1奇数继续右移到 2偶数停住右指针左移到 1奇数停住此时左指针已经越过右指针循环结束。结果 [3,1,2,4] 中两个偶数 2 和 4 的顺序还是 [2,4]没变两个奇数 3 和 1 的相对顺序是 [3,1]但原数组是 [1,3]已经变了。所以如果你遇到的是版本二直接套双指针是不过关的。这时候需要换思路。很多刚刷题的人在这里栽跟头我也一样第一次被问“能稳定吗”的时候愣了一下心想功能不是实现了吗。后来才明白“功能对了”和“满足所有约束条件”是两码事算法题里最怕的就是默认一些条件不存在。3. 稳定解法保持奇数内部顺序不变的几种路子3.1 额外数组最简单也最稳版本二最直观的解法是开两个新数组或者一个数组扫描两遍第一遍把所有奇数按顺序收集起来第二遍把所有偶数按顺序收集起来最后拼接。如果你不想用两个数组也可以用“一个结果数组 两个指针”的写法先从左往右扫一遍原数组把奇数依次放进结果数组的前半段再从左往右扫一遍原数组把偶数依次放进结果数组的后半段。两次扫描结果数组长度与原数组相同额外空间 O(n)。时间也是 O(n)因为第一遍扫描处理奇数时不会跳过偶数第二遍扫描处理偶数时也不会跳过奇数两个完整循环。这个方案为什么稳定因为两次扫描都是按原数组从左到右的顺序选取元素的奇数被选出来的顺序和原数组里奇数的顺序完全一致偶数同理。所以原数组里奇数相对顺序、偶数相对顺序都保留下来了。以 [1,2,3,4,5,6] 为例第一遍选出奇数 [1,3,5]第二遍选出偶数 [2,4,6]拼接得 [1,3,5,2,4,6]。没有破坏任何相对位置。这个方案的问题只有一个需要 O(n) 的额外空间。面试时如果题目明确不限制空间这几乎是最稳的写法甚至不容易写错。边界情况也少空数组直接返回空结果数组全是奇数时第二遍扫描结果为空没问题全是偶数时第一遍扫描结果为空也没问题。我在面试时一般先写这个版本因为好说话、好解释。但写完一定会补一句“如果要求原地完成不用额外空间我还有另一种思路。”3.2 原地解法插入排序的思路如果面试官追问“能不能原地完成”那就要把思路切到“插入排序”上。核心思想是用一个指针 i 记录“当前已经排好的奇数区域的末尾”也就是下一个奇数应该放的位置。另一个指针 j 从左往右扫描数组每遇到一个奇数就把它往前面“插入”到 i 位置同时把 i 到 j-1 之间的所有元素整体右移一位。这个过程类似插入排序里的“把新元素往前插后面元素顺次后移”。因为所有元素都是相邻移动没有“远距离交换”所以奇数之间的相对顺序、偶数之间的相对顺序都不会变。具体步骤初始化oddEnd 0表示下一个奇数要放的下标从j 0开始遍历数组如果nums[j]是奇数就先把这个奇数暂存到临时变量然后从oddEnd到j-1的元素整体右移一位再把暂存的奇数放到oddEnd位置最后oddEnd如果nums[j]是偶数什么都不做继续往后扫。以 [2,1,3,4] 为例j0nums[0]2偶数跳过j1nums[1]1奇数暂存1将 oddEnd0 到 j-10 的元素也就是2右移一位数组变为 [2,2,3,4]把1放到位置0数组变为 [1,2,3,4]j2nums[2]3奇数暂存3将 oddEnd1 到 j-11 的元素也就是2右移一位数组变为 [1,2,2,4]把3放到位置1数组变为 [1,3,2,4]j3nums[3]4偶数跳过。结果是 [1,3,2,4]奇数 1、3 相对顺序不变偶数 2、4 相对顺序不变完美。时间复杂度是 O(n^2)因为每次遇到奇数都可能触发一段连续元素的整体右移最坏情况是数组前半段全是偶数、后半段全是奇数比如 [2,4,6,8,1,3,5]每个奇数都要把前面一大段偶数往后挪挪动次数是 1234 这种等差数列量级总复杂度 O(n^2)。空间是 O(1)只用一个临时变量。我做笔试题时一般不会首选它因为 O(n^2) 在大数据量下会超时。但在面试场景里面试官要的不是最优时间而是“你能不能想到原地稳定的方法并解释清楚时间空间的取舍”。这个解法能展示你对“稳定排序”和“插入排序”这些基础概念的掌握。补充一个升级思路如果你学过“归并排序”会发现这里也可以用归并的思路做稳定分区。把数组不断二分先处理左半区和右半区再合并。合并时只有一种情况需要处理左半区末尾存在偶数段右半区开头存在奇数段。此时用“局部反转三次”的方式可以把这两段互换位置同时保证两段内部的顺序不变。这个方法的复杂度是 O(n log n)空间 O(1)递归栈不算。比插入排序法效率高但写起来复杂不少适合想冲击高难度追问的读者。我说实话如果没有事先练过面试中当场写这段代码容易翻车不如额外数组版本来得干脆。解法是否稳定时间复杂度额外空间适用场景首尾双指针交换否O(n)O(1)版本一、内存敏感场景双数组收集是O(n)O(n)版本二、不限制空间插入排序式移位是O(n²)O(1)版本二、要求原地且数据量小归并式稳定分区是O(n log n)O(1)版本二、要求原地方案且数据量大4. 代码实现与实操细节4.1 版本一代码实现首尾双指针版本一的代码非常短Python 写法如下def reorder_array(nums): if not nums: return nums left, right 0, len(nums) - 1 while left right: # 左指针向右移动找到第一个偶数 while left right and nums[left] % 2 1: left 1 # 右指针向左移动找到第一个奇数 while left right and nums[right] % 2 0: right - 1 # 交换偶数左边和奇数右边 if left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1 return nums这段代码里有两个细节值得说。一是内层 while 必须加left right条件否则数组全是奇数或全是偶数时左指针或右指针会越界。比如输入全奇数的 [1,3,5]左指针一路加到 right1内层循环还在找偶数就会IndexError。二是外层循环在交换后主动让两个指针同时向内移动一步这是一个优化可以跳过刚交换过的位置减少一次无用的扫描判断。不加也完全正确加了效率更好。Java 版本几乎一样的结构public void reorder(int[] nums) { if (nums null || nums.length 0) return; int left 0, right nums.length - 1; while (left right) { while (left right (nums[left] 1) 1) left; while (left right (nums[right] 1) 0) right--; if (left right) { int tmp nums[left]; nums[left] nums[right]; nums[right] tmp; left; right--; } } }这里用(nums[left] 1) 1代替% 2 1按位与运算在编译器层面通常比取模快那么一丁点而且它在负数场景下行为一致不会出现“负奇数模2等于-1”这种边界困扰。刷题和笔试里这么写不算炫技是常见的优化习惯。4.2 版本二代码实现双数组与原地双数组版实现如下def reorder_array_stable(nums): odds [] evens [] for num in nums: if num % 2 1: odds.append(num) else: evens.append(num) return odds evens这段代码极简但面试时可能要解释为什么它满足稳定性遍历是从左到右的append 操作把所有奇数和偶数分别按原顺序收进列表拼接时各自内部顺序不变。需要注意一点如果面试官要求“在原数组上修改并返回原数组”不能新建列表后直接返回新对象要先把结果写回nums。示范一下def reorder_array_stable_inplace(nums): result [0] * len(nums) idx 0 # 第一遍收集奇数 for num in nums: if num % 2 1: result[idx] num idx 1 # 第二遍收集偶数 for num in nums: if num % 2 0: result[idx] num idx 1 # 写回原数组 for i in range(len(nums)): nums[i] result[i]这个写法额外空间仍然 O(n)但对调用方来说数组对象没变在某些语言里更符合“修改输入”的预期。原地插入移位版def reorder_array_stable_inplace_shift(nums): if not nums: return nums odd_count 0 # 已排好的奇数个数也是下一个奇数要放的下标 for i in range(len(nums)): if nums[i] % 2 1: # 如果当前轮到的位置就是奇数区的末尾直接计数并继续 # 否则需要把这段区间右移 temp nums[i] # 从 odd_count 到 i-1 之间的元素整体右移一位 for j in range(i, odd_count, -1): nums[j] nums[j - 1] nums[odd_count] temp odd_count 1 return nums内层循环的写法range(i, odd_count, -1)是从 i 往 odd_count 方向倒着拷贝这样不会覆盖还没移动的元素。我见过有人用它替代nums[odd_count:i1] nums[odd_count-1:i]后者是 Python 的切片赋值虽然也能实现整体右移但切片会新建临时列表等于额外占用 O(i-odd_count) 的空间原地性就打了折扣。所以在“原地”这个前提下用逐个倒着拷贝更纯粹。4.3 边界条件和常见坑边界条件主要就三类空数组、全奇数、全偶数。这三类情况所有解法都能正确兼容但要注意版本一的双指针解法在“空数组”时直接return nums就好不要用len(nums)-1做循环条件不然 right 变成 -1直接跳过循环也没问题但新手容易在返回前对空数组做交换操作那就崩了。另一个坑是“奇偶判定”。直接用num % 2 1判断奇数在 C/C/Java 里对于负数有问题比如-3 % 2在多数语言里结果是-1不等于1于是把 -3 当成了偶数。这个问题面试官偶尔会设置陷阱所以稳妥的做法是判断num % 2 ! 0而不是 1。Python 的%运算结果是正余数-3 % 2 1成立但为了跨语言的代码习惯建议一律写成num % 2 ! 0。如果你在用位运算判断(num 1) 1这个写法对所有整数语言都成立因为它是直接看最低二进制位是不是 1与正负无关。我还踩过一个很隐蔽的坑版本一的双指针交换之后如果交换的是相邻两个数且下一次循环左指针刚好指向一个偶数、右指针刚好指向一个奇数会再次交换形成死循环。举例 [2,1]left0 指向2right1 指向1交换一次变成 [1,2]此时如果不把 left/right 往里收下一次外层循环 left 还是0指向1right 还是1指向2内层循环 left 会走到1因为 nums[0]1 是奇数它继续后移right 会走到0因为 nums[1]2 是偶数它继续前移left 已经不小于 right循环退出结果 [1,2] 是正确的。但如果交换后不做left / right--内层循环有可能出现同一对元素再次被交换的边界情况所以说为了避免无谓逻辑交换后就收缩指针是更稳的写法。5. 面试追问与实战避坑5.1 变体把奇偶换成任意判定条件面试官不会满足于“奇数偶数”。最常见的追问是如果是负数在前、正数在后呢如果先排能被3整除的数呢如果第一步先排奇数偶数第二步再排正负呢这种题其实考的是“解耦”。把判定条件抽成一个函数而不是写死在主循环里。比如def is_odd(num): return num % 2 ! 0 def reorder(nums, condition): left, right 0, len(nums) - 1 while left right: while left right and condition(nums[left]): left 1 while left right and not condition(nums[right]): right - 1 if left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1 return nums这样传入不同的condition就能应对不同规则。比如负数在前condition lambda x: x 0能被3整除的在前condition lambda x: x % 3 0。这种“把判断条件参数化”的做法在《剑指Offer》里是一个高频考点官方解析里也专门强调过思路扩展。面试时你主动写出这种可扩展版本通常比直接写死奇偶判断要加分。如果你遇到的是稳定版本同样可以抽条件。额外数组法的判断条件抽成is_odd(num)插入移位法的判断条件也抽成is_odd(num)其他逻辑完全不变。所以把核心逻辑和具体规则解耦之后两个版本都能无缝复用。5.2 和同类题目的横向比较这道题在力扣上对应的是“LCR 139训练计划I”或者剑指 Offer 21不同平台题号不同。但“调整数组顺序使奇数位于偶数前面”的核心思想在后续很多题目里都能看到影子比如荷兰国旗问题三色排序、按颜色分类、把0放在数组末尾、甚至某些快排 partition 的变体。荷兰国旗问题实际上就是“把数组按某个标准分成三段”而这道题是“分成两段”。理解了双指针分区的思想后续做“移动零”力扣283就很顺。移动零要求把数组里的 0 全部移到末尾同时保持非零元素的相对顺序——它本质上是这道题的稳定版本只不过“奇数”换成“非零元素”“偶数”换成“0”。我当时刷移动零时直接用这道题的稳定版思路一行都不多改就过了。这也说明“稳定 分区”这个组合在算法题里出现的频率相当高。另外这道题和“数组中的逆序对”“稳定排序”都有联系。如果你在面试中被问到归并排序的稳定性特点可以拿这道题当例子“稳定指的是值相同的元素排序后相对顺序不变而奇偶分区则要求不同类别也保持原序两者可以结合。”这种跨知识点的联想能力比死记硬背解法更能打动面试官。5.3 实际刷题时的场景与建议我自己的经验是不要一上来就背答案先把“版本一”默认的约束条件和“版本二”额外加的约束条件分清楚。再去做题时每一道关于数字分类的题都问自己三个问题需不需要稳定性题目有没有说“保持相对顺序”能不能用额外空间题目有没有说“原地操作”数据规模大概多大O(n²) 会不会超时这三个问题想清楚解法基本直接浮现。如果没想清楚就动手很可能写完一个版本被追问“加个条件怎么办”心态一崩就容易卡壳。我踩过的另一个坑是只练了版本二的双数组法结果面试官说不准用额外空间一下哑火。所以建议两个版本的至少三种解法都要手写一遍尤其要动手写“插入移位”这种有点别扭的原地稳定算法。手写的时候特别注意内层右移循环的边界别写成了for j in range(odd_count, i)这样拷贝方向错了会覆盖数据。正确写法是从后往前移动即把nums[i]空出来之后nums[i] nums[i-1]nums[i-1] nums[i-2]直到odd_count位置被空出来。这类实现细节只有自己多写几遍才能形成手感光看别人的代码很容易觉得自己会了一上手就错。最后分享一个调试技巧写完代码后拿几个极端用例跑一遍。我最常用的测试集是[][1][2][1,2,3,4,5][2,4,6,8,1,3,5][1,3,5,2,4,6][-1,-2,3,4,-5]跑通这些用例边界和稳定性基本都能验证到。刷题不是目的真正花时间的应该是把每个解法的原理和边界都吃透这样面试时不管怎么追问你都能接得住。我个人在实际刷题中最深的体会就是稳定性这道坎早晚要迈过去与其在面试现场被问住不如现在就把它想明白。