调整数组顺序使奇数位于偶数前面

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
这个题目可以用插入排序的思想的来完成，算法比较简单，时间复杂度是O（nlogn）？

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

我当时第一次看到这个题目时，考虑可以新建一个数组，从两端扫描原数组，从两端向新数组内填充，可以在线性时间内完成。

public class Solution {
    public void reOrderArray(int [] array) {
        if(array==null||array.length==0)
            return ;
        int[] arr = new int[array.length];
        int index0 = 0;
        int index1 = array.length-1;
        for(int i=0;i<array.length;i++){
            if(array[i]%2!=0) arr[index0++]=array[i];
            if(array[array.length-1-i]%2==0) arr[index1--]=array[array.length-1-i];
        }
        for(int i = 0;i<array.length;i++)
            array[i]=arr[i];
    }
}