剑指offer：13 调整数组中的偶数到奇数后面

1 冒泡解法 稳定

2 辅助数组 稳定

3 两个指针 不稳定

#include <iostream>
#include <vector>
using namespace std;
class solution
{
public:
    //冒泡解法
    void reOerderArray(vector<int> &array){
        if (array.size() == 0) {
            return ;
        }
        bool label = false;
        for (int i = 0; i < array.size(); i++) {
            for (int j = array.size() - 1; j > i; j--) {
                if ((array[j] % 2 == 1) && (array[j-1] % 2 == 0)) {
                    int temp = array[j];//前偶后积就交换
                    array[j] = array[j-1];
                    array[j-1] = temp;
                    label = true;
                    cout << label << endl;
                }
            }
        if (label == false){
            break;
        }
        }


    }

    //辅助数组完成
    void reOerderArray2(vector<int> &array){
        if (array.size() == 0) {
            return ;
        }
        vector<int> temp;
        vector<int> tp;//两个空数组
        for (int i = 0; i < array.size(); i++) {
            if (array[i] % 2 == 0) {
                temp.push_back(array[i]);

            }
        }

        for (int i = 0; i < array.size(); i++) {
            if (array[i] % 2 == 1) {
                tp.push_back(array[i]);
            }
        }

        for (int j=0 ; j < temp.size(); j++) {
            tp.push_back(temp[j]);
        }

        int m = 0, q = 0;
        while (tp[q]) {
            array[m++] = tp[q++];//压回原数组
        }
    }

    void reOerderArray3(vector<int> &array){
        if (array.size() == 0) {
            return ;
        }
        vector<int> temp;
        vector<int>::iterator ib1, ie1;//迭代器
        ib1 = array.begin();
        ie1 = array.end();
        for (; ib1 != ie1;) {
            if (*ib1 % 2 == 0) {
                temp.push_back(*ib1);//偶数压入空数组
                ib1 = array.erase(ib1);//删除偶数
            }
            else {
                ib1++;
            }
        }
        vector<int>::iterator ib2, ie2;
        ib2 = temp.begin();
        ie2 = temp.end();
        for (; ib2 != ie2; ib2++) {
            array.push_back(*ib2);//偶数放回原数组后面
        }

        /*int q = 0;
        while (temp[q]) {
            array.push_back(temp[q++]);
        }*/



    }

    //两个指针比较，但是不稳定，数度快
    void reOerderArray4(vector<int> &array){
        if (array.size() == 0) {
            return ;
        }
        vector<int>::iterator left, right;//迭代器
        left = array.begin();
        right = array.end() - 1;

        while(left < right) {
            while (left < right && (*left & 0x01) == 1){
                left++; //是奇数后移
            }
            //执行条件是现在已是偶数，等着下边移到奇数
            while (left < right && (*right & 0x01) == 0){
                right--; // 是偶数前移
            }
            //执行条件是前边是偶数，后边是奇数
            if (left < right) {
                int temp = *left;
                *left = *right;
                *right = temp;
            }

        }

    }




};

int main()
{
    int a1[] = { 5, 7 , 6, 3, 9, 8};
    vector<int> vec(a1, a1 + 6);
    solution s;
    s.reOerderArray4(vec);
    for (int i = 0; i < vec.size(); i++){
        cout << vec[i] << endl;
    }

    return 0;
}