剑指Offer——奇数都在偶数前 Java

题目描述

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

解题思路

1. 课本解题思路

   基本思想：扫描数组，如果发现偶数出现在奇数前面 就交换他们。

   细化操作：扫描采用两个指针，一个从左向右的i 有个从右向左j，i指针只判断是否为偶数，j指针判断是否为奇数

   当i指向偶数，j指向奇数 就交换他们（卧槽，看见没 这跟一次快排的原理一毛一样）

   类似的还有：所有负数都在非负前面、所有能被3整除的都在不能被3整除的数前面....

2. 牛客网解题思路（要求相对位置）

   1. o（n^2） 冒泡思想
   2. o（n）以及o（n）空间，再见一个数组 来保存一次遍历筛选结果

题解

书中题目（未要求奇数之间相对位置 和 偶数之间相对位置不变）

public void reOrderArray(int [] array) {
    int n = array.length;
    if (n <= 0 || array == null) return;
    int i = 0;
    int j = n-1;
    while (true){
        while ((array[i] & 0x1) != 0 && i<j) i++;
        while((array[j]&0x1)==0 && i<j) j--;
        if (i >= j) break;
        swap(array,i,j);
    }
}

public void swap(int array[],int i,int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

牛客网（也是本题 题目描述 要求 奇数 偶数 之间的相对位置不变）

    public void reOrderArray(int array[]){
        int n = array.length;
        if (n <= 0 || array == null) return;

        for (int i = 0; i < n-1; i++) {
            boolean isExch = false;
            for (int j = 0; j < n-1; j++) {
                if((array[j]&0x1) == 0 && (array[j+1]&0x1) != 0){
                    swap(array,j,j+1);
                    isExch = true;
                }
            }
            if (!isExch){
                break;
            }
        }
    }