维护一个标记firstEven指向数组当前第一个偶数的位置。
遍历数组,当遇到一个奇数时,判断其下标与firstEven是否相等,若相等,说明目前数组前面都是奇数,不需要调整顺序,使firstEven++,保持与循环控制遍历i同步。若不等,说明前面已有偶数出现,将当前i指向的奇数插入firstEven指向的位置,这里插入为了维持数组的稳定,即偶数与奇数内部的顺序不变,采用类似插入排序的方式,firstEven到i-1之前的偶数整体后移1位。当遇到偶数时,空过。

这种方式采用原地操作,空间复杂度为O(1)。由于有循环嵌套,时间复杂度大于O(n),具体情况根据输入数组的情况改变。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArray(vector<int>& array) {
        // write code here
        int firstEven = 0;
        for(int i = 0;i < array.size();i++){
            if(array.at(i) % 2 && i == firstEven){
                firstEven++;
            }
            else if(array.at(i) % 2){
                int temp = array.at(i);
                int pre = array.at(firstEven);
                for(int j = firstEven + 1;j < i + 1;j++){
                    int tmp = array.at(j);
                    array.at(j) = pre;
                    pre = tmp;
                }
                array.at(firstEven) = temp;
                firstEven++;
            }
        }
        return array;
    }
};