调整奇数位于偶数之前：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位与偶数的前半部分，偶数位于数组的后半部分，不需要保持相对位置。
//
// Created by 郑卓铭 on 2019/10/31.
//
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
void reOrderArray(vector<int> &array) {
/*
用双指针法，初始状态时，一个指针指向数组首元素，一个指针指向为元素
前指针找出偶数，后指针找出奇数，然后再满足前指针小于后指针的情况下
进行交换
*/
vector<int>::iterator first = array.begin(),last = array.end()-1;
while(first<last){
//前指针找出偶数
while(first<last && func(first))
first++;
while(first<last && !func(last))
last--;
if(first<last){
int temp = *first;
*first = *last;
*last = temp;
}
}
}
bool func(vector<int>::iterator p){
return (*p & 1);
}
};
复杂度分析： 时间复杂度：O（n），因为双指针法只会把数组遍历一遍.
调整数组顺序使奇数位于偶数前面:输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
分析：此处要求保持相对位置不变。 可以用冒泡的思想，找到一个偶数，然后找它后面的第一个奇数，然后对中间的元素进行移位 也可以使用插入的思想，每次找到一个奇数就插入到对应位置，因此需要设置一个变量来记录应该插入的位置，也就是统计已经归位的奇数的数量。 还可以使用空间换时间的方法，用一个新的数组遍历两遍原数组分别让奇数和偶数装入新数组。
解法一:
void reOrderArray(vector<int> &array) {
/*
先用冒泡排序的思想，首先找到偶数，然后找当前偶数的下一个奇数，然后对中间的数进行
移位覆盖
*/
for(auto i=0;i<array.size();i++){
if(array[i]%2==0){
//找到偶数，继续找奇数
for(auto j=i+1;j<array.size();j++){
if(array[j]%2==1){
//找到该偶数后的第一个奇数，然后移动位置
int temp = array[j];
while(j>i){
array[j] = array[j-1];
j--;
}
//最后把奇数移动到偶数的位置
array[i] = temp;
i=j-1;
break;
}
}
}
}
}
时间复杂度是O（n2）
解法二：
void reOrderArray(vector<int> &array) {
/*
利用插入排序的思想，每次检索到奇数就往前插入，并且要记录当前要被插入的下标
也就是当前已经插入了多少个奇数
*/
int k = 0;//k表示当前已经归位的奇数的个数，也就是当前奇数应该插入的位置
for(auto i=0;i<array.size();i++){
if(array[i]%2==1){
//检索到奇数就要向前插入
int temp = array[i];
auto j = i;
while(j>k){
array[j] = array[j-1];
j--;
}
array[k] = temp;
k++;
}
}
}
时间复杂度是O（n2）
解法三：
void reOrderArray(vector<int> &array) {
/*
设置另一个数组，先遍历一遍把奇数放入该数组，遍历第二遍把偶数放入数组
*/
vector<int> newArray;
for(auto i=0;i<array.size();i++){
if(array[i]%2==1){
newArray.push_back(array[i]);
}
}
for(auto i=0;i<array.size();i++){
if(array[i]%2==0){
newArray.push_back(array[i]);
}
}
array = newArray;
}
时间复杂度是O（n） 空间复杂度是O（n）
