Graceful Java Programming 之使用Collection排序

一.TreeSet 、 TreeMap
时间复杂度： log(n)
方法一： 对存入TreeSet的对象和put到TreeMap的key实现java.util.Comparable接口
代码样例：

 
public class TokenDelegate implements Comparable{
//词元的起始位移
private int offset;
    //词元的起始位置
    private int begin;
    //词元的终止位置
    private int end;
   ......
   ......
    
    /*
     * 词元在排序集合中的比较算法
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     */
    public int compareTo(Object o){
        TokenDelegate ntd = (TokenDelegate)o;
        if(this.begin < ntd.begin){
            return -1;
        }else if (this.begin == ntd.begin){
            //当起始位置相同时,长词优先
            if( this.end > ntd.end ){
                return -1;
            }else if(this.end == ntd.end){
                return 0;
            }else if(this.end < ntd.end){
                return 1;
            }
        }
        return 1;
    }
    ......
    ......
}

方法二：为对象实现java.util.Comparator，并通过构造函数传给TreeSet或TreeMap
代码样例：

 
class BusLineNameComparator implements Comparator{ 
        ...... 
        ...... 
        /**
         * 公交线路查询结果排序器
         * @param one
         * @param other
         * @return
         */
        public int compare(Object one , Object other){
            if(one == other){
                return 0;
            }
            if(one instanceof LBSBusLine && other instanceof LBSBusLine){
                LBSBusLine busLineA = (LBSBusLine)one;
                LBSBusLine busLineB = (LBSBusLine)other;
                String busNameA = busLineA.getName();
                String busNameB = busLineB.getName();
                //判断是否同一条线路
                if(busLineA.equals(busLineB)){
                    return 0;
                }
                //判断公交线路名称长度
                if(busNameA.length() < busNameB.length()){
                    return -1;
                }else if(busNameA.length() > busNameB.length()){
                    return 1;
                }else{
                    return busNameA.compareTo(busNameB);
                }
            }else{
                throw new java.lang.ClassCastException("Not LBSBusLine Type.");
            }
         }
      }
     ......
     ...... 
}

这里要提醒大家注意的是对于TreeSet中的对象和TreeMap的key，判断对象是否相等不是根据对象的equals方法实现的，而是根据对象的compareTo()实现或者比较器Comparator中的compare方法是否返回0来鉴别的，这一点在实现比较器的排序和集合的contain判别中尤为重要。


二.使用java.util.Collections.sort对List排序,其时间复杂度为n*log(n)。

使用java.util.Collections.sort方法同样可以通过对象自身实现Comparable接口，或者为sort方法给定Comparator实现来完成排序.这里不做复述。同TreeSet不同的是，用java.util.Collections.sort对List进行排序允许List中两个元素的compareTo()或compare()方法返回0，既允许概念上两个重复元素的共存于List中。这也符合了数学概念上Set和List的区别。

评论

2 楼 linliangyi2007 2008-03-29  

楼上是英文大牛，很需要想您这样的人出来，为加强中国程序界同国外同行的沟通添砖加瓦，尤其是在开源社区中！！

1 楼 vinhsu 2008-03-28  

引用

这里要提醒大家注意的是对于TreeSet中的对象和TreeMap的key，判断对象是否相等不是根据对象的equals方法实现的，而是根据对象的 compareTo()实现或者比较器Comparator中的compare方法是否返回0来鉴别的，这一点在实现比较器的排序和集合的contain 判别中尤为重要。

I want to add one comment from JDK:

The ordering imposed by a Comparator c on a set of elements S is said to be consistent with equals if and only if (compare((Object)e1, (Object)e2)==0) has the same boolean value as e1.equals((Object)e2) for every e1 and e2 in S.

JSK recommend developer takes care for equals to be consistent even thought collections.sort doesn't use.