重新排列使数组的奇数在左边，偶数在右边，O(n)

题目：对任意数组，重新排列使数组的奇数在左边，偶数在右边，要求时间复杂度为O(n)。

 

例子： {1,2,3,4,5,6,7,8,9,10} -> {1,3,5,7,9,2,4,6,8,10}

 

思路：类似快速排序的处理，从左边扫描直到找到偶数，再从右边扫描直至找到奇数，再交换。

 

代码：

package algorithm.ms100;

public class Ex83 {
	private int[] a = {1,2,3,4,5,6,7,8,9,10};
	
	public void oddAndEven() {
		int i = 0;
		int j = a.length-1;
		int temp;
		while(true) {
			while(i<a.length && (a[i]%2 == 0)) {
				i++;
			}
			while(j>= 0 && (a[j]%2 == 1)) {
				j--;
			}
			if( i > j ) break;
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
		
		for(i=0; i<a.length; i++) {
			System.out.print(a[i] + "  ");
		}
	}

	public static void main(String[] args) {
		Ex83 ex = new Ex83();
		ex.oddAndEven();

	}

}