题目描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分。
思路1：暴力解法
从头到尾扫描一遍数组，每遇见一个偶数时，就拿出这个数字，并把位于这个数字之后的所有数字往前挪动一位,然后把当前这个偶数放到最后。
这样每次遇到一个偶数就要挪动O(n)个数字，因此总的时间复杂度是O(n2)
但是这种方法不仅暴力而且还需要复杂的挪动工作。
public void reOrderArray(int[] array) {
if(array == null) {
return;
}
for(int i=0;i<array.length;i++) {
int j = i;
if(array[i]%2 == 0) {
int temp = array[i];
while(j<array.length-1) {
array[j] =array[j+1];
j++;
}
array[j] = temp;
}
}
}
思路2：冒泡解法
冒泡排序，每次循环前偶后奇就交换。同时我们设立一个标识，来标识数组是否已经符合要求。当再次循环时，发现没有要交换的数据，说明数组已经符合要求。
由于冒泡法比较相邻两个元素，因此奇数或者偶数的相对顺序不变，是稳定的。
public void reOrderArray2(int[] array) {
if(array == null) {
return;
}
boolean flag = true;
for(int i=0;i<array.length-1 && flag;i++) {
flag = false;
for(int j=0;j<array.length-1-i;j++) {
if(array[j]%2==0 && array[j+1]%2!=0) {
int temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
flag = true; //当有数据交换时则 flag 设置为true
}
}
}
}
思路3：利用一个辅助的数组空间来实现
在原来的数组中遇到偶数就放进新数组中，遇到奇数就将奇数移动到原来数组奇数下标的后面（第一次移动奇数到数组的开头），当整个遍历结束后，最后我们将新的数组追加在原来数组奇数下标的后面即可。
public void reOrderArray3(int[] array) {
if(array == null) {
return;
}
int[] auxiliaryArray = new int[array.length];
int auxiliaryIndex = -1; //辅助数组的下标
int index = 0; //原数组的下标，用于控制奇数的位置（偶数插入的下标）
for(int i=0;i<array.length;i++) {
if(array[i]%2 == 0) {
auxiliaryArray[++auxiliaryIndex] = array[i];
continue;
}
array[index ++] = array[i];
}
for(int j=index;j<array.length;j++) {
array[index ++] = auxiliaryArray[auxiliaryIndex--];
}
}
思路4：高效的解法，维护2个指针
由于题目中只要求记奇数在偶数之前，那么我们在扫描这个数组的时候，如果发现一个偶数出现在奇数之前就交换他们的位置，这样一趟后就满足要求了。
因此我们 维护两个索引或者指针，一个指向数组的第一个元素，并向后移动，一个指向数组的最后一个元素，并向前移动。
如果第一个指针指向的元素是偶数，而第二个指针指向的元素是奇数，说明偶数在奇数前面，那么就交换这两个数，直到两个指针相遇为止。
这种算法不能保证相同类型数据的相对位置不变，因此不稳定。
public void reOrderArray4(int[] array) {
if (array == null || array.length == 0) {
return;
}
int left = 0;
int right = array.length - 1;
while (left < right) {
while (left < right && (array[left] &1) != 0) {
left++;
}
while (left < right && (array[right] &1) == 0) {
right--;
}
if (left < right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
}
思路5：考虑可扩展性的解法（即解耦）。
这不仅是解决一个问题的办法，而是解决一系列同类型问题的通用办法。对扩展性的理解，能够给出一个模式，在这个模式下能够很方便地把已有的解决方案扩展到同类型的问题上。
比如（1）把数组中的数按照大小分成两部分，所有负数都在非负数的前面。
（2）把数组中的数分为两部分，能被3整除的数都在不能被3整除的数的前面。
public void reOrderArray5(int[] array) {
if (array == null || array.length == 0) {
return;
}
int left = 0;
int right = array.length - 1;
while (left < right) {
while (left < right && !isEven(array[left])) {
left++;
}
while (left < right && isEven(array[right])) {
right--;
}
if (left < right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
}
//even是偶数的意思，odd是奇数的意思
private boolean isEven(int n) {
//是奇数的话n & 1为1，返回false
//偶数的话n & 1为0，返回true
return (n & 1) == 0;
}
