一、保证数与数之间的相对位置不变，但空间复杂度变高O(n)

#include <fstream>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArray(vector<int>& array) {
        // write code here
        int a = array.size();
        vector<int> ans1,ans2;
        for(int i = 0; i < a; i++){
            if(array[i] % 2 == 1){
                ans1.push_back(array[i]);
            }
            if(array[i] % 2 == 0){
                ans2.push_back(array[i]);
            }
        }
        ans1.insert(ans1.end(), ans2.begin(), ans2.end());//偶数数组插入在奇数数组后面连接起来
        return ans1;
    }
};

基本算法思想：

遍历数组，将奇数和偶数分别存放在两个新的数组中，然后将偶数数组插入到奇数数组的后面。

时间复杂度：

遍历数组需要O(n)的时间复杂度，插入操作也需要O(n)的时间复杂度，所以总的时间复杂度为O(n)。

空间复杂度：

需要额外的两个数组来存放奇数和偶数，所以空间复杂度为O(n)。

二、不能保证数与数之间相对位置不会变化，但空间复杂度为O(1)

#include <any>
#include <type_traits>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型vector
     * @return int整型vector
     */
    vector<int> reOrderArrayTwo(vector<int>& array) {
        // write code here
        int a = array.size();
 
        for (int left = 0,right = a-1; left < right; ) {
            if(array[left] % 2 == 0){
                swap(array[left], array[right--]);
            }
            else if (array[right] % 2 == 1) {
                swap(array[right], array[left++]);
            }
            else {
                left++,right--;
            }
        }
        return array;
    }
};

基本算法思想：

使用双指针，左指针指向数组的第一个元素，右指针指向数组的最后一个元素。当左指针指向的元素为偶数，右指针指向的元素为奇数时，交换两个元素的位置，然后左指针右移，右指针左移。当左指针指向的元素为奇数时，左指针右移；当右指针指向的元素为偶数时，右指针左移。直到左指针大于等于右指针时退出循环。

时间复杂度：

使用双指针只遍历了一遍数组，所以时间复杂度为O(n)。

空间复杂度：

只需要常数级别的额外空间，所以空间复杂度为O(1)。