905. Sort Array By Parity

使一个数组偶数在前，奇数在后。 首先使用while找到第一个奇数和第一个偶数出现的位置，然后进行交换。

public int[] sortArrayByParity(int[] A) {
    int l = 0, r = A.length - 1;
    while (l < r) {
        while (l < r && (A[l] & 1) == 0) l++; // even++
        while (l < r && (A[r] & 1) == 1) r--; // odd--

        int tmp = A[l];  //swap
        A[l] = A[r];
        A[r] = tmp;
    }
    return A;
}

写成单独的函数：

public int[] sortArrayByParity(int[] A) {
    int l = 0, r = A.length - 1;
    while (l < r) {
        while (l < r && isEven(A[l])) l++;
        while (l < r && !isEven(A[r])) r--;

        int tmp = A[l];
        A[l] = A[r];
        A[r] = tmp;
    }
    return A;
}

public boolean isEven(int n) {
    return (n & 1) == 0;
}

保持奇偶的顺序，用插入排序

for (int i = 1; i < array.length; i++) {
    int key = array[i];
    if (!isEven(key)) { // 如果第一个数是奇数，需要将它排在前面
        int j = i;
        while (j > 0 && isEven(array[j - 1])) { // 没有越界且它的前面是偶数
            array[j] = array[j - 1];
            j--;
        }
        array[j] = key;
    }
}

public boolean isEven(int n) {
    return (n & 1) == 0;
}