NO13、调整数组顺序使奇数位于偶数前面(还不错、值得再看一遍）

13、调整数组顺序使奇数位于偶数前面 值得再看一遍

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

1、暴力解法，新开辟一个数组保存数据

void reOrderArray(vector<int>& array) {


    vector<int> temp(array.size(), 0);
    int low = 0;
    for (int i = 0; i < array.size(); ++i) {
        if ((array[i] & 1) == 1) { temp[low++] = array[i]; }
    }

    for (int i = 0; i < array.size(); ++i) {
        if ((array[i] & 1) == 0) { temp[low++] = array[i]; }
    }
    array.assign(temp.begin(), temp.end());
}

2、一种很巧妙的解法，空间复杂度o1的做法，时间复杂度是on^2

void reOrderArray(vector<int>& array) {

    for (int i = 0; i < array.size(); i++)
    {
        //for (auto a : array) {
        //    cout << a << " ";
        //}
        cout << endl;
        for (int j = array.size() - 1; j > i; j--)
        {
            if (array[j] % 2 == 1 && array[j-1] % 2 == 0) //前偶后奇就进行交换，这样一趟下来可以将第一个奇数放在首位，同时最后一个偶数放在末尾
            {
                swap(array[j], array[j - 1]);
            }
        }
    }
}

3、时间和空间都是on的做法，只保存偶数部分

    void reOrderArray(vector<int> &array) {
    vector<int> temp(array.size(), 0);
    int oddIndex = 0, evenIndex = 0;
    for (auto a : array) {
        if ((a & 1) == 1) array[oddIndex++] = a;
        else