题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
这段通过编译的代码，我并不是特别满意，实现的并不是特别的漂亮。时间复杂度为O(n)，空间复杂度为O(n)遍历了三遍。因为我觉得通过插入排序的方式时间复杂度会拓展到O(n2)，只有在限制空间复杂度的情况下可以尝试使用。
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中没有所谓的传指针，我无法将新建的数组付给入参，只能复制一遍。着重看一下有没有不需要复制的方法可以直接指向新的数组
