一路算法题：分离数列中的奇偶项
日期：2014-05-20 浏览次数：20713 次
一道算法题：分离数列中的奇偶项
以下是我想到的，大家有更好的算法么？多谢指教~
------解决方案--------------------
写了个期望时间为Nlog2N、空间复杂度为N的算法，可能不是最快的，但能肯定下面两点
1、对于乱序数组，如：{10,11,8,2,7,5,0,9,4},可以一次性做到分离奇偶、并且有序。
2、对于含有重复数字、含有大量随机数字的数组，此算法的性能就能体现出来。
中心思想是：BST的插入
以下是我想到的，大家有更好的算法么？多谢指教~
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() {
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
