调整数组顺序使奇数位于偶数前面的稳定解法与扩展

1. 题目到底想考什么：先看清需求再动手

“剑指offer-68、调整数组顺序使奇数位于偶数前面（二）”，别看题目不长，它在面试题里算是很典型的“看起来简单、做起来容易翻车”的题目。核心场景是这样的：给你一个整数数组，要求把所有奇数放到前面，偶数放到后面，并且相对顺序要保持稳定——也就是说，原本在前面的奇数调整后依然在前面，原本在前面的偶数调整后依然在前面。这里括号里的“（二）”其实暗示了它和基础版本的区别：基础版只要求“前奇后偶”的区间分布，不要求相对顺序；而进阶版多了一个稳定性的约束，难度一下就上来了。

这个问题本身的价值在哪？它考的绝不只是“你会不会写两次遍历”，而是三件事：第一，你有没有理解稳定排序的意义；第二，你手上有没有不止一种解法；第三，你写代码时对边界条件的敏感度怎么样。很多人在面试中五分钟搞定一个双指针交换版本，结果面试官追问“如果要求保持相对顺序怎么办”，当场发懵。所以这篇文章我想把这个题从暴力、优化、稳定版本到泛化扩展一层层拆开，讲清楚每个方案背后的取舍和适用场景。

适合谁看？准备算法面试的同学、复习数组操作的朋友，以及工作中遇到“按条件重新分区但又不能打乱原顺序”这类需求的开发人员。不管你是刚接触算法题的初学者，还是刷题已经有一段时间的进阶选手，这篇文章都能给你提供可直接复用的思路和代码。

2. 解题思路拆解：为什么这个问题不简单

2.1 先删掉最笨的办法：额外数组遍历

最容易想到的办法当然是创建两个临时数组，一个装奇数，一个装偶数，然后依次遍历原数组，判断每个元素的奇偶性，分到对应数组里，最后把“奇数数组 + 偶数数组”合并回来。这个方案的正确性没有任何问题，时间复杂度和空间复杂度都是O(n)，逻辑几乎是直白的。我见过很多人第一次上手就是这种写法，面试时也不会被判错。它能保证相对顺序，对于“（二）”这个带稳定性要求的版本，这其实是一个完全可用的答案。

但问题是，这个解法太“无脑”了。面试官后续一定会追问：“能不能在O(1)额外空间下完成？”这时候如果只会这一种解法，场面就会比较尴尬。从学习角度说，这种解法真正价值在于验证你对题意的理解——它把问题拆成了“分区 + 合并”两个子问题。先跑一遍实现，确保自己理解没有偏差，再往下深挖更好的解法，这样的学习路径反而是效率最高的。

为什么我会先提这个简单版本？因为在实战中，最快的解法不一定是最好的，但最稳的解法往往能帮你先拿下一道题的基础分。尤其在笔试环节，时间紧张的情况下，一个O(n)空间、O(n)时间的解法已经能解决大多数判题用例，剩下的优化属于锦上添花而非雪中送炭。

2.2 双指针头尾交换：快但是不稳定

再看经典的“头尾指针交换法”。定义两个指针，left从数组头部开始，right从尾部开始；left向右移动直到遇到偶数停下，right向左移动直到遇到奇数停下；然后交换这两个位置的元素，继续循环，直到left >= right。这个方案的时间复杂度是O(n)，空间复杂度是O(1)，而且思路非常经典，在很多教材里都被当作例题讲。

关键在于，这种方案是不稳定的。举个例子：假设数组是[1, 2, 4, 3, 5, 6]。left先指向索引1（值为2），right从尾部左移到索引4（值为5），交换后数组变成[1, 5, 4, 3, 2, 6]。然后left继续右移到索引2（值为4），right继续左移到索引3（值为3），再交换，数组变成[1, 5, 3, 4, 2, 6]。你看，原本在索引1位置的偶数2，被交换到了索引4位置，原本在索引4位置的奇数5被换到了索引1。奇数和偶数的“块”是分开了，但奇数之间的相对顺序已经乱了：原本3在5后面，现在3在5前面。偶数之间也一样，原本2在4前面，现在2在4后面。

