题解 | #调整数组顺序使奇数位于偶数前面#

方法一：

暴力方法，有较大改进空间。使用两个额外数组，分别用来存奇数和偶数，遍历原数组，根据数的奇偶将其存入不同的数组，最后将两个数组整合到一起即可。

class Solution {
public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 
   * @param array int整型vector 
   * @return int整型vector
   */
  vector<int> reOrderArray(vector<int>& array) {
      // write code here
      vector<int> odd,even;
      for(int x:array){
          if(x%2)
              odd.push_back(x);
          else
              even.push_back(x);
      }
      vector<int> ans;
      for(int x:odd)
          ans.push_back(x);
      for(int x:even)
          ans.push_back(x);
      return ans;
  }
};

复杂度分析：

时间复杂度：O(n)，遍历数组。
空间复杂度：O(n)，额外的数组空间。

方法二：

题目的要点在于调整顺序，自然地想到使用双指针的方法，但是由于需要保持原奇数之间、原偶数之间的顺序，因此不能直接进行交换。如果不需要保持顺序的话，可以用时间复杂度为O(n)、空间复杂度为O(1)的算法解决。现在需要保持顺序，因此需要提高时间复杂度和空间复杂度中的一项。
思路：使用双指针的方法，首先找出数组中第一个偶数的位置evenIndex以及在第一个偶数后面的第一个奇数位置oddIndex，将奇数oddIndex移动到evenIndex的位置，然后该奇数前面的所有偶数向后顺移一位。evenIndex加一，从oddIndex+1的位置开始寻找奇数的位置，为新的oddIndex。以此循环往复。

图解如下：

以[2,4,6,5,7]为例，下图是数组元素移动的简图。

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArray(vector<int>& array) {
        // write code here
        int oddIndex=0,evenIndex=0;
        int n=array.size();
        if(n==0) return {};
        //找到第一个为偶数的
        while(array[evenIndex]%2){
            evenIndex++;
        }
        //找到在第一个偶数后的第一个奇数
        while(array[oddIndex]%2==0||oddIndex<evenIndex){
            oddIndex++;
        }
        //将奇数交换到第一个偶数的位置，在该奇数之前的所有偶数向后顺延一个位置
        while(oddIndex<n&&evenIndex<n){
            int tmp=array[oddIndex];
            for(int i=oddIndex;i>evenIndex;i--){
                array[i]=array[i-1];
            }
            array[evenIndex]=tmp;
            //对两个指针位置进行更新
            evenIndex++;
            while(oddIndex<n&&array[oddIndex]%2==0)
                oddIndex++;
        }
        return array;
    }
};

此代码是增加了时间复杂度的做法。也可以用额外的数组空间将偶数暂存，得到时间复杂度O(n),空间复杂度O(n)的做法，这种方***明显优于方法一。
复杂度分析：
时间复杂度：O(n^2)，来源于双指针对数组的遍历，以及对偶数的向后移动，最坏情况下偶数移动会有O(n^2)。
空间复杂度：O(1)，常数个临时变量。