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

我们可以维护两个指针，第一个指针初始化时指向数组的第一个数字，它只向后移动；第二个指针初始化时指向数组的最后一个数字，它指向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。

如果第一个指针的数字是偶数，并且第二个指针指向的数字是奇数，我们就交换两个数字。

public class OddBeforeEven {
 
    public int[] recorderOddEven(int[] data, int length){
        if(data == null && length <= 0){
            return null;
        }
        
        int begin = 0;
        int end = length - 1;
        
        // begin指针要位于end指针前面
        while(begin < end){
            // 向后移动begin指针，直到它指向偶数
            if(begin < end && (data[begin] & 0x1) != 0){
                begin++;
            }
            
            // 向前移动end指针，直到它指向奇数
            if(begin < end && (data[end] & 0x1) == 0){
                end--;
            }
            
            // 交换奇数和偶数的位置
            if(begin < end){
                int temp = data[begin];
                data[begin] = data[end];
                data[end] = temp;
            }
        }
        return data;
    }
    
    // 测试
    public static void main(String[] args) {
        OddBeforeEven obe = new OddBeforeEven();
        int[] arr= {1,2,3,4,5,6,12,7,8,9,10};
        int[] data = obe.recorderOddEven(arr, arr.length);
        System.out.println(Arrays.toString(data));
    }
}

考虑可扩展

如果把题目改成数组中的数按照大小分为两部分，所有的负数在所有的非负数的前面，该怎么做？
如果再把题目改改，变成把数组中的数分成两部分，能被3整除的数都在不能被3整除的数的前面，怎么办？

希望我们能够给出一个模式，在这个模式下能够很方面第把已有的解决方案扩展到同类型的问题上去。

public class OddBeforeEvenExtension {
 
    public int[] recorderOddEven(int[] data, int length){
        if(data == null && length <= 0){
            return null;
        }
        
        int begin = 0;
        int end = length - 1;
        
        // begin指针要位于end指针前面
        while(begin < end){
            // 向后移动begin指针，直到它指向偶数
            if(begin < end && !isEven(data[begin])){
                begin++;
            }
            
            // 向前移动end指针，直到它指向奇数
            if(begin < end && isEven(data[end])){
                end--;
            }
            
            // 交换奇数和偶数的位置
            if(begin < end){
                int temp = data[begin];
                data[begin] = data[end];
                data[end] = temp;
            }
        }
        return data;
    }
    // 扩展函数
    private boolean isEven(int data) {
        return (data & 0x1) == 0;
    }
 
    // 测试
    public static void main(String[] args) {
        OddBeforeEvenExtension obe = new OddBeforeEvenExtension();
        int[] arr= {1,2,3,4,5,6,12,7,8,9,10};
        int[] data = obe.recorderOddEven(arr, arr.length);
        System.out.println(Arrays.toString(data));
    }
}

这样如果增加额外的判断条件，只需要改变isEven函数中的逻辑即可，对于recorderOddEven函数中的主体逻辑框架无需改变，这样就实现了解耦。

参考

【剑指offer】面试题21：调整数组顺序使奇数位于偶数前面