所以，这个经典解法只适用于基础版，不能直接拿来做“（二）”。如果你面试时只写出这个版本，却没有主动提稳定性问题，面试官一旦追问就会很被动。我建议的思路是：先讲双指针版本能解决“不要求稳定”的版本，然后主动指出这个方案的稳定性缺陷，再引出稳定版本的实现，这样整个回答的层次感就出来了。

2.3 直接找稳定版本的核心矛盾

稳定版本的核心矛盾在于：既要O(1)额外空间，又要保持相对顺序。数组的“原地”操作本身就很容易破坏顺序，因为你在交换元素时跨越了距离。要在不借助额外数组的情况下保持稳定性，最直观的思路是“把偶数往后挪，把奇数往前插”。

具体怎么做？维护一个变量oddTail，表示已经处理好的奇数区间的末尾位置。然后从左到右遍历数组，遇到奇数时，把它前面的所有偶数整体向后移动一个位置，然后把当前奇数放到oddTail的位置，oddTail加1。这个过程类似于“插入排序”的局部挪移，最坏时间复杂度为O(n^2)，空间复杂度仍为O(1)。但要注意，题目要求“（二）”版本的复杂度如果没有额外说明，通常希望你能给出更优策略。好在稳定的O(n)版本也有，那就是借用额外数组的那个方案——它用O(n)空间换来了稳定性。所以这个问题的本质其实是时间、空间、稳定性三者之间的取舍，没有绝对最优，只有根据约束条件选一个平衡点。

3. 手写实现：一步一步把稳定版代码写出来

3.1 Python 实现：冒泡思想原地稳定版

先上代码。这个实现适合在 O(1) 空间要求下保持稳定性，我把它叫“局部腾挪法”。

def reorder_odd_even_atable(nums): if not nums or len(nums) <= 1: return nums n = len(nums) # odd_tail 表示当前已放置好的奇数的下一个位置 odd_tail = 0 for i in range(n): if nums[i] % 2 == 1: # 把当前奇数从位置 i 移动到 odd_tail 位置 # 先把 nums[i] 保存下来 cur = nums[i] # 将 [odd_tail, i-1] 区间整体右移一位 for j in range(i, odd_tail, -1): nums[j] = nums[j - 1] nums[odd_tail] = cur odd_tail += 1 return nums

过程很好理解：从左往右扫描，遇到奇数时，它前面如果有一串偶数，就整体往后挪一位，给这个奇数腾出一个位置来。这样每次插入奇数时都不会跨过其他奇数，所以相对顺序一定保持稳定。试着跑一下：[2, 4, 1, 3]。初始化 odd_tail = 0。i=0，nums[0]=2，偶数，跳过。i=1，nums[1]=4，偶数，跳过。i=2，nums[2]=1，奇数，保存cur=1，然后将位置1和0的元素都往后挪，挪完后数组变成[2, 4, 4]，把cur放到位置0，数组变成[1, 2, 4]，odd_tail变成1。i=3，nums[3]=3，奇数，保存cur=3，将位置2和位置1的元素（4和2）依次后移，数组变成[1, 2, 2, 4]，把cur放到位置1，得到[1, 3, 2, 4]。可以看到奇数1和3的相对顺序没变，偶数2和4的相对顺序也没变——稳定达成。

这个方案最坏情况下逆序数组（所有奇数都在所有偶数后面）会触发显著挪移，时间复杂度接近O(n^2)。如果面试官明确要求O(n)时间，那这个方案就不够看了。

3.2 Python 实现：额外数组稳定版（时间优先）

需要O(n)时间时，用额外数组。代码非常干净：

def reorder_odd_even_stable(nums): if not nums or len(nums) <= 1: return nums odds = [] evens = [] for x in nums: if x % 2 == 1: odds.append(x) else: evens.append(x) return odds + evens

这段代码虽然简单，但它的关键在于：遍历一次数组，奇数依次放入odds列表，偶数依次放入evens列表，天然保留了稳定特性。最后拼接两个列表就完成了。这种方式在工程上非常常见，因为很多真实业务里数组规模不大，空间充裕，稳定性和代码可读性比那一点额外内存更值钱。

