一道算法题：分离数列中的奇偶项

引用

问题描述：
用最少的时间复杂度实现数组的奇偶分离，奇数排在数组前部，偶数排在数组后部
例：
原数列：1 2 3 4 5 6 7 8 9 10 12
分离后：1 3 5 7 9 2 4 6 8 10 12

以下是我想到的，大家有更好的算法么？多谢指教~

public class SeparateOddEven

{

	public static void main(String[] args)

	{

		int[] arr = {0, 1, 2, 3, 4, 5 ,6 ,7 ,8 ,8 ,9 ,10, 12, 15 ,17};

		display(arr);

		Separate(arr);

		display(arr);

	}

	//输出数组

	public static void display(int[] arr)

	{

		for(int i = 0; i < arr.length; i++)

		{

			System.out.print("[" + arr[i] + "]");

		}

		System.out.println();

	}

	//交换数组中两个元素的位置

	private static void swap(int[] arr, int a, int b)

	{

		int temp;

		temp = arr[a];

		arr[a] = arr[b];

		arr[b] = temp;

	}

	//判断给定数组元素是否为奇数

	private static boolean isOdd(int[] arr, int pos)

	{

		if(arr[pos] % 2 == 1)

		{

			return true;

		}

		else

		{

			return false;

		}

	}

	//将数组中的奇偶数分离

	public static void Separate(int[] arr)

	{

		int i, j;

		i = 0;

		j = arr.length - 1;

		while(i < j)

		{

			if(isOdd(arr, i) == true && isOdd(arr, j) == false)//前奇后偶情况

			{

				i++;

				j--;

			}

			if(isOdd(arr, i) == false && isOdd(arr, j) == true)//前偶后奇情况（需交换两个元素的位置）

			{

				swap(arr, i, j);

				i++;

				j--;

			}

			if(isOdd(arr, i) == true && isOdd(arr, j) == true)//前奇后奇情况

			{

				i++;

			}

			if(isOdd(arr, i) == false && isOdd(arr, j) == false)//前偶后偶情况

			{

				j--;

			}

		}

	}

}

------解决方案--------------------
写了个期望时间为Nlog2N、空间复杂度为N的算法，可能不是最快的，但能肯定下面两点
1、对于乱序数组，如：{10,11,8,2,7,5,0,9,4},可以一次性做到分离奇偶、并且有序。
2、对于含有重复数字、含有大量随机数字的数组，此算法的性能就能体现出来。
中心思想是：BST的插入

import org.junit.Test;



/**

 * 二叉排序树的节点类

 *

 */

class Node{

	

	/**

	 * 关键字

	 */

	private int data;

	

	/**

	 * 左孩子

	 */

	private Node leftCh;

	

	/**

	 * 右孩子

	 */

	private Node rightCh;

	

	/**

	 * 相同关键字出现的次数

	 */

	private int count;

	public int getData() {

		return data;

	}

	public void setData(int data) {

		this.data = data;

	}

	public Node getLeftCh() {

		return leftCh;

	}

	public void setLeftCh(Node leftCh) {

		this.leftCh = leftCh;

	}

	public Node getRightCh() {