题目难度：中等

题目描述：

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

数据范围：0≤n≤5000，数组中每个数的值 0≤val≤10000
要求：时间复杂度 O(n)，空间复杂度 O(n)
进阶：时间复杂度 O( $n^{2}$ )，空间复杂度 O(1)
示例1：输入：[2,4,6,5,7] 返回值：[5,7,2,4,6]

代码如下：

错误思路1：双指针 / 中心扩散 - 写法一

class Solution {
public:
  	vector<int> reOrderArray(vector<int>& array) {
      	if(array.size() < 2) return array;
        int i = 0, j = array.size() - 1;

        while (i < j) {
            while (array[i] & 1) i++;
            while ((array[j] & 1) == 0) j--;
            if ((array[j] & 1) && i < j) 
                // 此时， i 所指向的位置就是偶数
                swap(array[i++], array[j--]);
        }
        return array;
    }
};

此种写法，或者由中心扩散来交换奇偶数的方式，虽然能分离奇偶数，但是避免不了相对顺序的打乱

思路2：归并

时间复杂度：O(n) 运行时间：4ms 占用内存：520KB

class Solution {
public:
  	vector<int> reOrderArray(vector<int>& array) {
      	if(array.size() < 2) return array;
      	vector<int> even, odds, res(array.size(), 0);
      
      	for(int i = 0; i < array.size(); ++i) {
          	if(array[i] & 1) odds.push_back(array[i]);
          	else even.push_back(array[i]);
        }
      	
      	// copy to res
      	int i = 0, index = 0;
      // 先判断odds.size()，可以减少时间复杂
      	while(odds.size() && i < odds.size()) res[index++] = odds[i++];
      
      	i = 0;
      	while(even.size() && i < even.size()) res[index++] = even[i++];
      
      	return res;
    }
}

思路3：双指针 - 写法二

时间复杂度：O(n) 运行时间：4ms 占用内存：524KB

class Solution {
public:
  vector<int> reOrderArray(vector<int>& array) {
    int n = array.size();
    if(n < 2) return array;
    vector<int> res(n, 0);
    int odd = 0;
    
    for(int i = 0; i < n; ++i) if(array[i] & 1) odd++;
    
    int x = 0, y = odd;
    for(int i = 0; i < n; ++i) {
      if(array[i] & 1) res[x++] = array[i];
      else res[y++] = array[i];
    }
    return res;
  }
}

拓展思路：

运行时间：5ms 占用内存：428KB 时间复杂度：O( $n^{2}$ ), 空间复杂度：O(1)

此题的难点在于：怎样保证相对顺序的不变，前面的方法都是，牺牲空间，用额外的数组来单独保存奇数和偶数；但是，如果用思路1的方式，交换，必然导致相对顺序错误，所以不能用交换的方式，而是选择插入的方式，但是，插入只能牺牲时间复杂度。

class Solution {
public:
  vector<int> reOrderArray(vector<int>& array) {
    if(array.size() < 2) return array;
    int firstEven = 0;
    
    for(int i = 0; i < array.size(); ++i) {
      // 还没遇见偶数
      if((array[i] & 1) && i == firstEven) firstEven++;
      else if (array[i] & 1) {
        // 已经遇见偶数，找到首次出现的偶数，此时，只需要不断向后找奇数
        int temp = array[i];
        // 从后向前逐个替换
        for(int j = i; j > firstEven; --j) array[j] = array[j-1];
        
        array[firstEven++] = temp;
      }
    }
    return array;
  }
};