思路,把原数组分成一个奇数组一个偶数组,再按顺序复制回去,这样,只需要遍历两次原数组即可。(一次读出,一次写入)
空间效率下降,因为额外有两个数组用于记录,但时间效率较好。

public void reOrderArray(int [] array) {
    //所以此时,这两个array长度都==原array长度,所以需要oddLength,evenLength记录其有意义值的真实长度
    //也可先遍历原数组,确定奇偶数的个数再建立奇偶数组,但要多遍历一次。
    int[] arrayOdd = new int[array.length];
    int[] arrayEven = new int[array.length];
    int counter = 0, counterOdd = 0, counterEven = 0;
    int oddLength = 0, evenLength = 0;
    while(counter<array.length){
        if(array[counter]%2==0){//even
            arrayEven[counterEven] = array[counter];
            counterEven++;
            evenLength++;
        }else{//odd
            arrayOdd[counterOdd] = array[counter];
            counterOdd++;
            oddLength++;
        }
        counter++;
    }
    for(int i=0;i<oddLength;i++){
        array[i] = arrayOdd[i];
    }
    for(int i=0;i<evenLength;i++){
        array[i+oddLength] = arrayEven[i];
    }
}