问题描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

解决思路

思路一

最简单的思路应该是遍历这个数组，当遇到一个偶数时就把这个数后边所有的数都往前移动一位，然后再把这个偶数插入到数组最后。当遍历完这个数组时，这个数组就是一个奇数在前偶数在后的数组了。但是这种方式在每遇到一个偶数时都需要移动数据，在加上遍历整个数组，就使得这个算法的时间复杂度变为O(n^2)了。

思路二

我们可以利用快速排序的思想去解决这个问题。

假设有两个指针p1、p2，其中p1指向数组中第一个元素，p2指向数组中最后一个元素。首先将p1向后移动直到找到一个偶数，然后将p2向前移动直到找到一个奇数，交换p1、p2所指向的元素。然后重复上述过程，直到p1、p2相遇时(p1指向元素位置在p2指向位置之后)，这个数组就是一个奇数在前偶数在后的数组了。

示例

下面以数组[1, 2, 6, 3, 4, 7, 5]为例演示下思路二的过程：

初始时，p1指向元素1，p2指向元素5。

第一步：向后移动p1，直到找到一个偶数2；向前移动p2，直到找到一个奇数5，交换2和5，此时数组为[1, 5, 6, 3, 4, 7, 2]。
第二步：向后移动p1，直到找到一个偶数6；向前移动p2，直到找到一个奇数7，交换6和7，此时数组为[1, 5, 7, 3, 4, 6, 2]。
第三步：向后移动p1，直到找到一个偶数4；向前移动p2，直到找到一个奇数3，此时p1指向位置在p2指向位置之后，结束。

经过不断的交换奇数和偶数，最后可得到的数组[1, 5, 7, 3, 4, 6, 2]符合题目要求。

代码

public void reOrder(int [] array) {
    int start = 0;
    int end = array.length-1;
    
    while(start < end) {
    	//找到一个偶数
    	while((array[start] & 1) != 0) {
    		start++;
    	}
    	
    	//找到一个奇数
    	while((array[end] & 1) ==0) {
    		end--;
    	}
    	
    	//交换奇偶数
    	if(start < end) {
    		int temp = array[start];
    		array[start] = array[end];
    		array[end] = temp;
    	}
    }
}

一个整数和1进行与操作，如果结果为0，则这个整数为偶数

问题扩展

现在我们改下题目，把题目变为：使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，且保证奇数和奇数，偶数和偶数之间的相对位置不变。

解决思路

可以利用插入排序的思想，将数组分为两个部分：已查找序列和未查找序列，其中已查找序列中为奇数且奇数间的先后位置与原来保持一致。具体过程为：每次从待查找序列中找到第一个奇数，然后把数组中待排序序列中查找到的奇数之前的元素依次向后移动一位，再把这个奇数插入到已查找序列的最后（待排序序列的开头），重复这个过程，直到从待查找序列中找不到奇数。

过程示例

还是以数组[1, 2, 6, 3, 4, 7, 5]为例：

初始化时，已排序序列为[]、待排序序列为[1, 2, 6, 3, 4, 7, 5]。

第一步：从待排序序列中找到第一个奇数1，插入到已排序序列中，此时数组为[1, 2, 6, 3, 4, 7, 5]。
第二步：从待排序序列中找到第一个奇数3，把待排序序列中3之前的元素即[2, 6]依次向后移动一位，把3插入到已排序序列的最后（待排序序列的开头），此时数组为[1, 3, 2, 6, 4, 7, 5]。、
第三步：从待排序序列中找到第一个奇数7，把待排序序列中7之前的元素即[2, 6, 4]依次向后移动一位，把7插入到已排序序列的最后，此时数组为[1, 3, 7, 2, 6, 4, 5]。
第四步：从待排序序列中找到第一个奇数5，把待排序序列中5之前的元素即[2, 6, 4]依次向后移动一位，把5插入到已排序序列的最后，此时数组为[1, 3, 7, 5, 2, 6, 4]。

此时，从待查找序列中查不到奇数了，数组中元素位置以调整完成。

代码

public void reOrderArray(int[] array) {
	for(int i=0; i<array.length; i++) {
		int index = i;
		//找到一个奇数
		while(index<array.length && (array[index] & 1) ==0) {
			index++;
		}
		
		//找到最后没有找到奇数，说明剩下的全是偶数，数组已调整完成
		if(index >= array.length) {
			break;
		}
		
		int odd = array[index];
		//将奇数之前的、i之后的元素向后移动一位
		for(int start=index; start>i; start--) {
			array[start] = array[start-1];
		}
		array[i] = odd;
	}
}