面试题21：调整数组顺序使奇数位于偶数前面

从“只分类，不排序”开始

先预测：输入 1,2,3,4,5,6,7，算法输出必须是 1,3,5,7,2,4,6 吗？题目只要求奇数位于偶数前面，没有要求奇数内部或偶数内部继续保持原顺序，也没有要求升序。因此 1,7,3,5,4,6,2 同样是合法结果。

若把整个数组排序，当然也能让一部分奇数出现在偶数前，但需要更多比较，还会引入并非题目要求的组内次序。本题是二路划分：只要存在一个边界，使边界左侧全是奇数、右侧全是偶数即可。

把一个指针放在数组开头向右找偶数，另一个放在末尾向左找奇数；找到一对错位元素后交换。两个位置都从外侧向中间移动，这种技巧称为。

左指针停在偶数2，说明它不应留在前区；右指针停在奇数7，说明它不应留在后区。交换后两个元素同时归位。算法不需要知道最终边界在哪，它通过不断缩小未分类区间自然找到边界。

三段区间是不变量

循环任意时刻都可以把数组分为三段：

1. left 左侧已经全部是奇数。
2. left 到 right 之间尚未分类。
3. right 右侧已经全部是偶数。

这组始终成立的条件称为。左内层循环越过奇数，只扩大正确的前区；右内层循环越过偶数，只扩大正确的后区；交换则把两个边界错位元素放进对应区域。

当 left 与 right 相遇或交错时，未分类区间为空或只剩一个元素。由于两边已满足不变量，整个数组自然满足奇数在前、偶数在后。每个指针只朝一个方向移动，所以算法一定终止。

忠实实现作者第一种解法

作者用位与最低位判断奇偶：最低位为1是奇数，为0是偶数。空指针或长度为0时必须先返回，否则计算末尾指针会越过有效对象边界。

#include <cstddef>
#include <utility>
 
void reorderOddEven(int* data, std::size_t length) {
    if (data == nullptr || length == 0) return;
 
    int* begin = data;
    int* end = data + length - 1;
 
    while (begin < end) {
        while (begin < end && (*begin & 1) != 0) {
            ++begin;
        }
        while (begin < end && (*end & 1) == 0) {
            --end;
        }
        if (begin < end) {
            std::swap(*begin, *end);
        }
    }
}

注意作者交换后没有显式执行 begin 加一和 end 减一，这并不会死循环。交换前 begin 指向偶数、end 指向奇数；交换后 begin 位置变成奇数、end 位置变成偶数。下一轮两个内层循环会立刻分别越过它们，使未分类区间严格缩小。

显式移动也可以正确，因为这两个位置已经归类，但它不是防止死循环的唯一方式。阅读源码时应按值与谓词证明进展，不能看到没有手动移动就断言错误。

复杂度为何不是嵌套循环的平方

代码有外层循环和两个内层循环，但 begin 总共最多前进 length 次，end 总共最多后退 length 次；任何位置不会被同一指针反复跨越。总访问次数与数组长度成线性关系，所以时间 O(n)。

交换就地发生，只使用两个指针和一个临时值，额外空间 O(1)。最坏交换次数不超过 n 的一半，因为每次交换至少修复两个错位位置。已经分区、全奇数或全偶数时没有交换。

数组元素可能为负数。作者的位与写法在项目目标整数表示上可用；若希望表达语义更直接，可以写 value % 2 != 0。不能写 value % 2 == 1，因为负奇数在 C++ 中的余数是 -1，会被误判为非奇数。

把“偶数”提取成后区谓词

第二种解法不再把奇偶判断写死在扫描框架中。作者的 func 返回 true 表示该元素应该放到后半区：左指针越过 func 为 false 的元素，停在 true；右指针越过 true，停在 false，然后交换。

把这种函数称为。奇偶题传入 isEven，因此 false 的奇数在前，true 的偶数在后。这里的 true 不是“应放前面”，若调用者误解方向，结果会完全相反。

#include <cstddef>
#include <utility>
 
using BackPredicate = bool (*)(int);
 
bool isEven(int value) {
    return (value & 1) == 0;
}
 
void reorder(int* data,
             std::size_t length,
             BackPredicate belongsBack) {
    if (data == nullptr || length == 0 ||
        belongsBack == nullptr) {
        return;
    }
 
    int* begin = data;
    int* end = data + length - 1;
    while (begin < end) {
        while (begin < end && !belongsBack(*begin)) {
            ++begin;
        }
        while (begin < end && belongsBack(*end)) {
            --end;
        }
        if (begin < end) {
            std::swap(*begin, *end);
        }
    }
}
 
void reorderOddEvenExtensible(int* data, std::size_t length) {
    reorder(data, length, isEven);
}

这种“判断函数解耦”把稳定的扫描骨架与变化的业务规则分开。把 isEven 换成“是否非负”“是否无效”“是否超过阈值”，就能复用同一划分过程。这里的扩展性来自明确的谓词契约，而不只是把函数指针塞进参数列表。

现代 C++ 可用函数模板接收无状态 lambda，避免 std::function 的类型擦除开销；若接口跨动态库或 C ABI，普通函数指针反而更清晰。无论形式如何，谓词必须是确定的、无副作用的，并在一次调用期间对同一值返回一致结果。

