调整数组使奇数位于偶数前面（且相对位置不能改变）

class Solution {
public:
    /**
       1.冒泡排序，空间复杂度为O(1)
        2.空间复杂度O(n)
        3.相对位置可以改变可以用快速排序
     */
    vector<int> reOrderArray(vector<int>& array) {
        int flag = true;
        while (flag) {
            flag = false;
            for (int i = 1; i < array.size(); ++i) {
                if(array[i-1]%2==0 && array[i]%2){
                    flag = true;
                    swap(array[i-1],array[i]);
                }
            }
        }
        return array;
    }
// 多声明一个O(n)空间
   vector<int> reOrderArray(vector<int>& array) {
        vector<int> res;
        for (auto n: array) {
            if (n % 2) {
                res.push_back(n);
            }
        }
        for (auto n: array) {
            if (n % 2==0) {
                res.push_back(n);
            }
        }
        return res;
    }

};