CS-Notes 剑指 Offer 21：调整数组顺序使奇数位于偶数前面（稳定分区）两种实现与复杂度分析

本文基于 CS-Notes 仓库中 notes/21. 调整数组顺序使奇数位于偶数前面.md 展开，讲解这道"稳定分区"变体题的约束条件、两种完整解法（新数组法 O(N) 时间 / O(N) 空间，冒泡上浮法 O(N²) 时间 / O(1) 空间），并结合仓库中快排 partition 的实现，说明它与不稳定分区的本质区别。读完后你能掌握：如何在不改变同类元素相对顺序的前提下完成数组分区，以及空间换时间与原地交换两条路线的取舍。

题目描述：先看清楚约束条件

原题出自《剑指 Offer》第 21 题，在 剑指 Offer 题解 - 目录.md 中被归入"排序"分类。

这道题的约束与书本版本不一样，原文档特别强调了这一点：

需要保证奇数和奇数，偶数和偶数之间的相对位置不变，这和书本不太一样。例如对于 [1,2,3,4,5]，调整后得到 [1,3,5,2,4]，而不能是 {5,1,3,4,2} 这种相对位置改变的结果。

也就是说，这是一个**稳定分区（stable partition）**问题：

• 结果中所有奇数必须排在所有偶数前面；
• 奇数之间的相对顺序保持原样（1 在 3 前、3 在 5 前）；
• 偶数之间的相对顺序也保持原样（2 在 4 前）。

这个"稳定性"约束是选择算法路线的关键依据。如果不要求稳定，经典的双指针对向交换法（一次扫描、O(N) 时间、O(1) 空间）就足够了，其思路与快排的 partition 切分完全同构——仓库中 notes/算法 - 排序.md 里就给出了快排切分的完整实现：

private int partition(T[] nums, int l, int h) {
    int i = l, j = h + 1;
    T v = nums[l];
    while (true) {
        while (less(nums[++i], v) && i != h) ;
        while (less(v, nums[--j]) && j != l) ;
        if (i >= j)
            break;
        swap(nums, i, j);
    }
    swap(nums, l, j);
    return j;
}

该实现通过左右指针不断交换"错位"元素来完成分区，但它不保证稳定性——交换会打乱同类元素的先后关系。所以本题不能直接套用这种写法，必须采用下文两种"先分好位置、再按原顺序回填"或"只相邻交换偶数与后面的奇数"的稳定策略。

方法一：新数组按序回填（O(N) 时间，O(N) 空间）

这是原文档给出的第一种解法，核心思想是：先统计奇数个数确定分界点，再克隆一份原数组，按原顺序把奇数依次填入前半段、偶数依次填入后半段。由于是按原数组顺序扫描回填的，天然满足稳定性。

public int[] reOrderArray (int[] nums) {
    // 奇数个数
    int oddCnt = 0;
    for (int x : nums)
        if (!isEven(x))
            oddCnt++;
    int[] copy = nums.clone();
    int i = 0, j = oddCnt;
    for (int num : copy) {
        if (num % 2 == 1)
            nums[i++] = num;
        else
            nums[j++] = num;
    }
    return nums;
}

private boolean isEven(int x) {
    return x % 2 == 0;
}

逐步拆解关键细节：

1. 第一趟扫描：统计奇数个数 oddCnt。它是分区边界的依据——最终结果中下标 0 .. oddCnt-1 全部是奇数，下标 oddCnt .. N-1 全部是偶数。
2. nums.clone() 克隆原数组。这是稳定性的来源：回填时遍历的是 copy 而非正在被覆盖的 nums。如果直接一边遍历 nums 一边写回 nums，前面的写入会污染后面尚未扫描的元素，导致结果错乱。
3. 两个写入指针：i = 0 从头开始写奇数，j = oddCnt 从分界点开始写偶数。奇偶两类元素各自的写入顺序与 copy 中的出现顺序一致，因此奇数之间、偶数之间的相对位置都被保留。

以 [1,2,3,4,5] 为例：oddCnt = 3，扫描 copy 时依次遇到 1(奇, i=0→1)、2(偶, j=3→4)、3(奇, i=1→2)、4(偶, j=4→5)、5(奇, i=2→3)，最终得到 [1,3,5,2,4]，与题目要求一致。

