调整数组顺序使奇数位于偶数前面 - 牛客剑指offer 12

题目描述

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

第一种思路：

每次暴力寻找，然后暴力区间往后挪一位；

public class Solution {
    public void reOrderArray(int [] array) {
        int len=array.length;
        if(len==0)
            return;
        int t;
        boolean finsh=false;
        for(int i=0;i<len;i++){
            finsh=false;
            if(array[i]%2==0){
                for(int j=i+1;j<len;j++){
                    if(array[j]%2==1){
                        finsh=true;
                        t=array[j];
                        for(int j1=j;j1>i;j1--){
                            array[j1]=array[j1-1];
                        }
                        array[i]=t;
                        break;
                    }
                }
                if(!finsh)
                    break;
            }
        }
    }
}

第二种思路：

用两个队列，一个存储奇数，一个存储偶数；然后塞回去数组；

由于给出的代码是没有引入的，所以用两个数组处理；

public class Solution {
    public void reOrderArray(int [] array) {
        int len=array.length;
        if(len==0)
            return;
       int [] odd=new int [len];
       int [] even=new int [len];
       int oddNum=0;
       int evenNum=0;
       for(int i=0;i<len;i++){
           if(array[i]%2==1)
               odd[oddNum++]=array[i];
           else
               even[evenNum++]=array[i];
       }
       int t=0;
       int i=0;
       while(i<oddNum)
           array[t++]=odd[i++];
       int j=0;
        while(j<evenNum)
            array[t++]=even[j++];
    }
}