题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解题思路
题目中要求奇数和奇数，偶数和偶数之间的相对位置不变，就不能使用类似于快速排序的头尾双指针向中间靠拢的方式来计算。必须两个指针全部从头部开始，锁定第一个扫描到的奇数和偶数，将偶数后移，奇数插入。具体步骤如下：
1. 判断数组大小是否为0，为0直接返回；
2.初始化指针i=0,j=i+1,及临时变量tmp；
3.只要j满足j<size,就循环执行4~8操作；
4. 从i开始从左到右寻找第一个偶数位置赋给i；
5. j=i+1，从左到右寻找第一个奇数位置赋给j；
6.如果j大于数组大小，则数组已完成要求，跳出循环；
7.将i~j-1 位置的偶数后移，在i位置插入原j位置的值；
8.i指向下一元素(i++),返回步骤4；
C++代码实现：
class Solution {
public:
void reOrderArray(vector<int> &array) {
int size=array.size();
if(size==){
return;
}
int i=,j=i+, tmp;
while(i<size && j<size){
while(array[i]%!=){ //i确定偶数位置
i++;
}
j=i+;
while(array[j]%!=){ //j确定奇数位置
j++;
}
if(j>=size){ //j超过数组长度，则结束
return;
}
tmp=array[j];
for (int k=j;k>i;--k){
array[k]=array[k-];
}
array[i]=tmp;
i++;
}
}
};