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

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

1.暴力破解法

import java.util.*;

public class Solution {
    public void reOrderArray(int [] a) {
        if(a==null || a.length ==0){
            return ;
        }
//a3存放奇数，a2存放偶数
        ArrayList<Integer> a3 = new ArrayList<Integer>();
        ArrayList<Integer> a2 = new ArrayList<Integer>();

        for(int i = 0,count = 0; i < a.length; i++){
            if(a[i] % 2 != 0){
                a3.add(a[i]);
            }else{
                a2.add(a[i]);
            }
        }

        Integer[] b1 = a3.toArray(new Integer[a3.size()]);
        Integer[] b2 = a2.toArray(new Integer[a2.size()]);
        for(int i = 0; i < b1.length; i++){
            a[i] = b1[i];
        }
        for(int i = 0,j = b1.length; i < b2.length; i++,j++){
            a[j] = b2[i];
        }
    }
}

2.参考快速排序

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int len = array.size();
        if(len <= 1){ // 数组空或长度为1
            return;
        }

        int i = 0;
        while(i < len){
            int j = i + 1;
            if(array[i]%2 == 0){ // a[i]为偶数，j前进，直到替换
                while(array[j]%2 == 0){ // j为偶数，前进
                    if(j==len-1)// i为偶数，j也为偶数，一直后移到了末尾，证明后面都是偶数
                         return;
                    j++;
                }
                // 此时j为奇数
                int count = j-i;
                int temp = array[i];
                array[i] = array[j];
                while(count>1){
                    array[i+count] = array[i+count-1];//数组后移
                    count--;
                }
                array[i+1] = temp;
            }
            i++;
        }
    }
};