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

image.png

解法一：用空间换取时间的思想

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

解法二：插排的思想：

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