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

package cn.zxy.interview;

import org.junit.Test;

import java.util.Arrays;

/**
 * 调整数组元素顺序, 是所有奇数在前半段, 所有偶数在后半段
 *
 * 维护两个指针, while前指针 使其指向一个偶数; while后指针, 使其指向一个奇数 交换
 * 重复 直到前指针与尾指针相遇
 *
 * 细节 使用位运算代替取模判断 二进制最后一位是1, 则该数为奇数 反之为偶数
 * 三个地方都要判断pBegin<pEnd
 *
 * 内层两个while如果不加, 就可能造成数组越界异常
 */

public class A21_ReorderOddEven {
    @Test
    public void main(){
        int[] arr = {3, 5, 2, 6, 4, 1, 7, 8, 9};
        reorder(arr);
        System.out.println(Arrays.toString(arr));
    }

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

        int pBegin = 0;
        int pEnd = arr.length-1;

        while (pBegin < pEnd){
            // 偶数时退出循环
            while(pBegin < pEnd && (arr[pBegin] & 0x1) != 0) pBegin++;
            while (pBegin < pEnd && (arr[pEnd] & 0x1) == 0) pEnd--;  // 最后一位是0 说明是奇数

            if(pBegin < pEnd){
                swap(arr, pBegin, pEnd);
            }
        }
    }

    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}