描述

此题解是针对初学者的全面讲述，用三种方法来解决。
知识点：数组
难度：一星

题解

方法一：使用辅助数组

函数的类型为void func_name(array&)，想让我们不开辟额外数组来解决，使用in-place就地算法。但是如果空间要求不高的话，我们还是可以开挂的。也就是开辟个额外数组，接下来的做法就非常简单了，遍历一次数组，遇到奇数直接放入新开的数组中，再遍历一次数组，遇到偶数就继续放入新开的数组。最后再进行一次copy。
代码如下：

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        vector<int> arr;
        for (const int v : array) {
            if (v&1) arr.push_back(v); // 奇数
        }
        for (const int v : array) {
            if (!(v&1)) arr.push_back(v); // 偶数
        }
        copy(arr.begin(), arr.end(), array.begin());
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

方法二：in-place算法

如果不开辟额外数组该怎么做呢？
初始化操作：记录一个变量i表示已经将奇数放好的下一个位置，显然最开始i=0,表示还没有一个奇数放好。
j 表示数组的下标，初始值为0， 表示从下标0开始遍历。

  1. 如果遇到偶数，j++
  2. 如果遇到奇数,假设位置为j，就将此奇数插入到i所指的位置，然后i往后移动一个位置，在插入之前，显然会涉及到数据的移动，也就是将[i,j-1]整体往后移动。
  3. 直到整个数组遍历完毕，结束
    图片说明
    代码如下：
    class Solution {
public:
  void reOrderArray(vector<int> &array) {
      int i = 0;
      for (int j=0; j<array.size(); ++j) {
          if (array[j]&1) {
              int tmp = array[j];
              for (int k=j-1; k>=i; --k) {
                  array[k+1] = array[k];
              }
              array[i++] = tmp;
          }
      }
  }
};
    时间复杂度：O(n^2),假设数组中一般偶数在前，一半奇数在后，每次都要移动n/2个元素,是n^2/4
    空间复杂度：O(1)

方法三：使用STL库函数stable_partition()

函数原型:
template< class BidirIt, class UnaryPredicate > BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPredicate p );

第三个参数P可传入一个仿函数，函数指针，Lambda表达式，这里所示代码为Lambda表达式。
函数的意思是：对传入的区间[first, last)中的每个值进行P(value)判断，如果为真，就放入左边，并且保持稳定。

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        stable_partition(array.begin(), array.end(), [](int x) {return x&1;} );
    }
};

时间复杂度：O(n)
空间复杂度：O(n)，内部使用了额外数组