剑指offer 13 调整数组奇偶顺序

题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
  
// O(2n) O(n) 
void reOrderArray(vector<int> &array) {
  if(array.size()==0) return;
  vector<int> res(array.size(),0);
  int s=0,e=array.size()-1;
  for(int i=0;i<array.size();++i){
    if(array[i]%2==1){
      res[s++]=array[i];
    }
  }
  for(int i=array.size()-1;i>=0;--i){
    if(array[i]%2==0){
      res[e--]=array[i];
    }
  }
  array=res;
  }

// O(n*n) O(1) 插排想法
void reOrderArray1(vector<int> &array){
  if(array.size()<=1) return;
  for(int i=0;i<array.size();i++){
    if(array[i]%2==1){
      int tmp=array[i];
      int j=i-1;
      while(j>=0 && array[j]%2==0){
        array[j+1]=array[j];
        j--;
      }
      array[j+1]  =tmp;
    }
  }
}

// 开辟2个数组分别存奇数和偶数 O(n) O(2n)