题目：
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分
思路：
（摘抄剑指offer）维护两个指针：pBegin、pEnd。pBegin初始化时指向数组的第一个数字，它只向后移动；pEnd初始化时指向数组最后一个数字，它只能向前移动。
在两个指针相遇之前，第一个指针总是位于第二个指针的前面。
如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，就交换这两个数字。
解答：
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
//正常数组
int[] arrays = new int[]{1, 2, 3, 4, 5, 6, 7};
solution.reOrderArray(arrays);
Arrays.stream(arrays).forEach(i -> System.out.print(i + " "));
System.out.println();
//数组为空
int[] arrays2 = null;
solution.reOrderArray(arrays2);
System.out.println();
//数组只有一个数
int[] arrays3 = new int[]{3};
solution.reOrderArray(arrays3);
Arrays.stream(arrays3).forEach(i->System.out.print(i + " "));
System.out.println();
}
/**
* 重排数组
* @param array
*/
public void reOrderArray(int[] array) {
if (array == null || array.length <= 0) {
return;
}
//定义两个指针
int pBegin = 0;
int pEnd = array.length - 1;
//当前指针与后指针没有相交
while (pBegin < pEnd) {
//当前指针遇到偶数停止
while (pBegin < pEnd && !isEven(array[pBegin])) {
pBegin++;
}
//当后指针遇到奇数停止
while (pBegin < pEnd && isEven(array[pEnd])) {
pEnd--;
}
//交换
if (pBegin < pEnd) {
swap(array, pBegin, pEnd);
}
}
}
/**
* 两数交换
*
* @param array
* @param pBegin
* @param pEnd
*/
private void swap(int[] array, int pBegin, int pEnd) {
int temp = array[pBegin];
array[pBegin] = array[pEnd];
array[pEnd] = temp;
}
/**
* 是否为偶数
*
* @param num
* @return
*/
private boolean isEven(int num) {
return (num & 0x1) == 0;
}
}
扩展
牛客上该题目有额外要求：并保证奇数和奇数，偶数和偶数之间的相对位置不变。
上面的解法就不再可行。所以只能采用前后值对比的形式。
定义两个指针（下标）：pBegin、pEnd。
外层遍历数组，当遇到偶数时，pBegin记录当前偶数下标，此时继续遍历数组直到遇到奇数pEnd。
那么[pBegin,pEnd)之间下标对应值都是偶数。此时将[pBegin,pEnd)对应值往后移动一位,p[pBegin]=array[pEnd]。这样就实现了奇数移到了偶数的前面。
解法：
package com.qingcong.system.codeGenerator;
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
//正常数组
int[] arrays = new int[]{1, 2, 3, 4, 5, 6, 7};
solution.reOrderArray2(arrays);
Arrays.stream(arrays).forEach(i -> System.out.print(i + " "));
System.out.println();
//数组为空
/* int[] arrays2 = null;
solution.reOrderArray(arrays2);
System.out.println();
//数组只有一个数
int[] arrays3 = new int[]{3};
solution.reOrderArray(arrays3);
Arrays.stream(arrays3).forEach(i->System.out.print(i + " "));
System.out.println();*/
}
/**
* 重排数组
* @param array
*/
public void reOrderArray2(int[] array) {
if (array == null || array.length <= 0) {
return;
}
//指向第一个偶数
int pBegin = 0;
//指向第一个奇数
int pEnd = 0;
for (int i = 0; i < array.length; i++) {
if (isEven(array[i])) {
pBegin = i;
pEnd = pBegin + 1;
while (pEnd < array.length) {
if (!isEven(array[pEnd])) {
break;
}
pEnd++;
}
//将array[pEnd]移到最前面，所有的偶数往后移
if (pBegin != pEnd && pEnd < array.length) {
int temp = array[pEnd];
while (pEnd > pBegin) {
array[pEnd] = array[--pEnd];
}
array[pBegin] = temp;
}
}
}
}
/**
* 是否为偶数
*
* @param num
* @return
*/
private boolean isEven(int num) {
return (num & 0x1) == 0;
}
}
扩展性
为什么需要单独实现个isEven方法？
如果题目要求的是能被3整除的移到前面，不能被整除的移到后面。或者是负数都要求在非负数前面。我们可以用一个函数来判断数字是否符合标准，在reOrderArray中被调用，而不再需要重写类似的reOrderArray函数。
