題目描述：輸入一個整數(shù)數(shù)組，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分。

思路1：暴力解法
從頭到尾掃描一遍數(shù)組，每遇見一個偶數(shù)時，就拿出這個數(shù)字，并把位于這個數(shù)字之后的所有數(shù)字往前挪動一位,然后把當前這個偶數(shù)放到最后。
這樣每次遇到一個偶數(shù)就要挪動O(n)個數(shù)字，因此總的時間復雜度是O(n2)
但是這種方法不僅暴力而且還需要復雜的挪動工作。

public void reOrderArray(int[] array) {
        if(array == null) {
            return;
        }
        for(int i=0;i<array.length;i++) {
            int j = i;
            if(array[i]%2 == 0) {
                int temp = array[i];
                while(j<array.length-1) {
                    array[j] =array[j+1];
                    j++;
                }
                array[j] = temp;
            }
        }
    }

思路2：冒泡解法
冒泡排序，每次循環(huán)前偶后奇就交換。同時我們設立一個標識，來標識數(shù)組是否已經(jīng)符合要求。當再次循環(huán)時，發(fā)現(xiàn)沒有要交換的數(shù)據(jù)，說明數(shù)組已經(jīng)符合要求。
由于冒泡法比較相鄰兩個元素，因此奇數(shù)或者偶數(shù)的相對順序不變，是穩(wěn)定的。

public void reOrderArray2(int[] array) {
        if(array == null) {
            return;
        }
        boolean flag = true;
        for(int i=0;i<array.length-1 && flag;i++) {
            flag = false;
            for(int j=0;j<array.length-1-i;j++) {
                if(array[j]%2==0 && array[j+1]%2!=0) {
                    int temp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = temp;
                    flag = true;   //當有數(shù)據(jù)交換時則 flag 設置為true
                }
            }
        }
    }

思路3：利用一個輔助的數(shù)組空間來實現(xiàn)
在原來的數(shù)組中遇到偶數(shù)就放進新數(shù)組中，遇到奇數(shù)就將奇數(shù)移動到原來數(shù)組奇數(shù)下標的后面（第一次移動奇數(shù)到數(shù)組的開頭），當整個遍歷結束后，最后我們將新的數(shù)組追加在原來數(shù)組奇數(shù)下標的后面即可。

public void reOrderArray3(int[] array) {
        if(array == null) {
            return;
        }
        int[] auxiliaryArray = new int[array.length];
        int auxiliaryIndex = -1;  //輔助數(shù)組的下標
        int index = 0;  //原數(shù)組的下標，用于控制奇數(shù)的位置（偶數(shù)插入的下標）
        for(int i=0;i<array.length;i++) {
            if(array[i]%2 == 0) {
                auxiliaryArray[++auxiliaryIndex] = array[i];
                continue;
            }
            array[index ++] = array[i];
        }
        for(int j=index;j<array.length;j++) {
            array[index ++] = auxiliaryArray[auxiliaryIndex--];
        }
    }

思路4：高效的解法，維護2個指針
由于題目中只要求記奇數(shù)在偶數(shù)之前，那么我們在掃描這個數(shù)組的時候，如果發(fā)現(xiàn)一個偶數(shù)出現(xiàn)在奇數(shù)之前就交換他們的位置，這樣一趟后就滿足要求了。
因此我們 維護兩個索引或者指針，一個指向數(shù)組的第一個元素，并向后移動，一個指向數(shù)組的最后一個元素，并向前移動。
如果第一個指針指向的元素是偶數(shù)，而第二個指針指向的元素是奇數(shù)，說明偶數(shù)在奇數(shù)前面，那么就交換這兩個數(shù)，直到兩個指針相遇為止。
這種算法不能保證相同類型數(shù)據(jù)的相對位置不變，因此不穩(wěn)定。

public void reOrderArray4(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            while (left < right && (array[left] &1) != 0) {
                left++;
            }
            while (left < right && (array[right] &1) == 0) {
                right--;
            }

            if (left < right) {
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }
    }

思路5：考慮可擴展性的解法（即解耦）。
這不僅是解決一個問題的辦法，而是解決一系列同類型問題的通用辦法。對擴展性的理解，能夠給出一個模式，在這個模式下能夠很方便地把已有的解決方案擴展到同類型的問題上。
比如（1）把數(shù)組中的數(shù)按照大小分成兩部分，所有負數(shù)都在非負數(shù)的前面。
（2）把數(shù)組中的數(shù)分為兩部分，能被3整除的數(shù)都在不能被3整除的數(shù)的前面。

public void reOrderArray5(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            while (left < right && !isEven(array[left])) {
                left++;
            }
            while (left < right && isEven(array[right])) {
                right--;
            }

            if (left < right) {
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }
    }
    //even是偶數(shù)的意思，odd是奇數(shù)的意思
    private boolean isEven(int n) {
        //是奇數(shù)的話n & 1為1，返回false
        //偶數(shù)的話n & 1為0，返回true
        return (n & 1) == 0;
    }