非稳定划分会改变组内次序

原算法属于。输入 2,4,6,1,3,5,7 第一次会交换2和7，奇数7直接越过原本位于它前面的1、3、5；虽然分类正确，奇数组内顺序改变。

如果需求要求原数组中先出现的奇数在结果中仍先出现，偶数也同样保序，就需要。最直接方案是顺序扫描两次或使用两个缓冲区：先按原序写入所有奇数，再按原序写入所有偶数，时间 O(n)、额外空间 O(n)。

也可以原地稳定：遇到奇数时把它旋转到前区边界，并把中间偶数整体右移。简单实现最坏 O(n²)；分治配合区间旋转可做到 O(n log n) 时间和较少辅助空间，但明显复杂。需求没要求稳定时，不应主动承担这笔成本。

标准库 std::partition 对应本题非稳定划分，但它的谓词通常表示“放前区”，与作者后区谓词方向相反；std::stable_partition 提供稳定语义，复杂度和空间取决于可用缓冲。调用库函数时仍要先对齐契约。

测试三个性质而不是只看打印

作者六组测试依次是交错输入、偶数全在前、已经正确分区、单奇数、单偶数和空输入。原示例只打印调整前后数组，人工观察容易漏错；自动测试应验证三个性质：

1. 找到第一个偶数后，后面不能再出现奇数。
2. 调整前后的元素多重集合相同，不能丢失或复制元素。
3. 数组长度和存储边界不变，空输入不访问内存。

#include <algorithm>
#include <cassert>
#include <vector>
 
bool partitionedOddBeforeEven(const std::vector<int>& values) {
    bool seenEven = false;
    for (int value : values) {
        if ((value & 1) == 0) {
            seenEven = true;
        } else if (seenEven) {
            return false;
        }
    }
    return true;
}
 
void checkCase(std::vector<int> values) {
    auto before = values;
    reorder(values.data(), values.size(), isEven);
    assert(partitionedOddBeforeEven(values));
    std::sort(before.begin(), before.end());
    auto after = values;
    std::sort(after.begin(), after.end());
    assert(before == after);
}
 
void testReorder() {
    checkCase({1,2,3,4,5,6,7});
    checkCase({2,4,6,1,3,5,7});
    checkCase({1,3,5,7,2,4,6});
    checkCase({1});
    checkCase({2});
    checkCase({});
    reorder(nullptr, 0, isEven);
}

若元素可重复，多重集合检查仍然有效；只用普通集合会把两个2和一个2视为相同，掩盖复制或丢失。对于模板化对象，应记录ID序列或计数映射，避免排序本身要求对象可比较。

还应加入负奇数、全奇、全偶、两个元素正反序和随机数组。随机测试可以把结果与 std::partition 的性质断言比较，但不应要求两个非稳定算法输出相同排列。

边界、异常与泛型对象

长度类型使用 size_t 可以避免把负长度传入核心函数，但外部有符号输入仍要先验证再转换。作者先检查 length 为0，再计算 data + length - 1，这个顺序不可交换；零长度下减一会产生无效位置。

对 int 交换不会抛异常。泛型对象若移动或交换可能抛出，原地划分只能提供基本保证：数组仍由有效对象组成，但可能已经部分分区。若业务需要强异常保证，可以先计算目标排列并在临时容器完成，再无异常提交，代价是额外空间。

谓词若读取会变化的外部状态，同一元素第一次判为前区、下一次判为后区，不变量与终止证明都会失效。并发修改数组也会造成数据竞争。算法契约应要求独占访问、固定长度和纯判定函数。

链表无法从尾部反向扫描，不能直接套首尾指针。单链表可维护“满足前区谓词”的节点链和后区节点链再拼接，或使用前驱指针重连；如果按原遍历顺序追加到两条链，还能在线性时间、常数额外节点空间内保持稳定。

正确性证明

初始时两个已分类区间都为空，不变量成立。左扫描只跨越应在前区的奇数，右扫描只跨越应在后区的偶数，因此扩展后的两区仍正确。若指针未相遇，左边界是偶数、右边界是奇数，交换后两者分别属于正确区域。

每轮至少有一个指针向中间推进；交换后下一轮两侧都会越过刚归位元素，所以未分类区间严格缩小。指针相遇时所有元素都在某个正确区间内，故存在奇偶边界，奇数位于偶数前面。

交换不创建、不销毁元素，只置换两个位置，因此多重集合保持不变。结合终止性与分区不变量，算法满足题目全部要求。

本章练习

概念说明

本章核心概念包括：首尾双指针。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. 题目只要求奇数位于偶数前面，不要求排序或保持组内顺序。
2. 首尾双指针分别寻找左侧偶数和右侧奇数，交换错位元素。
3. 左前区全奇、右后区全偶、中央未分类构成分区不变量。
4. 作者交换后由下一轮内层扫描自然推进，不需要额外移动才能终止。
5. 两个指针单调移动，时间 O(n)、额外空间 O(1)。
6. 后区谓词返回true的元素放后面，isEven使奇数自然进入前区。
7. 非稳定划分允许组内次序改变；稳定需求需要额外时间或空间。
8. 测试应断言分区边界和多重集合，而不是只比较某个固定排列。

名词解释