数组偶数前置奇数后置的两种C++实现 哪一种算法更优？

两种方案的时间复杂度均为O(n)，没有绝对的优劣，具体选型看你的实际需求： #

方案1（双指针交换法） #

优势 #

• 原地修改数组，无额外空间开销，如果你后续需要使用调整顺序后的数组，不需要额外申请空间存储结果
• 仅遍历数组1次，超大数据量下内存访问开销更低
• 属于通用的数组划分模板，稍加修改就能适配其他划分规则（比如负数排在正数前、符合某条件的元素排在前面等）

劣势 #

• 会打乱偶数、奇数各自的相对顺序，是不稳定的划分：比如原数组偶数顺序是2、4、6，调整后可能变成2、6、4
• 会修改原数组内容，如果你需要保留原始输入数据不能用这个方案
• 边界条件多，容易写错导致数组越界

方案2（两次遍历输出法） #

优势 #

• 代码逻辑极简，可读性极高，几乎不会出现编写错误
• 不会修改原数组，能完整保留原始输入数据
• 是稳定的划分：偶数之间、奇数之间的相对顺序和原数组完全一致，和你给出的样例输出顺序完全匹配
• 如果你的需求仅为输出结果，不需要存储调整后的数组，没有多余的操作步骤

劣势 #

• 需要遍历数组两次，超大数据量下比方案1多一倍的遍历开销
• 如果你需要得到调整后的数组做后续操作，需要额外申请数组存储结果，空间复杂度会上升到O(n)

选型建议 #

• 仅输出结果、需要保留原数组、需要奇偶内部顺序稳定：选方案2，开发效率最高
• 需要原地修改数组、不需要保留原顺序、后续要操作调整后的数组：选方案1

两份代码的共性优化点 #

两份代码都用了C++标准不支持的变长数组语法int a[n];，这是GCC的扩展特性，跨编译器兼容性差，建议替换为标准的vector实现：

vector<int> a(n);

另外方案1引入的万能头文件#include<bits/stdc++.h>属于非标准头文件，仅适合竞赛场景，实际开发建议按需引入<iostream>、<vector>、<algorithm>等标准头文件。

内容的提问来源于stack exchange，提问作者sameerkumarsahu330