[劍指offer] 調整數組順序使奇數位于偶數前面

題目描述

輸入一個整數數組，實作一個函數來調整該數組中數字的順序，使得所有的奇數位于數組的前半部分，所有的偶數位于位于數組的後半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變。

參考代碼

最簡單的方法就是把奇數和偶數按順序挑出來，分别放到vector裡，最後再把偶數的vector接到奇數vector的末尾。

import java.util.Vector;
public class Solution {
    public void reOrderArray(int [] array) {
        Vector<Integer> odd = new Vector<Integer>();
        Vector<Integer> even = new Vector<Integer>();
        for(int i = 0; i < array.length; i++){
            if(array[i]%2 == 0){
                even.add(array[i]);
            }else{
                odd.add(array[i]);
            }
        }
        odd.addAll(even);
        for(int i=0;i<array.length;i++){
            array[i] = odd.get(i);
        }
    }
}
           

如果不能開僻額外的空間，可以嘗試有類似于冒泡排序的方法,如果目前的值為偶數，後一個值為奇數，則兩個數對換位置：

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