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

Question

以下是我想到的，大家有更好的算法么？多谢指教~
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--;
}
}
}
}
算法优化 java 

Answer 1

写了个期望时间为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() {
return rightCh;
}
public void setRightCh(Node rightCh) {
this.rightCh = rightCh;
}

public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public Node(int data, Node leftCh, Node rightCh) {
super();
this.data = data;
this.leftCh = leftCh;
this.rightCh = rightCh;
this.setCount(1);
}
public Node(int data) {
super();
this.data = data;
this.setCount(1);
}
public Node() {
super();
this.setCount(1);
}
@Override
public String toString() {
return "Node [data=" + data + "]";
}

}public class JiAndOu {

/**
 * 根节点
 */
private Node root;public Node getRoot() {
return root;
}public void setRoot(Node root) {
this.root = root;
}/**
 * 主要算法：
 * 1、构建根节点、根节点的左子树、根节点的右子树
 * 2、遍历数组，并调用BST的插入算法
 * i如果是奇数,插入左子树;否则插入右子树
 * 3、插入完成之后，设置全局变量index，分别递归遍历根节点的左、右子树，把关键字放入数组
 * 4、输出数组
 */
public void arrayToTree(int[] array){
root=new Node();
for(int i:array){
if(i%2!=0){
this.insertOneNode(i,root.getLeftCh());
}else{
this.insertOneNode(i, root.getRightCh());
}
}
this.midOrder(array, root.getLeftCh());
this.midOrder(array, root.getRightCh());
System.out.println("排序之后:");
for(int i:array){
System.out.print(i+",");
}
}/**
 * 全局变量index,用于把关键字放入目标数组
 */
private int index;public int getIndex() {
return index;
}public void setIndex(int index) {
this.index = index;
}/**
 * 中序遍历递归算法
 */
public void midOrder(int[] array,Node p){
if(p!=null){
//递归左子树
this.midOrder(array, p.getLeftCh());
for(int i=1;i<=p.getCount();i++){
//依次把关键字放入数组
array[index]=p.getData();
index++;
}
//递归右子树
this.midOrder(array, p.getRightCh());
}

}/**
 *在BST中插入一个节点
 *和《严蔚敏数据结构》的例题基本一致，就是多了个功能：当关键字相同时，相应节点的count++
 */
public void insertOneNode(int i,Node p){
if(p==null){
p=new Node(i);
if(i%2!=0){
root.setLeftCh(p);
}else{
root.setRightCh(p);
}
}else{
Node point=p;
while(true){
if(i<point.getData()){
if(point.getLeftCh()==null){
Node yezi=new Node(i);
point.setLeftCh(yezi);
break;
}else{
point=point.getLeftCh();
continue;
}
}else if(i>point.getData()){
if(point.getRightCh()==null){
Node yezi=new Node(i);
point.setRightCh(yezi);
break;
}else{
point=point.getRightCh();
continue;
}
}else{
int count=point.getCount();
count++;
point.setCount(count);
break;
}
}

}
}
@Test
public void test(){
int[] array={10,11,8,7,2,5,0,9,4,11,8,5,2,7,0,19,14,16};
this.arrayToTree(array);
}
}

Answer 2

此哥们的算法理论很扎实嘛，顶一个！我也小实现一下，就不搞那么复杂的：public static void main(String[] args) {
    int[] arrSrc = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12};
    int[] arrOdd = new int[arrSrc.length];
    int[] arrEven = new int[arrSrc.length];
    int oddIndex = 0;
    int evenIndex = 0;
    for (int iSrc : arrSrc) {
        if ((iSrc & 1) == 0) {    // even
            arrEven[evenIndex++] = iSrc;
        }
        else {                    // odd
            arrOdd[oddIndex++] = iSrc; 
        }
    }
    System.arraycopy(arrEven, 0, arrOdd, oddIndex, evenIndex);
    System.out.println(Arrays.toString(arrOdd));
}

Answer 3

楼主的程序会出现bug，当运行到i=k,j=k+1时，如果arr[i]为奇数，arr[j]为偶数时，将执行第一个if，接着就会出现arr[j]为奇数，arr[i]为偶数的情况，于是就马上要执行第二个if，此时i>j,就会出现将后面的偶数和前面的奇数交换的情况

Answer 4

可以用排序算法的思想，从左向右找到第一个偶数位于i，从右向左批一个奇数位于j，交换它们。然后i++, j--，直到i >= j，则结束。如果结果需要排序，再用快速排序。

Answer 5

修改一下，不要每次判断，isOdd
public class SortByOddEven {  public static void main(String[] args) {
    int[] array = new int[20];
    Random rand = new Random();
    for (int i = 0; i < array.length; i++) {
      array[i] = rand.nextInt(100);
    }
    System.out.println(Arrays.toString(array));
    sort(array);
    System.out.println(Arrays.toString(array));
  }  public static void sort(int[] array) {
    int head = 0;
    int tail = array.length - 1;
    boolean headIsEven = false;
    while (head < tail) {
      if (headIsEven) {
        if (isOdd(array[tail])) {
          swap(array, head, tail);
          head++;
          headIsEven = false;
        }
        tail--;
      } else {
        if (isEven(array[head])) {
          headIsEven = true;
        } else {
          head++;
        }
      }
    }
  }  private static boolean isEven(int n) {
    return (n & 1) == 0;
  }  private static boolean isOdd(int n) {
    return (n & 1) != 0;
  }  private static void swap(int[] array, int index1, int index2) {
    array[index1] ^= array[index2];
    array[index2] ^= array[index1];
    array[index1] ^= array[index2];
  }
}