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

浏览数：19 / 时间：2015年06月08日

题目

　　输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)

思路

　　采用两个指针low、high，分别指向数组的头部跟尾部。low指针向后滑动，high指针向前滑动，low指针用来找偶数，high指针用来找基数，然后将两者交换，这类似于快速排序

代码实现

public class Algorithm {
    
    /**判断数字num是否为奇数*/
    public static boolean isEven(int num){
        /**位运算要比%要快*/
        if((num & 1) == 1)
            return true;
        return false;
    }
    
    public static void ReorderOddEven(int [] source) {
        int low = 0;
        int high = source.length - 1;
        while(low <= high) {
            /**找偶数*/
            while(isEven(source[low])) {
                ++low;
            }
            /**找奇数*/
            while(!isEven(source[high])) {
                --high;
            }
            if(low <= high) {
                /**交换*/
                int tmp = source[low];
                source[low] = source[high];
                source[high] = tmp;
            }
        }
    }
    
    public static void main(String []args) {
        int [] array = new int[]{2,4,5,6,3,8,1};
        Algorithm.ReorderOddEven(array);
        for(int num : array) {
            System.out.println(num);
        }
    }
}