題目21：調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前
輸入一個(gè)整數(shù)數(shù)組市咽，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，所有偶數(shù)位予數(shù)組的后半部分。
舉例說(shuō)明
輸入數(shù)組{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}镊逝，
輸出{9,1,7,3,5,4,6,2,8,0};
思路
具體分析
這個(gè)題目要求把奇數(shù)放在數(shù)組的前半部分， 偶數(shù)放在數(shù)組的后半部分嫉鲸，因此所有的奇數(shù)應(yīng)該位于偶數(shù)的前面撑蒜。也就是說(shuō)我們?cè)趻呙柽@個(gè)數(shù)組的時(shí)候，** 如果發(fā)現(xiàn)有偶數(shù)出現(xiàn)在奇數(shù)的前面玄渗，我們可以交換它們的順序乖坠，交換之后就符合要求了**
- 因此我們可以維護(hù)兩個(gè)指針经备，在兩個(gè)指針相遇之前啊终，第一個(gè)指針總是位于第二個(gè)指針的前面规丽。
- 移動(dòng)
2.1 第一個(gè)指針初始化時(shí)指向數(shù)組的第一個(gè)數(shù)字，它只向后移動(dòng)
2.2 第二個(gè)指針初始化時(shí)指向數(shù)組的最后一個(gè)數(shù)字也榄， 它只向前移動(dòng) - 如果第一個(gè)指針指向的數(shù)字是偶數(shù)巡莹，并且第二個(gè)指針指向的數(shù)字是奇數(shù)，我們就交換這兩個(gè)數(shù)字
代碼實(shí)現(xiàn)
public class _21 {
public static void reorderOddEven(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int begin = 0;// 從左向右記錄偶數(shù)的位置
int end = arr.length - 1;// 從右向左記錄奇數(shù)的位置
while (begin < end) {
// 從頭往尾找偶數(shù) ：當(dāng)前位置是奇數(shù)就 一直后移
while (begin < end && (arr[begin] & 0x01) == 1) {
begin++;
}
// 從尾往頭找奇數(shù) ：當(dāng)前位置是偶數(shù)就 一直前移
while (begin < end && (arr[end] & 0x01) == 0) {
end--;
}
// 找到后就將奇數(shù)和偶數(shù)交換位置
// 對(duì)于start=end的情況甜紫，交換不會(huì)產(chǎn)生什么影響,所以將if判斷省去了
int tmp = arr[begin];
arr[begin] = arr[end];
arr[end] = tmp;
}
}
// for test
public static void printArray(int[] arr) {
if (arr != null && arr.length > 0) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
reorderOddEven(array);
printArray(array);
}
}
輸出：
9 1 7 3 5 4 6 2 8 0
