面试题14. 调整数组顺序使奇数位于偶数前面

本文主要是介绍面试题14. 调整数组顺序使奇数位于偶数前面，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

思路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;}}
}