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

2013-03-27

一道算法题：分离数列中的奇偶项引用问题描述：用最少的时间复杂度实现数组的奇偶分离，奇数排在数组前部，偶

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

引用

问题描述：
用最少的时间复杂度实现数组的奇偶分离，奇数排在数组前部，偶数排在数组后部
例：
原数列：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--;
}
}
}
}

算法优化?java?
[解决办法]
写了个期望时间为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);
} 
 
}

[解决办法]

引用:

用移位运算来解决。
原理就是把数以2进制读入，只需要判断最后一位是0还是1就可以了。

我觉得此方法很好！
[解决办法]
修改一下，不要每次判断，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];
  }
}

热点排行

J2SE开发

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