《剑指offer》面试题21：调整数组顺序使奇数位于偶数前面（Java实现）

题目

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

解题思路

1. 新建了两个数组，一个放奇数，一个放偶数

public class Solution {
    public void reOrderArray(int [] array) {
        int len = array.length;
        if(array==null || len==0){
            return;
        }
        int[] odd = new int[len];
        int[] even = new int[len];
        int len1=0;
        int len2=0;
        for(int i=0; i< len; i++){
            if((array[i]%2) == 0){
                len2++;
                even[len2-1] = array[i];
            }else{
                len1++;
                odd[len1-1] = array[i];
            }
        }
        for(int i=0; i<len1; i++){
            array[i] = odd[i];
        }
        for(int i=0; i<len2; i++){
            array[i+len1] = even[i];
        }
}}

2. 时间复杂度$O(n^2)$的方法：即从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾就有一个空位，这时把该偶数放入这个空位，但是要在此位置（刚刚被移走偶数所在的位置）重新判断一次。由于每次碰到一个偶数就需要移动O（n）个数字，因此这个算法的时间复杂度为O（n^2）。

public class Solution {
    public void reOrderArray(int [] array) {
        int len = array.length;
        if(array==null || len==0){
            return;
        }
        int temp;
        int count=0;//控制数组遍历的循环次数
        for(int i = 0; i<len && count<len; i++){
            count++;
            if((array[i]%2) == 0){
                temp = array[i];
                for(int j=i; j<len-1; j++){
                    array[j] = array[j+1];
                }
                array[len-1] = temp;
                i--;
            }
        }

}
}

3. 类似冒泡排序，两个相邻的整数如果前偶后奇就交换

public class Solution {
    public void reOrderArray(int [] array) {
        int len = array.length;
        if(array==null || len==0){
            return;
        }
        for(int i=0;i<len;i++){          
           for(int j=0;j<len-1;j++){
               if(array[j]%2==0&&array[j+1]%2==1){//前偶后奇
                   int temp=array[j+1];
                   array[j+1]=array[j];
                   array[j]=temp;
               }
           }
       }
}
}

4. 这个题目要求把奇数放在数组的前半部分，偶数放在数组的后半部分，因此所有的奇数应该位于偶数的前面，也就是说我们在扫描这个数组的时候，如果发现有偶数在奇数的前面，我们可以交换他们的数序，交换之后就符合要求了。
   两个指针：第一个指针初始化时指向数组的第一个数字，它只向后移动；第二个指针初始化只向数组的最后一个数字，它只向前移动。如果第一个数字指向的数字是偶数，且第二个指针指向的数字是奇数，则交换这两个数字。