题目描述 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路1： 用两个list分别存储奇数和偶数，然后再合并到array中 空间换时间O(n)，方法比较傻比较傻。
在面试时，注意方法的可扩展性，比如题目可以换成：使得所有的能被3整除的数位于数组的前半部分，其余不被3整除的数位于数组的后半部分。可以和面试官沟通，将方法单独提炼出来，采用简单工厂模式等。
import java.util.ArrayList; public class Solution { public void reOrderArray(int [] array) { ArrayList<Integer> oddlist = new ArrayList<Integer>(); ArrayList<Integer> evenlist = new ArrayList<Integer>(); int len = array.length; for(int i = 0; i < len; i++) { if((array[i] & 1) != 0) { oddlist.add(array[i]); }else { evenlist.add(array[i]); } } int k = 0; for(int i = 0; i < oddlist.size(); i++) { array[k++] = oddlist.get(i); } for(int i = 0; i < evenlist.size(); i++) { array[k++] = evenlist.get(i); } } }思路2：(无法保证相对位置不变)
用两个指针i，j，有点像快排的partation。
初始化时，i指向数组中的第一个数字，j指向最后一个数字。向后移动i，直到遇到一个偶数向前移动j，直到遇到一个奇数交换i，j指向的偶数和奇数重复上述步骤，直到i、j相遇 public boolean isEven(int n) { return (n & 1) == 0; } public void reOrderArray(int [] array) { int i = 0; int j = array.length-1; while(i < j) { while(i < j && !isEven(array[i])) i++; while(i < j && isEven(array[j])) j--; if(i < j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } }