題目：
輸入一個(gè)整數(shù)數(shù)組聂受，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序杂伟，使得所有的奇數(shù)位于數(shù)組的前半部分剃毒，所有的偶數(shù)位于數(shù)組的后半部分
思路：
（摘抄劍指offer）維護(hù)兩個(gè)指針：pBegin斩芭、pEnd典勇。pBegin初始化時(shí)指向數(shù)組的第一個(gè)數(shù)字桅锄，它只向后移動(dòng)琉雳；pEnd初始化時(shí)指向數(shù)組最后一個(gè)數(shù)字，它只能向前移動(dòng)友瘤。
在兩個(gè)指針相遇之前翠肘，第一個(gè)指針總是位于第二個(gè)指針的前面。
如果第一個(gè)指針指向的數(shù)字是偶數(shù)辫秧，并且第二個(gè)指針指向的數(shù)字是奇數(shù)束倍，就交換這兩個(gè)數(shù)字。
解答：
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
//正常數(shù)組
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();
//數(shù)組為空
int[] arrays2 = null;
solution.reOrderArray(arrays2);
System.out.println();
//數(shù)組只有一個(gè)數(shù)
int[] arrays3 = new int[]{3};
solution.reOrderArray(arrays3);
Arrays.stream(arrays3).forEach(i->System.out.print(i + " "));
System.out.println();
}
/**
* 重排數(shù)組
* @param array
*/
public void reOrderArray(int[] array) {
if (array == null || array.length <= 0) {
return;
}
//定義兩個(gè)指針
int pBegin = 0;
int pEnd = array.length - 1;
//當(dāng)前指針與后指針沒(méi)有相交
while (pBegin < pEnd) {
//當(dāng)前指針遇到偶數(shù)停止
while (pBegin < pEnd && !isEven(array[pBegin])) {
pBegin++;
}
//當(dāng)后指針遇到奇數(shù)停止
while (pBegin < pEnd && isEven(array[pEnd])) {
pEnd--;
}
//交換
if (pBegin < pEnd) {
swap(array, pBegin, pEnd);
}
}
}
/**
* 兩數(shù)交換
*
* @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;
}
/**
* 是否為偶數(shù)
*
* @param num
* @return
*/
private boolean isEven(int num) {
return (num & 0x1) == 0;
}
}
擴(kuò)展
琶讼罚客上該題目有額外要求：并保證奇數(shù)和奇數(shù)绪妹，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。
上面的解法就不再可行柿究。所以只能采用前后值對(duì)比的形式邮旷。
定義兩個(gè)指針（下標(biāo)）：pBegin、pEnd蝇摸。
外層遍歷數(shù)組廊移，當(dāng)遇到偶數(shù)時(shí)，pBegin記錄當(dāng)前偶數(shù)下標(biāo)探入，此時(shí)繼續(xù)遍歷數(shù)組直到遇到奇數(shù)pEnd狡孔。
那么[pBegin,pEnd)之間下標(biāo)對(duì)應(yīng)值都是偶數(shù)。此時(shí)將[pBegin,pEnd)對(duì)應(yīng)值往后移動(dòng)一位,p[pBegin]=array[pEnd]蜂嗽。這樣就實(shí)現(xiàn)了奇數(shù)移到了偶數(shù)的前面苗膝。
解法：
package com.qingcong.system.codeGenerator;
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
//正常數(shù)組
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();
//數(shù)組為空
/* int[] arrays2 = null;
solution.reOrderArray(arrays2);
System.out.println();
//數(shù)組只有一個(gè)數(shù)
int[] arrays3 = new int[]{3};
solution.reOrderArray(arrays3);
Arrays.stream(arrays3).forEach(i->System.out.print(i + " "));
System.out.println();*/
}
/**
* 重排數(shù)組
* @param array
*/
public void reOrderArray2(int[] array) {
if (array == null || array.length <= 0) {
return;
}
//指向第一個(gè)偶數(shù)
int pBegin = 0;
//指向第一個(gè)奇數(shù)
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]移到最前面，所有的偶數(shù)往后移
if (pBegin != pEnd && pEnd < array.length) {
int temp = array[pEnd];
while (pEnd > pBegin) {
array[pEnd] = array[--pEnd];
}
array[pBegin] = temp;
}
}
}
}
/**
* 是否為偶數(shù)
*
* @param num
* @return
*/
private boolean isEven(int num) {
return (num & 0x1) == 0;
}
}
擴(kuò)展性
為什么需要單獨(dú)實(shí)現(xiàn)個(gè)isEven方法植旧？
如果題目要求的是能被3整除的移到前面辱揭，不能被整除的移到后面〔「剑或者是負(fù)數(shù)都要求在非負(fù)數(shù)前面问窃。我們可以用一個(gè)函數(shù)來(lái)判斷數(shù)字是否符合標(biāo)準(zhǔn)，在reOrderArray中被調(diào)用完沪，而不再需要重寫(xiě)類(lèi)似的reOrderArray函數(shù)域庇。
