剑指offer（十三）调整数组顺序使奇数位于偶数前面

点击进入 牛客网题库：调整数组顺序使奇数位于偶数前面

题目描述

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

上来我就撸了一个，借助List来进行的，不过这个肯定不是面试官想要的

方法一：

  /**
     * 算法 时间复杂度O(n) 空间复杂度 O(n) 
     * @param array
     */
 public void reOrderArray(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        final ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 != 0) {
                list.add(array[i]);
            }
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 0) {
                list.add(array[i]);
            }
        }

        for (int i = 0; i < array.length; i++) {
            array[i] = list.get(i);
        }
    }

方法二：

j 遇到奇数就进行交换，然后把所有的偶数往后调整，然后，再把奇数赋值到原来的偶数上

一个比较糟糕的图解（第一次画图，比较瑕疵，凑合着看把[😂]）

剑指offer topic13图解.png

代码：

  /**
     * 算法 时间复杂度O(n^2) 空间复杂度 O(1)
     *
     * @param array
     */
    public void reOrderArray(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        int m = 0;
        for (int i = 0; i < array.length; i++) {
            //判断奇数类型 符合条件
            if (array[i] % 2 != 0) {
                //把这个奇数保存起来
                int tmp = array[i];
                int j = i;
                while (j > m) {
                    //一顿交换，把偶数往前走一步
                    array[j] = array[j - 1];
                    j--;
                }
                //奇数占用原来偶数的位置，偶数的位置向前移动了一步
                array[j] = tmp;
                //m指向偶数位置，等待下次的交换
                m = j + 1;
            }

        }
    }