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

解法一、

直观的处理逻辑，开辟一个结果数组，第一趟遍历原数组，将原数组中的奇数依次挪到结果数组中；第二趟再遍历一遍原数组，将原数组中的偶数再依次挪到结果数组中。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

import java.util.*;

public class Solution {
    public int[] reOrderArray (int[] a) {
        if (a == null) 
            return null;
        int[] ret = new int[a.length];
        int i = 0;
        for (int j = 0; j < a.length; j++) { // 第一趟，依次移动奇数
            if (a[j] % 2 != 0) {
                ret[i++] = a[j];
            }
        }
       for (int j = 0; j < a.length; j++) { // 第二趟，依次移动偶数
            if (a[j] % 2 == 0) {
                ret[i++] = a[j];
            }
        }
        return ret;
    }
}

解法二、插入排序思想

使用插入排序的思想，就地处理，不用开辟新的空间，但是没找到一个奇数都要向前判断这个奇数应该插入的位置，因此时间复杂度上并不经济，但是可以加深对于插入排序的理解。

特点：

• 就地变动
• 每个奇数一次跟前一个数进行比较，如果前面一个是偶数，就跟他交换，一直交换到队首或前面是奇数。
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

import java.util.*;


public class Solution {
    public int[] reOrderArray (int[] a) {
        if (a == null) 
            return null;
        int j, tmp;
        for (int p = 1; p < a.length; p++) { // 插入排序的思想
            tmp = a[p];
            for (j = p; j > 0 && isOdd(tmp) && isEven(a[j-1]); j--) {
                a[j] = a[j-1];
            }
            a[j] = tmp;
        }
        return a;
    }

    private boolean isOdd(int x) {
        return (x & 0B1) != 0; // 奇数
    }

    private boolean isEven(int x) {
        return (x & 0B1) == 0; // 偶数
    }
}