前段时间遇到一个排序的问题，是对一个数组进行排序，数组中存放的是有级别的对象（已经由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;
}
}
