Array-905. Sort Array By Parity

题目：
非负数组A包含偶数和奇数，将所有奇数排列在所有偶数后边

例子：
Input: [3,1,2,4]Output: [2,4,3,1]The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

想法：本来想用一个标志位p来标识最后一个偶数，如果再遍历到偶数则和标志位下一位的奇数交换，这样，时间复杂度为O(n)，空间复杂度为O（1）；但是仔细推敲是有问题的。

最后用了最笨的方法，即遍历找到偶数和奇数，再拼接起来，程序如下：

class Solution {
    public int[] sortArrayByParity(int[] A) {
        if(A.length<=0||A==null)return null;
        int length=A.length;
        int n=0;
        for(int i=0;i<length;i++){
            if(A[i]%2==0){
                n++;
            }
        }
        int[] AParity=new int[n];
        int[] BOdd=new int[length-n];
        int j=0;
        int i=0;
        int z=0;
        int m=0;
        while (j<length){
            if(A[j]%2==0){
                AParity[i]=A[j];
                i++;
            }else {
                BOdd[z]=A[j];
                z++;
            }
            j++;
        }
        while (m<length){
            if(m<n){
                A[m]=AParity[m];
            }
            else{
                A[m]=BOdd[m-n];
            }
            m++;
        }
        return A;
    }
}

这样可以实现，但是过于繁复，25ms的通过时间。看了大神们的解答，有的独辟蹊径，有的跟我的想法一样，但更简单。我与大神只差10000步。

神1：用是否为偶数重写Arrays的排序算法

class Solution {
    public int[] sortArrayByParity(int[] A) {
        Integer[] B = new Integer[A.length];
        for (int t = 0; t < A.length; ++t)
            B[t] = A[t];
        Arrays.sort(B, (a, b) -> Integer.compare(a%2, b%2));
        for (int t = 0; t < A.length; ++t)
            A[t] = B[t];
        return A;
        /* Alternative:
        return Arrays.stream(A)
                     .boxed()
                     .sorted((a, b) -> Integer.compare(a%2, b%2))
                     .mapToInt(i -> i)
                     .toArray();
        */
    }
}

鉴于比较函数 Integer.compare还没搞懂，现在无法验证这种方法。

神2：遍历两遍A[n]，找到奇偶数放到另一个数组中

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int[] ans = new int[A.length];
        int t = 0;
        for (int i = 0; i < A.length; ++i)
            if (A[i] % 2 == 0)
                ans[t++] = A[i];
        for (int i = 0; i < A.length; ++i)
            if (A[i] % 2 == 1)
                ans[t++] = A[i];
        return ans;
    }
}