调整数组顺序 奇前偶后 剑指OFFER

题目描述

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

这段通过编译的代码，我并不是特别满意，实现的并不是特别的漂亮。时间复杂度为O(n)，空间复杂度为O(n)遍历了三遍。因为我觉得通过插入排序的方式时间复杂度会拓展到O(n²)，只有在限制空间复杂度的情况下可以尝试使用。

    public void reOrderArray(int[] array)
    {
        int[] newArray = new int[array.length];
        int cur = 0;//新数组游标
        for (int i = 0; i<array.length;i++)
        {
            if((array[i] & 0x01) == 1)
            {
                newArray[cur] = array[i];
                cur++;
            }
        }
        for (int i = 0; i<array.length;i++)
        {
            if((array[i] & 0x01) == 0)
            {
                newArray[cur] = array[i];
                cur++;
            }
        }
        for (int i = 0;i<array.length;i++)
        {
            array[i] = newArray[i];
        }
    }

错误解法

调整顺序使奇数在前偶数在后,且相对位置不变
思路 1.找下一个偶数位置
​ 2.找偶数后的第一个奇数，交换 回到步骤1.重复
这种思路是错误的，例1 2 3 4 5 6
偶数不能保证按序，因为从 1 3 2 4 5 6 到 1 3 5 4 2 6 偶数顺序不能保证

可以利用插入排序的思想对这个解法进行改进，即插入奇数的时候，奇数与偶数中间部分的数值进行后移，但这会增加时间复杂度。

    public void reOrderArray(int [] array) {
        for (int i = 0; i<array.length;i++){
            //找下一个偶数
            if ((array[i] & 0x01 )== 0)//问题1. 如不加括号无法通过编译
            {
                //从偶数后找到下一个奇数
                for (int j = i+1; j<array.length; j++)
                {
                    if ((array[j] & 0x01) == 1)
                    {
                        int temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                    }
                }
            }
        }
    }

通过这道题，学到了两个知识

• 一个是关于java对位的操作。之前基于c++的编程过程中，学到了可以通过位操作来判断奇偶和乘二、除二等问题。

int i = 99, j = 0;//源数据
j = i>>2;//右移1位相当于除以2
j = i<<2;//左移1位相当于乘以2（要注意符号的问题，可能会越界、溢出）
j = i&0x01; //最后一位为1，此数为奇数
j = i&0x02; //最后一位为0，此数为偶数

• 二是学会了java中对象数组的声明，java中没有所谓的传指针，我无法将新建的数组付给入参，只能复制一遍。着重看一下有没有不需要复制的方法可以直接指向新的数组