面试题 21：调整数组顺序使奇数位于偶数前面

题目描述

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

思路

定义两个指针。

第一个指针 begin 指向数组的第一个数字

开始遍历数组

只要 begin 指向的数字是奇数，则向后一位，依次判断

当 begin 指向的数字是偶数，则让第二个指针 end 指向 begin + 1 的位置。

然后开始判断 end 所指向的数字是不是偶数，如果是继续往后判断，直至遇到奇数为止。

当 end 指向的是奇数的时候，先将 arr[end] 的数字保存，再将 [begin, end - 1] 的数字都往后整体移动一位。

移动完毕后，将 arr[end] 的数字赋值给 arr[begin]，然后 begin 加 1。

只要 end 超出数组的索引范围，则继续判断剩余部分数字的奇偶。

代码

public class Solution {
    public void reOrderArray(int [] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int begin = 0;
        int end = 0;
        
        while (end < array.length) {
            // 判断是否是奇数
            while (begin < array.length && !isEven(array[begin])) {
                begin++;
            }
            
            // end == 0 用来防止重复判断已经查找到的偶数
            if (end == 0) {
                end = begin + 1;
            }

            // 判断是否是偶数
            while (end < array.length && isEven(array[end])) {
                end++;
            }

            // 只要 end 没有超出索引范围，说明找到了一个奇数，整体移位操作
            if (end < array.length) {
                int temp = array[end];
                for (int i = end - 1; i >= begin; i--) {
                    array[i + 1] = array[i];
                }
                array[begin] = temp;
                begin++;
                end++;
            }
        }
    }

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