复杂度分析：

• 时间 O(N)：两次线性扫描（统计 + 回填），共 2N 次比较；
• 空间 O(N)：需要一个与原数组等长的克隆数组。

这是典型的时间换空间方向上的正向操作——用一份 O(N) 的额外空间把调整成本压到了线性。

方法二：冒泡思想原地交换（O(N²) 时间，O(1) 空间）

原文档第二种解法放弃额外数组，改为原地相邻交换：从右向左逐轮扫描，遇到"前面是偶数、后面是奇数"的相邻组合就交换，从而让偶数一步步"上浮"到数组最右边。

public int[] reOrderArray(int[] nums) {
    int N = nums.length;
    for (int i = N - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (isEven(nums[j]) && !isEven(nums[j + 1])) {
                swap(nums, j, j + 1);
            }
        }
    }
    return nums;
}

private boolean isEven(int x) {
    return x % 2 == 0;
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

正确性与稳定性可以从两个层面理解：

• 交换条件足够保守：只在 nums[j] 为偶数且 nums[j+1] 为奇数时才交换。奇奇相邻、偶偶相邻都不会触发交换，因此同类元素之间永远不会发生互换，相对顺序天然保持不变。
• 轮次结构保证完成：外层 i 从 N-1 递减到 1，等价于冒泡排序的轮次结构——每一轮结束后，位置 i 上的元素确定是"当前未定区间中最靠右的偶数"，偶数像气泡一样逐轮漂移到右侧。N-1 轮之后，所有奇数必然都位于所有偶数之前。

注意 swap 中用临时变量 t 完成三步交换，这是原地交换的标准写法；整个算法不申请任何辅助数组，空间复杂度 O(1)。

代价是时间：外层 N-1 轮、内层最多 i 次比较，最坏比较次数为 (N-1)N/2，即 O(N²)。这是典型的空间换时间方向上的反向操作——为了省掉 O(N) 的克隆数组，接受平方级的时间。

两种方案对比与选型建议

方案	时间复杂度	空间复杂度	稳定性	适用场景
方法一：克隆数组回填	O(N)	O(N)	稳定	内存宽裕、追求线性时间；面试中更推荐的基线答案
方法二：冒泡原地交换	O(N²)	O(1)	稳定	内存极度受限、N 很小、或明确不允许额外空间

几点补充说明：

• 为什么不用经典双指针：如开头所述，快排式 partition（见 notes/算法 - 排序.md 中的切分实现）用左右指针交叉交换，一次扫描即可完成分区，但它会打乱同类元素的相对顺序，不满足本题"和书本不太一样"的稳定性约束。
• 从源码结构看，方法一与归并排序中"先合并到辅助数组再拷回"的模式同源——仓库 notes/算法 - 排序.md 中归并实现里有一处注释 nums[k] = aux[i++]; // 先进行这一步，保证稳定性，说明"借助副本 + 按序回填"正是保证稳定性的通用手段。
• 实际工程中如果 N 很大，方法一的 O(N) 方案明显占优；O(N) 的克隆开销在现代内存成本下几乎可以忽略，而方法二的平方级时间在 N 达到数万后就不太可接受了。

小结

本题表面上是一道"奇偶重排"，实际考察的是稳定分区这一与快排切分相对的概念：

1. 读题先确认约束——本题要求奇数之间、偶数之间相对位置不变，因此一次扫描的交叉交换法不适用；
2. 方法一（克隆 + 双指针回填）是线性时间、O(N) 空间的稳定解法，克隆数组是稳定性的关键；
3. 方法二（冒泡式相邻交换）以"只交换前偶后奇的相邻对"为交换条件，O(N²) 时间换来 O(1) 空间；
4. 理解它与快排 partition 的异同（稳定 vs 不稳定），是这道题区别于普通分区题的最大价值所在。

更多同分类题可参见 剑指 Offer 题解 - 目录.md 中"排序"分类下的第 45 题（把数组排成最小的数）与第 51 题（数组中的逆序对），以及 notes/剑指 offer 题解.md 中的总览。