Collections.sort()
The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.
转自：http://dev.csdn.net/article/31/31142.shtm
以及：http://gaojiewyh.javaeye.com/blog/405514
=================================================
Java API针对集合类型排序提供了两种支持：
java.util.Collections.sort(java.util.List)
java.util.Collections.sort(java.util.List, java.util.Comparator)
第一个方法要求所排序的元素类必须实现java.lang.Comparable接口。
第二个方法要求实现一个java.util.Comparator接口。
java.lang.Comparable接口和 java.util.Comparator接口是Java对排序最提供最基本支持。这两个接口不但可以用于集合元素排序，还可以用于数组排序。
如果数组或集合元素是String类型，则可以利用Java API实现的Comparator对象String.CASE_INSENSITIVE_ORDER为容器元素排序。
下面给出两个里测试，涵盖集合和数组的排序，并且还演示了数组和集合的相互转换，附件里面是完整的排序演示代码。
方法一：实现 Comparable接口排序package collsort.comparable;
package com.cvicse.sort.comparable; public class Cat implements Comparable { private int age; private String name; public Cat(int age, String name) { this.age = age; this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } ...... public int compareTo(Cat o) { return this.getAge() - o.getAge(); } ......
} 通过实现Comparable接口实现个性化排序测试。排序测试，Collection.sort(list)升序排列Collections.sort(list, Collections.reverseOrder());降序排列；Collections.reverse(list);反转排序，先输出列表最后一个元素
public class TestComparable { public static void main(String args[]) { test(); test2(); } public static void test() { ...... List listCat1 = new ArrayList(); Cat cat1 = new Cat(34, "hehe"); Cat cat2 = new Cat(12, "haha"); Cat cat3 = new Cat(23, "leizhimin"); Cat cat4 = new Cat(13, "lavasoft"); listCat1.add(cat1); listCat1.add(cat2); listCat1.add(cat3); ...... System.out.println("调用Collections.sort(List list)listCat2升序排序："); Collections.sort(listCat1); System.out.println("降序排列元素:"); Collections.sort(listCat1, Collections.reverseOrder()); System.out.println("Collections.reverse 从列表中最后一个元素开始输出:"); Collections.reverse(listCat1); ...... } /** * 针对数组的排序 */ public static void test2() { String[] strArray = new String[] { "z", "a", "C" }; System.out.println("数组转换为列表"); List list = Arrays.asList(strArray); System.out.println("顺序排序列表"); Collections.sort(list); System.out .println("按String实现的Comparator对象String.CASE_INSENSITIVE_ORDER排序----"); Collections.sort(list, String.CASE_INSENSITIVE_ORDER); System.out.println("倒序排序列表"); Collections.sort(list, Collections.reverseOrder()); ...... }
} 方法二：实现Comparator接口排序
public class Person { private int age; private String name; ...... public int getAge() { return age; } public void setAge(int age) { this.age = age; } ......
} 实现了Comparator接口，重写了compare方法
import java.util.Comparator;
public class PersonComparator implements Comparator { public int compare(Person o1, Person o2) { return o1.getAge() - o2.getAge(); }
} 测试方法
public class TestComparator { public static void main(String args[]) { test1(); } public static void test1() { System.out.println("升序排序测试:"); List listPerson = new ArrayList(); Person person1 = new Person(34, "lavasoft"); Person person2 = new Person(12, "lavasoft"); Person person3 = new Person(23, "leizhimin"); Person person4 = new Person(13, "sdg"); listPerson.add(person1); listPerson.add(person2); listPerson.add(person3); Comparator ascComparator = new PersonComparator(); System.out.println("排序后集合为:"); // 利用Collections类静态工具方法对集合List进行排序 Collections.sort(listPerson, ascComparator); System.out.println("/n降序排序测试:"); // 从升序排序对象产生一个反转(降序)的排序对象 Comparator descComparator = Collections .reverseOrder(ascComparator); System.out.println("利用反转后的排序接口对象对集合List排序并输出:"); Collections.sort(listPerson, descComparator); outCollection(listPerson); }
} 以上的例子中使用是对int类型的属性排序，对String属性排序可以用以下的方法
public int compareTo(Cat o) {return this.getName().compareTo(o.getName());} comparetTo()函数的使用说明：
如果
结果
<0
a
==0
a==b
>=0
a>b
Java如何通过所实现接口的方法进行排序是API内部的事情，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）。这样，元素将总是排序形式的。
![使用Windbg调试.Net应用程序[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)