题目描述：
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
实现如下：
//很奇怪，竟然加了“保证奇数和奇数，偶数和偶数之间的相对位置不变。”这个条件→_→ //如果加了这个条件，目前想到的是开辟一个新的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; } } } };