调整数组顺序使得偶数在前，奇数在后，且不改变相对次序

题目

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

解决

1. 搜索+交换
   首先是一种错误的解法：index1向右寻找一个偶数，令index2=index1+1，然后index2向右寻找一个奇数，若找到了，则交换array[index1]与array[index2]，否则说明已经满足条件

public void reOrderArray(int [] array) {
        int index1 = 0;
        int index2 = 0;
        while(index2<array.length){
            while(index1<array.length && array[index1] % 2 == 1)
                index1 ++;
            if(index1 >= array.length-1)
                return;
            index2 = index1 + 1;
            while(index2<array.length && array[index2] % 2 ==0)
                index2 ++;
            if(index2 == array.length)
                return;
            swap(array,index1,index2);
        }
  }

此方式不满足偶数相对位置不变的条件，其原因在于交换元素时，若两个指针之间存在偶数，则交换操作便打乱了它们之间的相对次序。注意到这点之后我们还发现，若两指针不相邻，则中间元素一定全为偶数，而在index2处只需填入一个偶数即可，不一定非要是array[index1]，那么改进的方法便是将index2指向的元素插入index1所指位置，其后所有元素向后移动，即：

来自Ariser.cn

将上述代码的swap方法改为move方法即可：

    public void move(int[] array,int index1,int index2){
        int t = array[index2];
        for(int i=index2-1;i>=index1;i--){
            array[i+1] = array[i];
        }
        array[index1] = t;
    }

2. 使用两个辅助数组
   该方法更加直观简单，时间复杂读为O(n)，牺牲了一点空间

public void reOrderArray(int [] array) {
        int[] a = new int[array.length];
        int[] b = new int[array.length];
        int ia = 0;
        int ib = 0;
        for(int i=0;i<array.length;i++){
            if(array[i]%2 == 0){
                b[ib] = array[i];
                ib ++;
            }
            else{
                a[ia] = array[i];
                ia ++;
            }
        }
        for(int i=0;i<ia;i++)
            array[i] = a[i];
        for(int i=0;i<ib;i++)
            array[i+ia] = b[i];
    }

3. 利用冒泡排序或插入排序
   冒泡排序是稳定的排序方法，可以将判定条件改为：两两比较，若前为偶后为奇则交换，否则不变。同理也可以类似地改造插入排序、希尔排序等稳定排序算法来实现。这些方法最简单，但时间复杂度为O（n^2）

public void reOrderArray(int [] array) {
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]%2==0 && array[j+1]%2==1){
                    int t = array[j];
                    array[j] = array[j+1];
                    array[j+1] = t;
                }
            }
        }
    }