调整数顺序使奇数位于偶数前面

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

剑指offer_14 调整数顺序使奇数位于偶数前面

2018/05/14 星期一

题目：输入一个整数数组，实现一个函数用来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

思考三分钟。。。

一个简单的思路就是，顺序遍历数组，当我们碰到偶数的时候，就将该偶数后面的所有数字往前移一位，然后将该偶数放到数组移动后末尾挪出来的位置之中。整个时间复杂度 $O(n^2)$ 。

只完成基本功能的解法

这个题目要求把所有的奇数放在数组的前半部分，偶数放在数组的后半部分。也就是说，如果我们在扫描这个数组的时候，如果发现有偶数在奇数的前面，我们就可以交换他们的顺序。

因此，可以维护两个指针，一个指针初始化指向数组的第一个元素，往后一定；另一个指针指向数组的后面一个元素，往前移动。在两个指针相遇之前，第一个指针总是在第二个指针的前面，如果第一个指针指向的是偶数，就和第二个指针中指向的奇数进行互换。下面以数组{1,2,3,4,5}为例说明。

调整数组{1,2,3,4,5}使得奇数位于偶数前面的过程

图的说明：

图（a）中把第一个指针指向数组的第一个数字，第二个指针指向数组的第二个位置
向后移动第一个指针，使它指向一个偶数；向前移动第二个指针，使它指向一个奇数
交换此时两个指针指向的值。
继续前面1,2,3等操作，直到第二个指针移动到了第一个指针的前面。

基于上面的分析，写下如下Java代码。

public void ReorderOddEven(int[] array) {if (array == null || array.length == 0) {return;}int pStart = 0;int pEnd = array.length - 1;while (pEnd > pStart) {// 向后移动，直到它指向偶数while (!isEven(array[pStart])) {pStart++;}// 向前移动，直到它指向奇数while (isEven(array[pEnd])) {pEnd--;}if (pEnd > pStart) {// 交换swap(array, pStart, pEnd);}}
}public void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;
}private boolean isEven(int n) {
//         return n % 2 == 0;return (n & 0x1) == 0;
}

考虑可扩展的解法

如果是资深的开发职位，需要考虑程序的扩展性，提出能够解决这一系列问题的解法。例如，数组中按照大小分为两个部分，前面为负数后面为非负数；能被3整数和不能被3整除的数等等。就是将前面的函数解耦出两部分：一是判断数字应该在数组的前半部分还是后半部分，二是拆分数组的操作。（前面代码已经完成了这部分解耦工作）

测试用例：