利用树型结构进行排序

王朝java/jsp·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

前段时间遇到一个排序的问题,是对一个数组进行排序,数组中存放的是有级别的对象(已经由Oracle的Connect 进行分级),但是每级内的对象顺序是乱的,下面这个类完成了排序功能

package dsn;

import java.util.*;

import log.*;

import model.*;

public class RequireSorter2

{

Log4jWrapper log = WebLog.getInstance();

private static RequireSorter2 instance = new RequireSorter2();

private RequireSorter2()

{

}

public static RequireSorter2 getInstance()

{

return instance;

}

public ProductRequire[] sort( ProductRequire[] sourceRequire )

{

log.debug("Begin sort");

long start = System.currentTimeMillis();

if(null==sourceRequire || sourceRequire.length ==0 )

{

return sourceRequire;

}

/*构造有序树*/

SorterTreeNode root = new SorterTreeNode( null );

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

{

if(null==sourceRequire[ i ])

{

continue;

}

SorterTreeNode treeNode = new SorterTreeNode( sourceRequire[ i ] );

root.add(treeNode);

}

/*将树转为数组*/

sourceRequire = treeToArray(root);

long end = System.currentTimeMillis();

log.debug("Sort count:"+sourceRequire.length);

log.debug("Sort time:"+(end-start));

return sourceRequire;

}

/**

* 使用深度优先遍历树,返回数组

* @param treeNode TreeNode

* @return ProductRequire[]

*/

private ProductRequire[] treeToArray(SorterTreeNode treeNode)

{

/*存储从树中取出的节点*/

ArrayList list = new ArrayList();

Stack stack = new Stack();

stack.push(treeNode);

SorterTreeNode parent = null;

SorterTreeNode child = null;

while(!stack.isEmpty())

{

parent = (SorterTreeNode)stack.pop();

/*根节点是null*/

if(null!=parent.getProductRequire())

{

list.add( parent.getProductRequire() );

}

ArrayList children = parent.getChildren();

for(int i=children.size()-1;i>=0;i--)

{

stack.push(children.get(i));

}

}

ProductRequire[] productRequire = (ProductRequire[])list.toArray(new ProductRequire[list.size()]);

return productRequire;

}

}

class SorterTreeNode

{

/*人造节点*/

public static final String OTHER_LEVEL_REQUIREMENT_NO = " ";

/*父节点*/

private SorterTreeNode parent = null;

/*本节点存储的对象*/

private ProductRequire productRequire = null;

/*子节点*/

private ArrayList children = new ArrayList();

private int lastChildIndex = -1;

/**

* 私有

*/

private SorterTreeNode(ProductRequire[] sourceRequire)

{

}

/**

* 构造函数

*/

public SorterTreeNode(ProductRequire productRequire)

{

this.productRequire = productRequire;

}

public SorterTreeNode getParent()

{

return parent;

}

public void setParent(SorterTreeNode parent)

{

this.parent = parent;

}

public ArrayList getChildren()

{

return children;

}

public ProductRequire getProductRequire()

{

return productRequire;

}

/**

* 添加节点

*/

public void add(SorterTreeNode treeNode)

{

if(lastChildIndex<0

|| ((SorterTreeNode)children.get(lastChildIndex)).getProductRequire().getLevelId()==treeNode.getProductRequire().getLevelId())

{

insertChild(treeNode);

}

else

{

((SorterTreeNode)children.get(lastChildIndex)).add(treeNode);

}

}

/**

* 按序插入子节点

* @param productRequire ProductRequire

*/

private void insertChild(SorterTreeNode child)

{

child.setParent(this);

ProductRequire productRequire = child.getProductRequire();

ProductRequire tmp = null;

for(int i=0;i<children.size();i++)

{

tmp = ((SorterTreeNode)children.get(i)).getProductRequire();

if(compare(tmp.getRequirementNo(),productRequire.getRequirementNo())>0)

{

lastChildIndex = i;

children.add(i,child);

return;

}

}

children.add(child);

lastChildIndex = children.size()-1;

}

public int compare( Object o1, Object o2 )

{

int result = ( ( String )o1 ).compareTo( o2 );

if ( result > 0 && OTHER_LEVEL_REQUIREMENT_NO.equals( o2 ) )

{

result = 0;

}

return result;

}

public boolean equals( Object o1 )

{

return true;

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航