剑指offer----调整数组顺序使奇数位于偶数前面

题目： 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

方法一：

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

不需要额外的空间 时间复杂度为O(n^2),类似于冒泡排序，不断的将偶数向后移动，
移动的条件位当前位置的值是偶数，下一个节点是奇数
最后一个没有排序好偶数的后面，要么是界外，要么就是一个或者几个奇数，所以一定会把这个偶数移动到所有的奇数的后面。
方法二：

public class Solution {
    public void reOrderArray(int [] array) {
        int[] newArray = new int[array.length];
        int odd = 0;
        int even = 0;
        for(int i = 0; i < array.length; i++){
            if((array[i]&1) == 1)
                even++;
        }
        int oddCount = even;
        for(int i = 0; i < array.length; i++){
            if((array[i]&1) == 1){
                array[odd++] = array[i];
            }else{
                newArray[even++] = array[i];
            }
        }
        for(int i = oddCount; i < array.length; i++){
            array[i] = newArray[i];
        }
    }
}

用一个数组额外空间来换取时间 ，时间复杂度为O(n)
这个就很简单了，先求出奇数的个数，然后将偶数复制到新数组的对应位置，奇数复制到老数组的对应位置。
最后将新数组中偶数填充到老数组中对应位置即可。