题目描述：（题目一）
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。
测试用例：
功能测试：（输入的数组中的奇数、偶数交替出现；所有偶数都在奇数的前面；输入的数组中所有奇数都出现在偶数的前面）
特殊输入测试：（输入为nullptr；输入的数组只包含一个数字）
解题思路：
1) 初级程序员：维护两个指针，一个指向数组的第一个数字，一个指向数组的最后一个数字；两者向中间移动，第一个指针寻找偶数，第二个指针寻找奇数，将两者内容交换。(快速排序算法)
class Solution {public: void reOrderArray(vector &array) { if(array.empty()) return; int front = 0; int back = array.size()-1; while(front 注意：!=优先级高于& 因此判断是要对(array[front]&0x1)加括号，否则在寻找奇数时，会先计算0x1 !=1 永远不成立，因此永远不会进入到循环内
2）高级程序员：写成一些列同类型的通用写法
-- 题目改成把数组中的数按照大小分为两部分，所有负数都在非负数的前面。
-- 能被3整除的数都在不能被3整除的数的前面。
上述问题都只要修改第二个while跟第三个while的的判断条件即可
通用的解决方法：把判断的标准变成一个函数指针，也就是用一个单独的函数来判断数字是否符合标准。
class Solution {public: void reOrderArray(vector &array, bool (*func)(int)) { if(array.empty()) return; int front = 0; int back = array.size()-1; while(front
题目描述：（题目二）
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。并保证奇数和奇数，偶数和偶数之间的相对位置不变。
测试用例：
功能测试：（输入的数组中的奇数、偶数交替出现；所有偶数都在奇数的前面；输入的数组中所有奇数都出现在偶数的前面）
特殊输入测试：（输入为nullptr；输入的数组只包含一个数字）
解题思路：
1）使用vector内置的函数erase与push_back，从左到右遍历，当遇到偶数时，将其在原位置删除并在vector的后面追加。
class Solution {public: void reOrderArray(vector &array) { //if(array.empty()) //return; vector ::iterator even = array.begin(); int size = array.size(); while (size) { if ((*even &01) == 0) { int tmp = *even; even = array.erase(even); //使用erase函数 array.push_back(tmp); }else{ even++; } size--; } }}; 注意：该方法的效率主要取决于erase的效率。
erase()函数删除当期位置，然后将后面的数据前移 效率较低。
2）类似冒泡算法，前偶后奇数就交换：
class Solution {public: void reOrderArray(vector &array) { for (int i = 0; i < array.size();i++) //每一次i循环，可以确定i位置的奇数，离i最近的奇数会传递到i位置 { for (int j = array.size() - 1; j>i;j--)//j每次都从尾部遍历到i后面 { if ((array[j] & 0x1) == 1 && (array[j - 1] & 0x1) == 0) //前偶后奇交换 { //交换两个值swap(array[j], array[j-1]); array[j] = array[j] + array[j-1]; array[j-1] = array[j] - array[j-1]; array[j] = array[j] - array[j-1]; } } } }}; 3）使用stable_partition函数：
//实现1 判断函数定义在类外部 bool isOk(int n){ return ((n & 1) == 1); //奇数返回真 }class Solution {public: void reOrderArray(vector &array) { stable_partition(array.begin(),array.end(),isOk); }}; //实现2 判断函数定义在类内部 class Solution {public: void reOrderArray(vector &array) { stable_partition(array.begin(),array.end(),isOk); } static bool isOk(int n){ //定义在类内，要加static,否则类内会报错。与*this指针有关 return ((n & 1) == 1); //奇数返回真 }}; //实现3 lambda表达式 class Solution {public: void reOrderArray(vector &array) { stable_partition(array.begin(), array.end(), [](int i){return (i & 1) == 1;}); //奇数返回真 }}; 注：
[1] stable_partiton(first,last,compare);//first为容器的首迭代器，last为容器的末迭代器，compare为比较函数（可略写）。1 2 3 4 5 序列，用partition函数 那么输出不一定是：1 3 5 2 4 也有可能是：3 5 1 4 2。如果使用stable_partition函数（稳定整理算法），那么输出一定就是：1 3 5 2 4
[2] stable_partition函数源码其实是开辟了新的空间，然后把符合条件的放在新空间的前面，其他的放在后面。 代码中看起来时在原array上进行的操作
[3] 可以向一个算法传递任何类别的可调用对象。可调用对象有，函数指针，其实还有重载了函数调用运算符的类，和lambda表达式。
-- lambda表达式 : 用于定义并创建匿名的函数对象，以简化编程工作。
-- 语法形式:
[capture list] (params list) mutable exception-> return type { function body }各项具体含义如下1. capture list：捕获外部变量列表2. params list：形参列表3. mutable指示符：用来说用是否可以修改捕获的变量4. exception：异常设定5. return type：返回类型6. function body：函数体可以省略其中的某些成分来声明“不完整”的Lambda表达式，常见的有以下几种//省略 mutable指示符、exception：异常设定1. [capture list] (params list) -> return type {function body}格式1声明了const类型的表达式，这种类型的表达式不能修改捕获列表中的值//省略返回类型及mutable指示符、exception：异常设定2. [capture list] (params list) {function body}格式2省略了返回值类型，但编译器可以根据以下规则推断出Lambda表达式的返回类型： （1）：如果function body中存在return语句，则该Lambda表达式的返回类型由return语句的返回类型确定； （2）：如果function body中没有return语句，则返回值为void类型。3. [capture list] {function body}格式3中省略了参数列表，类似普通函数中的无参函数。示例：[] (int x, int y) { return x + y; } // 隐式返回类型[] (int& x) { ++x; } // 没有 return 语句 -> Lambda 函数的返回类型是 'void'[] () { ++global_x; } // 没有参数，仅访问某个全局变量[] { ++global_x; } // 与上一个相同，省略了 (操作符重载函数参数)//显示指定返回类型[] (int x, int y) -> int { int z = x + y; return z; } 4）新建数组，遍历两遍，先存奇数，再存偶数
class Solution {public: void reOrderArray(vector &array) { vector res; //存奇数 for(int i = 0; i < array.size(); i++) { if((array[i] & 1) == 1) res.push_back(array[i]); } //存偶数 for(int i = 0; i < array.size(); i++) { if(array[i] % 2 == 0) res.push_back(array[i]); } //array.swap(res); //swap的效率？ array = res; //或者用 swap } 注：以后判断奇偶性，不要用 array[i] % 2 == 1 因为不仅效率低，而且当array[i] 为负数，比如-1%2=-1 并不等于1。
用空间换时间，存偶数与存奇数分别是O(n)，最后array=res;的操作，时间复杂度是O(1)么？
5）插入排序算法
相对位置不变--->保持稳定性；奇数位于前面，偶数位于后面 --->存在判断，挪动元素位置；
//java public class Solution { public void reOrderArray(int [] array) { //相对位置不变，稳定性 //插入排序的思想 int m = array.length; int k = 0;//记录已经摆好位置的奇数的个数 for (int i = 0; i < m; i++) { //将找到的奇数移动到已确定的k的后面，k++，可以确定k+1个 if (array[i] % 2 == 1) { int j = i; while (j > k) {//j >= k+1 int tmp = array[j]; array[j] = array[j-1]; array[j-1] = tmp; j--; } k++; } } }} 6）归并排序 （快速排序是不稳定的，这里不能使用）归并时间复杂度是nlogn，需要额外的O(N)空间
//java 该算法过于麻烦 待考虑public class Solution { public void reOrderArray(int [] array) { //用用归并排序的思想，因为归并排序是稳定的 int length = array.length; if(length == 0){ return; } int[] des = new int[length]; MergeMethod(array, des, 0,length - 1); } public void MergeMethod(int[] array, int [] des, int start, int end){ if(start < end){ int mid = (start + end) / 2; MergeMethod(array, des, start, mid); //前半部分 MergeMethod(array, des, mid + 1, end); //后半部分 Merge(array, des, start, mid, end); } } public void Merge(int[] array, int[] des, int start, int mid, int end){ int i = start; int j = mid + 1; int k = start; while(i <= mid && array[i] % 2 == 1){ des[k++] = array[i++]; } while(j <= end && array[j] % 2 == 1){ des[k++] = array[j++]; } while(i <= mid){ des[k++] = array[i++]; } while(j <= end){ des[k++] = array[j++]; } for(int m = start; m <= end; m++){ array[m] = des[m]; } }} 7）新开数组空间换时间的解法：