题解 | #调整数组顺序使奇数位于偶数前面#

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

拿到题目我首先想到可以类比C++在头尾处放两个指针，左指针指向奇数指针右移，右指针指向偶数指针左移，否则指针不动，等到左指针指向偶数且右指针指向奇数，这时直接调换左右顺序即可。这样时间复杂度O(n)，空间复杂度O(1)。但是题目要求奇数偶数相对位置不能改变，这个方法就无效了。

方法1 临时数组法
接下来切换思路，我的想法是扫描两边数组，分别将奇数和偶数存放在两个临时数组中，这样其相对位置不会发生改变，在扫描存放奇数的数组，一旦发现空位就将偶数数组复制进去，这样能保证时间复杂度仍为O(n),而空间复杂度也为O(n)。
时间复杂度O(n)
空间复杂度O(n)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here
        int[] temp1 = new int[array.length];
        int[] temp2 = new int[array.length];
        int i=0; int j=0; int k=0; int m=0; int n=0;
        while(i<array.length){
            if(array[i]%2 == 1){
                temp1[j] = array[i];
                j++;
            }
            if(array[i]%2 == 0){
                temp2[k] = array[i];
                k++;
            }
            i++;
        }
        for(m=0; m<array.length&&temp1[m]%2==1; m++);
        for(n=m; n<array.length; n++){
            temp1[n] = temp2[n-m];
        }
        return temp1;
    }
}

方法2 冒泡排序
后来我又想到可以利用冒泡排序的思想，找到奇数就放到前面，最后结果也是一样的。这里就不付代码了。
时间复杂度O(n^2)
空间复杂度O(1)