【剣指offer】奇数が左偶数になるように配列順を調整

タイトル
整数配列を入力し、すべての奇数が配列の前半に位置し、すべての偶数が配列の後半に位置し、奇数と奇数、偶数と偶数の間の相対位置が変わらないことを保証する関数を実現します.
ぶんせき
奇数偶数を単純に分けるだけなら、早列の思想をそのまま使って、一度遍歴すれば答えが得られる.しかし、この問題は複雑で、相対的な位置が変わらないことが要求されている.
1補助スペースの使用
スペース要件がない場合は、補助スペースを直接使用して奇数と偶数をそれぞれ格納し、奇数を前面に、偶数を背面に配置することができます.

class Solution {
public:
    void reOrderArray(vector<int> &array) {
       vector<int> left,right;
        int size = array.size();
        for(int i=0;i< size; i++)
        {
            if(array[i] %2 == 1)
                left.push_back(array[i]);
            else
                right.push_back(array[i]);
        }
        int leftlen = left.size();
        int rightlen = right.size();
        for(int i=0; i< leftlen; i++)
            array[i] = left[i];
        for(int j =0;j < rightlen;j++)
            array[j+ leftlen] = right[j];
        }
 }

2.補助スペースを使用しない
空間的要件がある場合,O(1)は,後から奇数を見つけ,この奇数集団を絶えず拡張し,偶数を見つけると全体的に交換する処理が可能である.

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int index = array.size()-1;
        int datalen = 0;
        for(int i = array.size()-1;i >= 0; i--)
        {
            if(array[i] %2 == 1)
            {
                index = i;
                datalen++;
                break;
            }
        }
        while(index > 0)
        {
            while(index > 0 && array[index-1] %2 == 1)
            {
                index --;
                datalen++;
            }
            if(index ==0 )
                break;
            int temp = array[index -1];
            for(int i =index -1;i<index+datalen;i++)
                array[i] = array[i+1];
            array[index + datalen -1] = temp;
            index --;
        }
    }
};