Given an arrayA of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that wheneverA[i]is odd,iis odd; and wheneverA[i]is even,iis even.

You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Note:

1. 2 <= A.length <= 20000
2. A.length % 2 == 0
3. 0 <= A[i] <= 1000

1.比较简单一点的方法是建立两个长度为原数组长度一半数组，分别存奇数和偶数，然后把奇数和偶数放到相应的位置上，问题是需要额外的空间。

2.我们可以用类似Sort Array By Parity I里的方法，先用3 way partition把原来的array分为奇数的一半和偶数的一半，偶数在前奇数在后，然后左边从index 1开始，右边从index A.length - 2开始交换元素位置，左边index自增2，右边index自减2，直到左边index到达数组中间

class Solution {
    public int[] sortArrayByParityII(int[] A) {
        if(A == null || A.length == 0)
            return A;

        int left = 0;
        int right = A.length - 1;
        int i = 0;

        while(i <= right) {
            if(A[i] % 2 == 0)
                swap(A, left++, i++);
            else
                swap(A, i, right--);
        }

        left = 1;
        right = A.length - 2;

        while(left <= A.length / 2 - 1) {
            swap(A, left, right);
            left += 2;
            right -= 2;
        }

        return A;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

3.另一种方法可以分别检查偶数index和奇数index，在两个位置数字都不符合要求的时候交换位置，这样做只需要遍历一遍数组

class Solution {
    public int[] sortArrayByParityII(int[] A) {
        if(A == null || A.length == 0)
            return A;

        int j = 1;
        for(int i = 0; i < A.length; i += 2) {
            if(A[i] % 2 == 1) {
                while(j < A.length && A[j] % 2 == 1)
                    j += 2;

                swap(A, i, j);
            }
        }

        return A;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}