題目

實現(xiàn)函數(shù)：輸入一個整數(shù)數(shù)組，調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對位置不變。

解決

1. 搜索+交換
   首先是一種錯誤的解法：index1向右尋找一個偶數(shù)，令index2=index1+1，然后index2向右尋找一個奇數(shù)，若找到了，則交換array[index1]與array[index2]，否則說明已經(jīng)滿足條件

public void reOrderArray(int [] array) {
        int index1 = 0;
        int index2 = 0;
        while(index2<array.length){
            while(index1<array.length && array[index1] % 2 == 1)
                index1 ++;
            if(index1 >= array.length-1)
                return;
            index2 = index1 + 1;
            while(index2<array.length && array[index2] % 2 ==0)
                index2 ++;
            if(index2 == array.length)
                return;
            swap(array,index1,index2);
        }
  }

此方式不滿足偶數(shù)相對位置不變的條件，其原因在于交換元素時，若兩個指針之間存在偶數(shù)，則交換操作便打亂了它們之間的相對次序。注意到這點之后我們還發(fā)現(xiàn)，若兩指針不相鄰，則中間元素一定全為偶數(shù)，而在index2處只需填入一個偶數(shù)即可，不一定非要是array[index1]，那么改進的方法便是將index2指向的元素插入index1所指位置，其后所有元素向后移動，即：

來自Ariser.cn

將上述代碼的swap方法改為move方法即可：

    public void move(int[] array,int index1,int index2){
        int t = array[index2];
        for(int i=index2-1;i>=index1;i--){
            array[i+1] = array[i];
        }
        array[index1] = t;
    }

2. 使用兩個輔助數(shù)組
   該方法更加直觀簡單，時間復雜讀為O(n)，犧牲了一點空間

public void reOrderArray(int [] array) {
        int[] a = new int[array.length];
        int[] b = new int[array.length];
        int ia = 0;
        int ib = 0;
        for(int i=0;i<array.length;i++){
            if(array[i]%2 == 0){
                b[ib] = array[i];
                ib ++;
            }
            else{
                a[ia] = array[i];
                ia ++;
            }
        }
        for(int i=0;i<ia;i++)
            array[i] = a[i];
        for(int i=0;i<ib;i++)
            array[i+ia] = b[i];
    }

3. 利用冒泡排序或插入排序
   冒泡排序是穩(wěn)定的排序方法，可以將判定條件改為：兩兩比較，若前為偶后為奇則交換，否則不變。同理也可以類似地改造插入排序、希爾排序等穩(wěn)定排序算法來實現(xiàn)。這些方法最簡單，但時間復雜度為O（n^2）

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