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

题目描述

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

题解

思路1

开一个辅助数组，简单实用

遍历3次

1 -- 将奇数放入辅助数组

2 -- 将偶数放入辅助数组

3 -- 辅助数组的值覆盖原数组

时间复杂度: O(n)- 空间复杂度: O(N)

public void reOrderArray(int[] array) {
    int[] cp = new int[array.length];
    int idx = 0;
    /*先存储奇数*/
    for (int i = 0; i < array.length; i++) {
        if (array[i] % 2 != 0)
            cp[idx++] = array[i];
    }
    /*再存储偶数*/
    for (int i = 0; i < array.length; i++) {
        if (array[i] % 2 == 0)
            cp[idx++] = array[i];
    }

    /*赋回给原数组*/
    for (int i = 0; i < array.length; i++) {
            array[i] = cp[i];
    }
}

思路2

类似于插入排序

找偶数，找到后，该元素后续全部向前位置1位，将该偶数插入到数组最后

为了保证偶数和偶数之间的顺序不变，用一个指针P 指向最开始的那个偶数，遍历到指针P处，说明数组已全部调整好

时间复杂度: O(N^2)- 空间复杂度: O(1)

public static void reOrderArray(int[] array) {
    int p = array.length;
    for (int i = 0; i < array.length; ) {
        if (p == i)
            break;
        if (array[i] % 2 == 0) {
            int tmp = array[i];
            for (int j = i; j < array.length - 1; j++) {
                array[j] = array[j + 1];
            }
            array[array.length - 1] = tmp;
            p--;
        } else {
            i++;
        }
    }
}