題目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ù)的前面，我們可以交換它們的順序，交換之后就符合要求了**

1. 因此我們可以維護(hù)兩個(gè)指針，在兩個(gè)指針相遇之前，第一個(gè)指針總是位于第二個(gè)指針的前面。
2. 移動(dòng)
   2.1 第一個(gè)指針初始化時(shí)指向數(shù)組的第一個(gè)數(shù)字，它只向后移動(dòng)
   2.2 第二個(gè)指針初始化時(shí)指向數(shù)組的最后一個(gè)數(shù)字， 它只向前移動(dòng)
3. 如果第一個(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