3.3 C++ 实现：原地版与标准库风格

如果你用C++打比赛或者面试，原地挪移版可以这么写：

void reorderArray(vector<int>& nums) { int n = nums.size(); int oddTail = 0; for (int i = 0; i < n; i++) { if (nums[i] & 1) { // 位运算判断奇数，效率更高 int cur = nums[i]; for (int j = i; j > oddTail; j--) { nums[j] = nums[j - 1]; } nums[oddTail++] = cur; } } }

这里额外想提一个位运算的小知识：判断一个整数是否为奇数，用x & 1比x % 2更快。因为取模运算符在底层涉及除法运算，而按位与直接对最低比特位做判断，性能更好。在算法题里这种微优化可能影响不大，在真正的大循环高频调用场景里，差距会比较明显。这也是热词里提到“奇数字节”相关问题的观察角度之一——字节是8位，最低位为1就是奇数，为0就是偶数，和整数判断本质是一致的。

4. 泛化扩展：从奇偶判定到任意划分函数

4.1 用高阶函数封装判奇偶逻辑

好的代码不止要解决一道题，还要能复用。也许明天需求就变成“把所有负数放前面”、“把所有能被3整除的放前面”、“把所有质数放前面”——如果每次重写整个排序逻辑，那就是重复劳动了。所以更好的方式是把这个判断条件抽象成一个函数参数，我们把核心排序逻辑和高层判断逻辑解耦。

先定义一个基础接口：

from typing import List, Callable def reorder_with_condition(nums: List[int], should_move_front: Callable[[int], bool]) -> List[int]: if not nums or len(nums) <= 1: return nums result = [] # 第一轮收集满足条件的元素 for x in nums: if should_move_front(x): result.append(x) # 第二轮收集其余元素 for x in nums: if not should_move_front(x): result.append(x) return result def is_odd(x: int) -> bool: return x % 2 == 1

调用方式：reorder_with_condition(nums, is_odd)。以后想改规则，比如要负数在前，就可以写lambda x: x < 0，再传给同一个函数。这个设计的好处是：排序逻辑本身的稳定性由函数内部保证，无论判断条件怎么换，都不会影响正确的相对顺序。

如果你追求更严谨的工程化写法，还可以把它写得和 C++ 的std::stable_partition对齐。实际上 C++ 标准库就有这个函数，专门做稳定分区，内部实现就是类似思路，只是它针对的是任意迭代器区间。面试时如果提到自己熟悉std::stable_partition，并和这道题联系起来，会是个加分项。

4.2 变体：负数在前、被3整除的在前等

我看到很多资料里把这道题当作“奇偶划分”，但它的本质其实是“二分分区”。我们只需改变判定函数，就能派生出一整个题目家族。

比如“把负数放在非负数前面，且保持相对顺序稳定”。测试数据 [-3, 4, -1, 0, 5, -2]。期望结果应该是 [-3, -1, -2, 4, 0, 5]。写法就是把should_move_front换成x < 0。没有任何其他变化。

再比如“把能被3整除的放在不能被3整除的前面，保持稳定”。输入 [6, 2, 9, 4, 3, 1]，期望输出 [6, 9, 3, 2, 4, 1]。同理。

这种变体题在面试中出现频率极高，因为它能从基础题延伸出大量子问题，侧面考察代码的可扩展性。我在实际面试候选人时，经常先让候选人解决奇偶问题，然后立刻追加“如果换成负数在前呢？”如果候选人答“再写一个函数”，那我会继续问“那如果每个星期换一个规则，你怎么设计？”这时候能说出“把判断条件抽成参数”的候选人，代码能力明显强一档。

4.3 从数组扩展到字符串或字节流的奇偶处理

热词里有个有趣的点：“为什么socket接收到奇数字节，后面会补一个随机数”。这个问题虽然不是剑指offer原题，但它背后的思维方式完全一致——我们不仅要对数组里的整数做奇偶判断，还会对字节流、数据包、文件内容做各种基于奇偶性的处理。我简单解释一下：socket通信中，如果应用层协议要求数据按固定长度对齐（比如偶数长度封包），而底层传来的数据刚好是奇数字节，可能需要在末尾补填充字节，这个填充值有时候是零，有时候是随机数——这取决于协议定义。如果你把每个字节看成一个小整数，那么“判断奇偶”就是用byte & 1 == 1来判断。所以这也算是奇偶判断在工程领域的实际落地，能让我们把算法题和真实业务场景串起来。

热词里还有“如何在一列excel数据中提取奇数列数据”。这个问题本质上也是奇偶判定：把列索引拿出来，判断列号除以2的余数是否为1。可以用Excel的MOD(COLUMN(), 2)=1，也可以写个简单脚本按列遍历。同样的判定逻辑，用在数组索引、列号、字节上，抽象层级不同，思维模型相同。

5. 常见问题与排查技巧实录

5.1 边界条件吃大亏：空数组、单元素、全是奇数、全是偶数

不管哪种解法，边界条件都是最容易扣分的地方。先说空数组和单元素数组，很多代码在遍历前没判空，直接就用下标访问，轻则报错，重则越界。我的习惯是任何数组类算法题，开头三行先处理空和长度小于等于1的情况，这样后续逻辑可以假设数组至少有两个元素，思维负担小一些。

再说全奇数和全偶数的情况。测试时要专门验证：如果全是奇数，odd_tail会一路增长到n，最终数组不变；如果全是偶数，odd_tail一直是0，数组也不变。这两种情况都不该报错，且结果要和原数组完全一致。书写时要注意，odd_tail只在遇到奇数时才增加，所以全奇数时会正确递增，不会越界；全偶数时odd_tail保持0，也不会异常。这里最容易出错的其实是“腾挪”版本：当odd_tail和i相等时，内层循环不需要执行，直接把奇数放到当前位置，这就是天然的正确行为。我曾经见过有人为了省掉这个判断添加额外的复杂度，反而弄出了Bug。

5.2 稳定性验证：交换法写完后，拿小样本逐条核对

关于稳定性，我建议写完代码后不要急着提交，先拿一个小的反例数组在纸上走一遍。比如[1, 4, 3, 2, 5]如果目标结果是[1, 3, 5, 4, 2]，那就说明奇数之间相对顺序未变，偶数之间也未变。双指针交换法跑出来的可能是[1, 5, 3, 4, 2]，奇数5和3的顺序反了，一下就露馅了。这个验证过程很值钱，因为面试官不一定每次都会提醒你验证稳定性，但一旦结果和预期不一致，一眼就能看出问题。

我在实际刷题时也常常碰到一种现象：在网上搜题解，发现有些博客给出的“指针交换法”被误称为稳定算法。这是不对的。要分清楚“快排分区”和“stable_partition”的区别。快排自身是不稳定的，而stable_partition专门保证稳定性。所以看到任何说“双指针法稳定”的文章，都要留个心眼。

5.3 面试的坑：别在没审清要求时用错方案

面试中最大的坑，是没听清楚题目的限制条件就开写。基础版如果只要求“前奇后偶”，那双指针交换法是最优解；进阶版加了“相对顺序稳定”，双指针交换法直接不合格；如果再加“时间复杂度O(n)”，那么原地腾挪版也出局了，只能选额外数组版。所以拿到题目先复述一遍：“您是说需要奇数都在偶数前面，同时保持它们原有相对顺序，对吗？是否有空间复杂度限制？”这种确认看起来琐碎，实际上反而是专业度的体现。

顺便说一句，我在面试中见过不少候选人在这道题上栽跟头，不是因为代码写得有问题，而是因为对整个题目的变体没有体系化认知。如果你能把“基础版、稳定版、O(n)时间版、泛化函数版”全部讲一遍，基本上这道题就拿下了。我在实际面试候选人时，经常先让候选人解奇偶问题，然后立刻追加“如果换成负数在前呢？”如果候选人答“再写一个函数”，那我会继续追问“那如果每个星期换一个规则，你怎么设计？”这时候能说出“把判断条件抽成参数”的候选人，代码能力明显强一档。

5.4 常见问题与排查速查表

关于“负数取模”那一条我要特别提醒一下。Java里-3 % 2的结果是 -1 而不是 1，如果你用x % 2 == 1来判断奇数，负数奇数会被误判为偶数。这就解释了为什么很多 C++/Java 代码里判断奇数都用x & 1而不是x % 2 == 1。我在实际面试中见过不止一次候选人在这个问题上踩坑。Python 的取模行为是向负无穷取整，-3 % 2 == 1成立，所以用== 1没问题。写代码时一定要先明确语言特性，再用合适的写法。这个细节看似很小，但足以让测试样例直接翻车。

6. 扩展与延伸：奇偶判断在真实场景中的那些变体

6.1 奇偶+排列组合：比如“求07所能组成的奇数个数”怎么想

热词里有一个挺有意思的问题：“求07所能组成的奇数个数”。我猜这里的意思是给定数字0和7，用它们组成若干位数（可能每位可重复，也可能需要排列），求能组成多少个奇数。这个问题的核心依然是奇偶判断——奇数必须有1、3、5、7、9等奇数做末位。在这个给定集合里，只有7是奇数，所以能组成的奇数个数取决于末位固定为7时，前面位数的排列方式有多少种。如果每位可从0和7中选，且末位为7，那么前面每一位都有2种选择，总数为2^(n-1)。和数组调整问题相比，同样用到“末位奇偶决定整体奇偶”这一直觉，只是从“数组位置分区”变成了“数字组合计数”。

这种交叉联想对面试特别有帮助，因为面试官一旦考察“奇数”相关话题，可能从完全不同的角度出题：数组分区、组合计数、字符串数字验证……所有题目背后都是奇偶性这一基础数学性质。如果我们能熟练地从一个题目迁移到另一个题目的判断逻辑，举一反三的能力就体现出来了。

6.2 奇偶判断用于ASCII、字节补位和数据筛选

热词里还提到了“任意输入一个字符，判断其ascii是否是奇数，若是输出yes，否则输出no”。本质上就是ord(char) % 2 == 1或ord(char) & 1 == 1。字符的ASCII码是个整数，最低比特位是1时，它就是奇数。这个题的思路和剑指offer这道数组题其实共用同一个“奇偶判定”引擎。

“如何在一列excel数据中提取奇数列数据”，同样是把列索引做奇偶判断。用Excel公式可以做，比如用辅助列=MOD(COLUMN(), 2)，筛选输出结果为1的列；或者用Python的pandas，按df.columns[::2]来选奇数列（注意索引从0开始时的偏移）。这让我想到，很多人以为算法题只存在于面试题集里，其实奇偶判定在后端数据处理、报表生成、字段对齐等业务中非常常见。

6.3 稳定性需求在工程场景中的真实案例

最后补充一个工程场景。假设你在维护一个订单列表，每个订单有一个状态码，需要把所有“已支付”状态的订单排在“未支付”之前，且每个状态内部依然按时间先后排序。如果直接使用不稳定的快排分区，用户会看到订单顺序被随机打乱，体验极差。而使用稳定分区，状态调整后原有的时间顺序依然保留，这就是stable_partition的意义。因此，剑指offer这道题并不是单纯的刷题游戏，它在真实业务中的映射比比皆是。

7. 总结与自己的心得

这道“调整数组顺序使奇数位于偶数前面（二）”我刷过很多遍，每次都有新的体会。当初我刚开始刷题时，只会写额外数组版，觉得这题实在简单，后来面试时被问到“能否原地且稳定”，才意识到自己远远没吃透。

我自己在实际项目中，最常用的是“判断条件函数化 + 两次遍历”的组合方案。原因很简单：稳定性有保障，时间复杂度O(n)可控，而且代码可读性非常高，团队成员接手时没有理解成本。只有在硬性要求“O(1)额外空间”时，我才会用局部腾挪版并接受O(n²)的最坏时间。

最后再分享一个小技巧：平时刷题时，可以把同一道题的多个变体整理在一个文档里，每个变体只改判定函数那一行。比如奇偶版、正负版、整除版、质数版，全部用同一个框架去套。这样练习一个月后，你再看到任何“把满足X条件的元素放前面”的题目，基本不用想直接写，因为你的代码结构已经把判断逻辑抽象好了。这种抽象能力，比会背一道题的解法重要得多。