题目描述：

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

实现如下：

//很奇怪，竟然加了“保证奇数和奇数，偶数和偶数之间的相对位置不变。”这个条件→_→
//如果加了这个条件，目前想到的是开辟一个新的vector从array中遍历
//第一次遍历，将奇数push，第二次遍历再将偶数push
class Solution {
public:
	void reOrderArray(vector<int> &array)
	{
		vector<int> res;
		for (int i = 0; i < array.size(); ++i)//array为空直接跳出
		{
			if (array[i] & 0x1)
				res.push_back(array[i]);
		}
		for (int i = 0; i < array.size(); i++)//array为空直接跳出
		{
			if (array[i] % 2 == 0)
				res.push_back(array[i]);
		}
		array = res;
	}
};

//如果不考虑“保证奇数和奇数，偶数和偶数之间的相对位置不变。”这个条件
//维护两个指针/迭代器，itp寻找下一个最近的偶数，its寻找前一个最近的奇数
//当itp > its时，说明全部奇数都在偶数前面
//特殊情况：
//当its - itp == 1时，不需要再交换
//全部为奇数
//全部为偶数
class Solution {
public:
	void reOrderArray(vector<int> &array) 
	{
		int size = array.size();
		if (size == 0 || size == 1) return;//为空或只有一个元素时
		
		vector<int>::iterator itp = array.begin();
		vector<int>::iterator its = array.end() - 1;

		int tmp = 0;
		while (itp < its)//保证还有数字未调整
		{
			//寻找下一个偶数，
			while (itp != array.end() - 1 && *itp & 0x1) ++itp;
			//寻找下一个奇数
			while (its != array.begin() && !(*its & 0x1)) --its;
			//判断是否itp剩下的全为奇数或its剩下的全为偶数
			if (itp == array.end() || its == array.begin()) break;
			else if(itp < its)//保证非its - itp == 1的情况
			{
				tmp = *itp;
				*itp = *its;
				*its = tmp;
			}
		}
	}
};