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

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

import java.util.ArrayList;
public class Solution {
    public void reOrderArray(int [] array) {
        ArrayList<Integer> list = new ArrayList<>();
        //第一次遍历取出所有奇数
        for(int i=0; i<array.length; i++){
            if(array[i]%2!=0){
                list.add(array[i]);
            }
        }
        //第二次遍历取出所有偶数
        for(int i=0; i<array.length; i++){
            if(array[i]%2==0){
                list.add(array[i]);
            }
        }
        
        //第二次遍历取出所有偶数
        for(int i=0; i<array.length; i++){
            array[i]=list.get(i);
        }
    }
}

第二遍做的时候，如果不考虑保持原有顺序，比较好的做法：

import java.util.ArrayList;
public class Solution {
    public void reOrderArray(int [] array) {
        //用两个指针，一个指向头部，一个指向尾部
        int a = 0;
        int b = array.length-1;
        while(a<b){
            //如果前端是奇数
            if(array[a]%2!=0){
                a++;
                continue;
            }
            //如果后端是偶数
            if(array[b]%2==0){
                b--;
                continue;
            }
            //如果前端是偶数，后端是奇数，交换位置
            if(array[a]%2==0 && array[b]%2!=0){
                int tmp = array[a];
                array[a] = array[b];
                array[b] = tmp;
                a++;
                b--;
            }
        }
    }
}

当然了，题目要求保持原有的奇数和奇数顺序、偶数和偶数的顺序，如果再要求只能在原数组上进行操作：

import java.util.ArrayList;
public class Solution {
    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!=0){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }
}