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

问题描述

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

思路分析

首先想到的思路是从头开始遍历这个数组，如果遇到偶数就把这个数之后的所有数往前移动一位，这样数组就会流出一个空位，移动完毕后就把该偶数放到该空位，但是由于一次是遍历，一次是移位，所以导致时间复杂度为O（n*2)

码上有戏

public int[] reOrderArray2(int[] array){
		if(array==null||array.length==0)
			return null;
		int i,j;
		for(i=1;i<array.length;i++){
			int temp=array[i];
		if(!isEven(array[i])){
			for(j=i-1;j>=0&&isEven(array[j]);j--)
			{
				array[j+1]=array[j];
			}
			array[j+1]=temp;
		}
		}
		return array;
	}
	
	public boolean isEven(int i){
		if((i&0x1)==0)
			return true;
		return false;
	}

测试：

Fib fib=new Fib();
int[] arr=fib.reOrderArray2(new int[]{3,5,6,7,8,9});
for(int i=0;i<arr.length;i++)
System.out.println(arr[i]);

另一种思路

如果说不改变相对位置的话，就可以用两个指针操作，第一个指针指向偶数，第二个指针指向奇数，并且让第一个指针在第二个指针前面，就交换两个元素。当第一个指针在第二个指针后面就说明所有的奇数都移动到所有偶数前面了

public void reOrderArr(int[] array){
		if(array==null||array.length==0)
			return;
		int evenIndex=0;
		int oddIndex=array.length-1;
		while(evenIndex<oddIndex)
		{
			while(evenIndex<oddIndex&&(array[evenIndex]&0x1)!=0)
				evenIndex++;
			while(evenIndex<oddIndex&&(array[oddIndex]&0x1)==0)
				oddIndex--;
			if(evenIndex<oddIndex)
				swap(array,evenIndex,oddIndex);
		}
	}