zhangge's stupid and messy life

Java排序之Comparable和Comparator

27 Jun 2013

这么简单的东西，可是每次用的是总得有一点点忘记，于是乎，还是记录一下呗

1 排序

实际上，我记得把排序做成一个通用模板的是在看C primary plus这本书的时候，那是大一学习C语言，学习了list，当然，快速排序是在中学时候就会了；cpp这书上就把快排给学通用化了。后来学习java的时候知道了jdk里面提供了排序的api，忽然恍然大悟，原来一样的思想！

当然了，jdk里面的api到底用的是哪种排序算法，看源码就知道了，应该是快速排序，堆排序，合并排序这些的了。我们知道使用的API即可：

Collections.sort();
Arrays.sort();

而其实Collections里面调用的也是Arrays的方法，因此，核心的代码都是在Arrays里面的。如果我们的数据结构是list就是用前者接口，是数组就使用后者接口。

排序我们需要的是比较元素的大小，在java里面就是比较对象的大小，算法是固定的，我们可以在比较那里扩展，正常比较是顺序，我们修改比较器以后就可以使其逆序了。

sort方法的排序默认是自然顺序的，也就是顺序，调用比较的方法，小的放前面，大的放后面。

扩展的方式有两种，一是元素本身支持比较大小，二是提供一个比较器来比较元素大小，因此sort方法是有两个重载的。

2 Comparable接口

元素对象实现这个接口即表示元素本身支持比较大小。需要实现一个方法：

public int compareTo(Person o);

学习排序的时候，我们的元素都是数值，既然是数字，那么直接相减就能知道大小了，而java里面不能像C++那样重载操作符，就是不能改变减号对对象进行操作了，于是只能通过实现接口。意思也是一样的，下面两个方法的意思一样：

A.compareTo(B) == A - B

因此compareTo方法返回负值表示A比B要小，A在排序算法中将会排放在前面，B会被排放在后面。可见，如果我们要逆序的话，只需要在返回值那里修改一下即可。

3 Comparator接口

使用Comparable接口表示集合内部实现了比较的方法，是使用Comparator接口就表示集合外部程序实现了比较的方法，这样更加的易于扩展，因为它采用了策略模式。我们可以在外面实现不同的比较器，这不会去修改集合的元素，比较是外面来控制的。

public int compare(Person o1, Person o2);

调用compare方法相当于里面的两个参数前者减去后者，意义和上文一样，返回int的值。

compare(A, B) == A - B

实际上，这些是排序模板里面调用的，不需要我们关心，只需要理解就好了。