Java中的Set，List，Map引出的排序技巧。
一。关于概念： List接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和LinkedList。你可以将任何东西放到一个List容器中，并在需要时从中取出。ArrayList从其命名中可以看出它是一种类似数组的形式进行存储，因此它的随机访问速度极快，而 LinkedList的内部实现是链表，它适合于在链表中间需要频繁进行插入和删除操作。在具体应用时可以根据需要自由选择。前面说的Iterator只能对容器进行向前遍历，而ListIterator则继承了Iterator的思想，并提供了对List进行双向遍历的方法。
Set接口也是Collection的一种扩展，而与List不同的时，在Set中的对象元素不能重复，也就是说你不能把同样的东西两次放入同一个Set容器中。它的常用具体实现有HashSet和TreeSet类。HashSet能快速定位一个元素，但是你放到HashSet中的对象需要实现hashCode()方法，它使用了前面说过的哈希码的算法。而TreeSet则将放入其中的元素按序存放，这就要求你放入其中的对象是可排序的，这就用到了集合框架提供的另外两个实用类Comparable和Comparator。一个类是可排序的，它就应该实现Comparable接口。有时多个类具有相同的排序算法，那就不需要在每分别重复定义相同的排序算法，只要实现Comparator接口即可。集合框架中还有两个很实用的公用类：Collections和Arrays。Collections提供了对一个Collection容器进行诸如排序、复制、查找和填充等一些非常有用的方法，Arrays则是对一个数组进行类似的操作。
Map是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个Map，依次类推，这样就可形成一个多级映射。对于键对象来说，像Set一样，一个Map容器中的键对象不允许重复，这是为了保持查找结果的一致性;如果有两个键对象一样，那你想得到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求。你可以将任意多个键都映射到一个值对象上，这不会发生任何问题（不过对你的使用却可能会造成不便，你不知道你得到的到底是那一个键所对应的值对象）。Map有两种比较常用的实现：HashMap和TreeMap。 HashMap也用到了哈希码的算法，以便快速查找一个键，TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如 firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。键和值的关联很简单，用pub(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。
二.Java技巧：列表排序 在Java Collection Framework中定义的List实现有Vector，ArrayList和LinkedList。这些集合提供了对对象组的索引访问。他们提供了元素的添加与删除支持。然而，它们并没有内置的元素排序支持。
你能够使用java.util.Collections类中的sort()方法对List元素进行排序。你既可以给方法传递一个List对象，也可以传递一个List和一个Comparator。如果列表中的元素全都是相同类型的类，并且这个类实现了Comparable接口，你可以简单的调用 Collections.sort()。如果这个类没有实现Comparator，你也可以传递一个Comparator到方法sort()中，进行排序。如果你不想使用缺省的分类顺序进行排序，你同样可以传递一个Comparator到方法sort()中来进行排序。如果列表中的元素并不都是相同类型的类，你在进行排序的时候就不是这样幸运了。除非你编写一个专用的跨类的Comparator。 排序的顺序怎么样呢？如果元素是String对象，却省的排序顺序是按照字符编码进行的，基本上是每个字符的ASCII/Unicode 值。如果严格的限制在处理英文，却省的排序顺序通常是足够的，因为它首先排A-Z，然后是小写字母a-z。然而如果你处理非英文字，或者你只是想使用不同的排序顺序，这样Collections.sort()就出现了第二种变化。例如，你想使用字符串的反序进行排序。为了实现这个功能，你可以在 Collections类中通过reverseOrder()来获取一个反序Comparator。然后，你将反序Comparator传递给 sort()方法。换句话说，你作如下工作：
| List list = …; Comparator comp = Collections.reverseOrder(); Collections.sort(list, comp); |
如果列表包含项目：Man, man, Woman, 和woman，排序好的列表将是Man, Woman, man, woman。这里没有什么复杂的。需要注意的非常重要的一点是Collections.sort()是进行原位排序。如果你需要保留原序，需要先对原集合进行复制，在排序，就像这样：
| List list = …; List copyOfList = new ArrayList(list); Collections.sort(copyOfList); |
这里，排好序的列表是：Man, Woman, man, woman，但是原始列表（Man, man, Woman, woman）被保留了。
到目前为止，排序是区分大小写的。你如何进行不去分大小写的排序呢？一种实现方式是象这样实现Comparator:
| public static class CaseInsensitiveComparator implements Comparator { public int compare(Object element1, Object element2) { String lower1 = element1.toString().toLowerCase(); String lower2 = element2.toString().toLowerCase(); return lower1.compareTo(lower2); } } |
你确实不需要手工的创建这个类。而是，你可以是用以存在的Comparator，CASE_INSENSIVTIVE_ORDER，它是在String类中定义的。
这种实现方式有一点小小的问题。Sort()算法提供稳定的排序，并保持与原有序列相同的元素。这意味着一个包含两个元素”woman”和”Woman”的列表将有不同的排序，而这种不同是根据两个元素在列表中出现的先后次序决定的。 语言的不同又会怎么样呢？java.text包提供了Collector和CollectionKey类来进行区分语言的排序。这里是例子:
注意，如果你的文本是本地语言，而不是缺省语言，你需要传递一个本地语种给getInstance()方法，就象:
| public static class CollatorComparator implements Comparator { Collator collator = Collator.getInstance(); public int compare(Object element1, Object element2) { CollationKey key1 = collator.getCollationKey( element1.toString()); CollationKey key2 = collator.getCollationKey( element2.toString()); return key1.compareTo(key2); } } |
你是在对集合关键字进行排序，而不是实际的字符串。这不仅提供固定的不区分大小写的排序，而且它是跨语种的排序。换句话说，如果你对西班牙文和非西班牙文的混合词进行排序，词ma?ana (tomorrow)将排在mantra的前面。如果你不使用Collector，ma?ana将排在mantra的后面。
下面这个程序对一个列表进行不同类型的排序（缺省的、区分大小写的、区分语种的）：
| import java.awt.BorderLayout; import java.awt.Container; import java.io.*; import java.text.*; import java.util.*; import javax.swing.*; public class SortIt { public static class CollatorComparator implements Comparator { Collator collator = Collator.getInstance(); public int compare(Object element1, Object element2) { CollationKey key1 = collator.getCollationKey( element1.toString()); CollationKey key2 = collator.getCollationKey( element2.toString()); return key1.compareTo(key2); } } public static class CaseInsensitiveComparator implements Comparator { public int compare(Object element1, Object element2) { String lower1 = element1.toString(). toLowerCase(); String lower2 = element2.toString(). toLowerCase(); return lower1.compareTo(lower2); } } public static void main(String args[]) { String words[] = {“man”, “Man”, “Woman”, “woman”, “Manana”, “manana”, “ma?ana”, “Ma?ana”, “Mantra”, “mantra”, “mantel”, “Mantel” }; // Create frame to display sortings JFrame frame = new JFrame(“Sorting”); frame.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE); Container contentPane = frame.getContentPane(); JTextArea textArea = new JTextArea(); JScrollPane pane = new JScrollPane(textArea); contentPane.add(pane, BorderLayout.CENTER); // Create buffer for output StringWriter buffer = new StringWriter(); PrintWriter out = new PrintWriter(buffer); // Create initial list to sort List list = new ArrayList(Arrays.asList(words)); out.println(“Original list:”); out.println(list); out.println(); // Perform default sort Collections.sort(list); out.println(“Default sorting:”); out.println(list); out.println(); // Reset list list = new ArrayList(Arrays.asList(words)); // Perform case insensitive sort Comparator comp = new CaseInsensitiveComparator(); Collections.sort(list, comp); out.println(“Case insensitive sorting:”); out.println(list); out.println(); // Reset list list = new ArrayList(Arrays.asList(words)); // Perform collation sort comp = new CollatorComparator(); Collections.sort(list, comp); out.println(“Collator sorting:”); out.println(list); out.println(); // Fill text area and display textArea.setText(buffer.toString()); frame.pack(); frame.show(); } } |
如果你的主要问题是顺序访问，可能列表不是你的好的数据结构选择。只要你的集合没有重复，你可以在树（TreeSet）中保存你的元素（提供或不提供Comparator）。这样，元素将总是排序形式的。
三.Collections.sort() 对 List 排序
import java.util.Comparator; import java.util.List; import java.util.ArrayList; import java.util.Collections;
class User { String name; String age; public User(String name,String age){ this.name=name; this.age=age; } public String getAge() { return age; } public void setAge(String age) { this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } }
class ComparatorUser implements Comparator{
public int compare(Object arg0, Object arg1) { User user0=(User)arg0; User user1=(User)arg1; //首先比较年龄，如果年龄相同，则比较名字 int flag=user0.getAge().compareTo(user1.getAge()); if(flag==0){ return user0.getName().compareTo(user1.getName()); }else{ return flag; } } }
public class SortTest {
public static void main(String[] args){ List userlist=new ArrayList(); userlist.add(new User(“dd”,”4″)); userlist.add(new User(“aa”,”1″)); userlist.add(new User(“ee”,”5″)); userlist.add(new User(“bb”,”2″)); userlist.add(new User(“ff”,”5″)); userlist.add(new User(“cc”,”3″)); userlist.add(new User(“gg”,”6″)); ComparatorUser comparator=new ComparatorUser(); Collections.sort(userlist, comparator); for (int i=0;i<userlist.size();i++){ User user_temp=(User)userlist.get(i); System.out.println(user_temp.getAge()+”,”+user_temp.getName()); } } }
//首先比较年龄，如果年龄相同，则比较名字
结果: 1, aa 2, bb 3, cc 4, dd 5, ee 5, ff 6, gg
四：Java.util.Collections.sort(List list)与Comparable,Comparator 接口
copyright ? lizongbo
copyright ? lizongbo
copyright ? lizongbo
copyright ? lizongbo
copyright ? lizongbo
copyright ? lizongbo
copyright ? lizongbo
原帖地址：http://www.blogjava.net/shingo/archive/2009/03/31/263190.html