JAVA学习【9】 集合框架TreeSet类和TreeMap类的排序

        TreeSet类和TreeMap类有序且元素唯一，Integer和String等都有有默认排序方式，即键值依次比较ASCii码值按升序排列。其他类型必须实现Comparable接口，并且重写compareTo()方法。

        有时候需根据Integer或String等JDK已重写过compareTo()的变量来排序，例如降序排列，直接重写覆盖Integer中的compareTo()方法会不太合适，因此可以利用Comparator接口中的compare()方法（即比较器）来实现。因此，博客http://www.cnblogs.com/lixiaolun/archive/2012/12/25/2832775.html认为compareTo()方法是默认排序，compare()方法是定制排序。

        下面看一下两种方法的具体实现。

import java.util.*;
import java.util.Map.Entry;
public class MyCode5 {
public static void main(String args[]) {
TreeMap<Student,Integer> myhm = new TreeMap<Student,Integer>();
myhm.put(new Student("Jack",19),100);
myhm.put(new Student("Rose",20),101);
myhm.put(new Student("Lucy",19),102);
myhm.put(new Student("Lily",18),103);
//遍历输出
Set<Entry<Student, Integer>> set = myhm.entrySet();
for(Map.Entry<Student,Integer> me:set){
System.out.print(me.getValue()+": ");
System.out.println(me.getKey().getName()+" "+me.getKey().getAge());
}
myhm.clear();
}
}

class Student {
private String name;
private int age;
Student(String name, int age){
this.name = name;
this.age  = age;
}
public String getName(){
return name;
}
public int getAge(){
return age;
}
}

程序运行报错：

Exception in thread "main" java.lang.ClassCastException: Student cannot be cast to java.lang.Comparable
at java.util.TreeMap.compare(Unknown Source)
at java.util.TreeMap.put(Unknown Source)
at MyCode5.main(MyCode5.java:6)

TreeMap类在put()元素时，会调用compare()对键值key进行默认升序排列存储，现在Student类未 实现Comparable接口，因此报错。

java.lang 

接口 Comparable<T>

方法 int compareTo(T o)

比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。

import java.util.*;
import java.util.Map.Entry;
public class MyCode5 {
public static void main(String args[]) {
TreeMap<Student,Integer> myhm = new TreeMap<Student,Integer>();
myhm.put(new Student("Jack",19),100);
myhm.put(new Student("Rose",20),101);
myhm.put(new Student("Lucy",19),102);
myhm.put(new Student("Lily",18),103);
//遍历输出
Set<Entry<Student, Integer>> set = myhm.entrySet();
for(Map.Entry<Student,Integer> me:set){
System.out.print(me.getValue()+": ");
System.out.println(me.getKey().getName()+" "+me.getKey().getAge());
}
myhm.clear();
}
}

class Student implements Comparable<Student>{
private String name;
private int age;
Student(String name, int age){
this.name = name;
this.age  = age;
}
public String getName(){
return name;
}
public int getAge(){
return age;
}
@Override
public int compareTo(Student stu) {
if(this.age>stu.getAge()){
return (this.age-stu.getAge());
}else if(this.age<stu.getAge()){
return (this.age-stu.getAge());
}

return (this.name.compareTo(stu.getName()));
}
}

程序运行结果：

103: Lily 18
100: Jack 19
102: Lucy 19
101: Rose 20

先按年龄排序，再按名字排序。

若将“return (this.name.compareTo(stu.getName()));”改写成“return 0”只进行年龄排序，则年龄相同的值将会被覆盖，程序运行结果为：

103: Lily 18
102: Jack 19
101: Rose 20

java.util 
接口 Comparator<T>

方法 int compare(T o1,T o2)和boolean equals(Object obj)

import java.util.*;
import java.util.Map.Entry;

public class MyCode5 {
public static void main(String args[]) {
TreeMap<Student,Integer> myhm = new TreeMap<Student,Integer>(new Student());
myhm.put(new Student("Jack",19),100);
myhm.put(new Student("Rose",20),101);
myhm.put(new Student("Lucy",19),102);
myhm.put(new Student("Lily",18),103);
//遍历输出
Set<Entry<Student, Integer>> set = myhm.entrySet();
for(Map.Entry<Student,Integer> me:set){
System.out.print(me.getValue()+": ");
System.out.println(me.getKey().getName()+" "+me.getKey().getAge());
}
myhm.clear();
}
}

class Student implements Comparator<Student>{
private String name;
private int age;
Student(String name, int age){
this.name = name;
this.age  = age;
}
public Student() {
}
public String getName(){
return name;
}
public int getAge(){
return age;
}
@Override
public int compare(Student stu0, Student stu1) {
if(stu0.getAge()>stu1.getAge()){
return stu0.getAge()-stu1.getAge();
}else if(stu0.getAge()<stu1.getAge()){
return stu0.getAge()-stu1.getAge();
}
return (stu0.getName().compareTo(stu1.getName()));
}

}

程序运行结果：

103: Lily 18
100: Jack 19
102: Lucy 19
101: Rose 20

        

        此外，若键值相同，TreeSet类和TreeMap类存放元素时就会覆盖以前的值，对于含有重复值序列的排序，TreeSet类和TreeMap类会不太合适。对于有重复元素的，一般使用LinkedList和ArrayList，而这两者并没有默认排序。例如对含有重复单词的单词表排序问题，无论是LinkedList和ArrayList，还是TreeSet和TreeMap都不能直接得到。

        因此，JDK定义了所有集合框架类使用的一些方法，以Collections类的静态方法存在。其中最常用的方法有：

static<T> void sort(List<T> list, Comparator<? superT> comp)

按照comp定义的排序方式对list进行排序。

static int frequency(Collection<?> c, Object obj)

计算obj在c中出现的次数。

例如，将输入指定个数的单词按首字母降序排列：

import java.util.*;

public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();

LinkedList<String> myll = new LinkedList<String>();
for(int i=0;i<n;i++){
String s = sc.nextLine();
myll.add(s);
}
sc.close();

Collections.sort(myll, new MyCom());;
for(String str:myll){
System.out.println(str);
}
}
}

class MyCom implements Comparator<String>{

@Override
public int compare(String s1, String s2) {
// TODO Auto-generated method stub
return s2.compareTo(s1);
}
}