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

题目：

​ 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

分析：

​ 如果不考虑时间复杂度，最简单的思路是从头扫描这个数组，每碰到一个偶数，拿出这个数字，并把这个数字后面的所有数向前挪动一位。挪动之后，数组末尾有一个空位，把这个偶数放入空位。

方法：

​ 使用两个指针，start 指向数组的第一个数字，它只向后移动；end 指向数组的最后一个数字，它只向前移动。在两个指针相遇之前，start 总是位于 end 的前面。如果 start 指向的数字是 偶数 并且 end 指向的数字是奇数，交换这两个数字。

代码：

public class ChangeArray {

    public static void change(int[] arr) {
        if (null == arr || arr.length == 0) {
            return;
        }

        int start = 0;
        int end = arr.length -1;
        while (start < end) {
            // 向后移动 start，直到它指向偶数
            while (start < end && (arr[start] & 0x1) != 0) {
                start++;
            }
            // 向前移动end， 直到它指向奇数
            while (start < end && (arr[end] & 0x1) == 0) {
                end --;
            }
            //  交换奇数和偶数位置
            if (start < end) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
        }
    }
}

扩展：

​ 如果所有负数放在数组前面，非负数放在数组后面；或者不能被3整除放在前面，能被3整除放在后面应该怎样设计？

​ 主要的逻辑可以不用改变，主要修改对数值的判断。所以为了灵活，可以把判断逻辑单独抽离出来。代码如下：

public static void changePredicate(int[] arr, Predicate<Integer> predicate) {
    if (null == arr || arr.length == 0) {
        return;
    }
    int start = 0;
    int end = arr.length -1;
    while (start < end) {
        while (start < end && !predicate.test(arr[start])) {
            start++;
        }
        while (start < end && predicate.test(arr[end])) {
            end--;
        }
        if (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
    }
}

测试：

@Test
public void test2() {
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 12, 14, 15, 21};
    ChangeArray.changePredicate(arr, a -> a % 3 == 0);
    System.out.println(Arrays.toString(arr));
}