剑指offer - 调整数组顺序使奇数位于偶数前面(Java实现)

题目链接：https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=13&&tqId=11166&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：开两个辅助数组，把奇数和偶数分别存储在数组中，然后将奇数放在前面，偶数放在后面即可。

public class Solution {
    public void reOrderArray(int [] array) {
        int n = array.length;
        int[] even = new int[n];
        int[] odd = new int[n];
        int cnt1 = 0, cnt2 = 0;
        for(int i = 0; i < n; ++ i) {
            if(array[i] % 2 == 0) even[cnt1 ++] = array[i];
            else odd[cnt2 ++] = array[i];
        }
        for(int i = 0; i < cnt2; ++ i) {
            array[i] = odd[i];
        }
        for(int i = 0; i < cnt1; ++ i) {
            array[i + cnt2] = even[i];
        }
    }
}

  思路一：设置两个指针 i 和 j，如下图。首先我们找到第一个奇数，如果我们需要将其放入到 i 位置，首先我们需要将 [i, j - 1] 位置上面的值全部后移一位，然后在向 i 中插入第一个奇数，i 指针后移去找后面一个奇数，然后 j 指针后移继续遍历数组，如果找到奇数就按照上述操作继续进行，直到整个数组遍历结束即可。

public class Solution {
    public void reOrderArray(int [] array) {
        int n = array.length;
        int i = 0;
        for(int j = 0; j < n; ++ j) {
            if(array[j] % 2 == 1) {
                int value = array[j];
                for(int k = j - 1; k >= i; -- k) {
                    array[k + 1] = array[k];
                }
                array[i ++] = value;
            }
        }
    }
}