《剑指offer》面试题14 调整数组顺序使奇数位于偶数前面 Java版

（输入整数数组，使所有奇数位于前半部分，所有偶数位于后半部分。）

我的方法：想到用两个下标分别表示奇数和偶数的界线，一个在开头，一个在末尾，判断每一个数字的类别，然后将它放入对应的范围内，移动下标，直至两个下标相遇。两个下标，第一个index表示当前要检测的数字以及其左边的数字为奇数（所以当前要检测的数字为奇数的时候，index才会向右移动，否则是even向左移动），even表示其右边的数字为偶数，当index 大于 even的时候分割完毕。这里有个细节，在index表示index左边是奇数，even表示even右边是偶数的前提下 ，如果将while中的“<=”换成“<”（也就是index和even相遇时终止循环，相遇的这个元素无论偶奇不影响分割）也可以完成分割，但此时不知道最后一个元素到底是奇还是偶，如果while中的条件是“<=”（也就是index == even+1时终止循环），我们就可以知道确切的奇偶分界，这一点也可以利用到快速排序中。

public class PartitionInArray {
    public void partition(int[] a){
        if(a == null || a.length == 0)return;
        int index = 0;
        int even = a.length - 1;
        while(index <= even){
            if((a[index] & 0x01) == 1){
                index ++;
            }else{
                exch(a, index, even);
                even--;
            }
        }
    }

    private void exch(int[] a, int l, int m){
        int temp = a[l];
        a[l] = a[m];
        a[m] = temp;
    }
}

书中的方法：指针odd（odd左边为奇数）指向开头，指针even（even右边为偶数）指向末尾。同时移动，直到两指针“相遇”(书中是相遇就结束，这里我依旧用odd超过even结束)。

    public void partition2(int[] a){
        if(a == null || a.length == 0)return;
        int odd = 0;
        int even = a.length-1;
        while(true){
            while(odd <= even && isOdd(a[odd])){
                odd++;
            }
            while(odd <= even && !isOdd(a[even])){
                even--;
            }
            if(odd - even == 1){
                break;
            }
            exch(a, odd, even);
        }

    }

    private boolean isOdd(int m){
        if((m & 0x01) == 1){
            return true;
        }
        return false;
    }

联想：这里很自然地就想到了快速排序的分割——将数组分割成小于目标数字和大于等于目标数字两块，只需要把上述上述中的判断条件改了，同时选取一个用于分割的标准元素即可。