[water]调整数组顺序使奇数位于偶数前面

第一个思路是借助辅助空间直接先将奇数筛选下来，再筛选偶数
第二个思路是用排序中的思路，问题转视作将奇数的元素尽可能往前面移动，直至到开头或者遇到其他奇数元素（即前面的已经是奇数群体），可以插排也可以冒泡排移动元素
第三个思路是用vector动态调整将偶数都取出然后尾插

#include <iostream>
#include <vector>
using namespace std;

class Solution { //辅助空间
public:
    void reOrderArray(vector<int> &array) {
        vector<int> v;
        for(auto it:array){
            if((it)%2 != 0){
                v.push_back(it);
            }
        }
        for(auto it:array){
            if((it)%2 == 0){
                v.push_back(it);
            }
        }
        for(int i=0;i<array.size();++i){
            array[i] = v[i];
        }
        return ;
    }
};

class Solution2 { //借鉴插入排序，奇数往前部移直至遇到奇数停止
public:
    void reOrderArray(vector<int> &array) {
       for(int i=0;i<array.size();++i){
           if(array[i]%2!=0){
               int j=i-1;
               int tempt=array[i];
               while((j>=0)&&(array[j]%2==0)){
                   array[j+1]=array[j];
                   j--;
               }
               array[j+1] = tempt;
           }
       }
    }
};

vector有两个注意的：
1.动态调整vector还要遍历，变量不能按vector的元素遍历，可能死循环也可能访问非法（调整后it的指向未知并不一定顺延下去），自己手动技术size次。
2.先察除（当然要先存好副本），再插入而不能先插入副本再删除（估计是插入的时候vector就变了it指向也变了），同时得用it=v.erase（it）（无法解释为什么先删除再插入删除的返回it还能用，反正是实测踩坑）

class Solution3 { //vector偶数动态倒插法
public:
    void reOrderArray(vector<int> &array) {
        vector<int>::iterator it = array.begin();
        for(int i=0;i<array.size();++i){
            if(*it%2==0){
                int tempt = *it;
                it = array.erase(it);             //顺序反了就不行？？？？
                array.push_back(tempt);
            }else{
                it++;                            //记得没成功的也有指针后移
            }
        }
    }
};

int main(){
    vector<int> v={1, 2,3,4, 5, 6, 7};
    Solution3 s;
    s.reOrderArray(v);
    for(int i=0;i<v.size();++i)
        cout<<v[i]<<" ";

}