問(wèn)題引入
??在之前的一次Java上機(jī)實(shí)習(xí)中，老師布置了一道很簡(jiǎn)單的題:
從控制臺(tái)輸入10個(gè)整數(shù)，對(duì)它們進(jìn)行升序排序并輸出膊毁。
??考慮到只有10個(gè)數(shù)，需要比較的次數(shù)不是很多基跑，所以當(dāng)時(shí)我自己寫(xiě)了一段冒泡排序的算法然后就上交作業(yè)婚温。交作業(yè)之后我突然想到一個(gè)問(wèn)題：JDK是否有類(lèi)似于STL中的std::sort方法，能實(shí)現(xiàn)基本的排序而無(wú)需用戶(hù)自己實(shí)現(xiàn)媳否？
Collections.sort簡(jiǎn)介
??第9版《Java核心技術(shù)卷Ⅰ》的第607頁(yè)介紹了一個(gè)方法：
Collections類(lèi)中的sort方法可以對(duì)實(shí)現(xiàn)了List接口的集合進(jìn)行排序栅螟。這個(gè)方法假定列表元素實(shí)現(xiàn)了Comparable接口荆秦。
??查看Java官方文檔可知，sort方法有兩種重載形式力图。第一種重載是：
static <T extends Comparable<? super T>> void sort(List<T> list)
??根據(jù)官方文檔的描述步绸，這個(gè)方法將列表元素進(jìn)行升序排序，但是列表要滿(mǎn)足以下條件：
??1.列表元素實(shí)現(xiàn)了Comparable接口吃媒，且任意兩個(gè)列表元素都是可比的瓤介。
??2.列表必須支持set方法。
??如果要通過(guò)這個(gè)方法來(lái)完成我上面提到的作業(yè)赘那，那顯然是行得通的：整數(shù)可以進(jìn)行相互比較刑桑，第一個(gè)條件滿(mǎn)足；把10個(gè)整數(shù)放入一個(gè)ArrayList或LinkedList中募舟，這兩個(gè)列表都支持set方法祠斧，第二個(gè)條件滿(mǎn)足。實(shí)現(xiàn)代碼如下：
import java.util.*;
public class Sort {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
List<Integer> list = new ArrayList<>();
//用戶(hù)輸入10個(gè)整數(shù)
System.out.println("請(qǐng)輸入10個(gè)整數(shù)：");
for(int i = 0; i < 10; i++)
{
list.add(scan.nextInt());
}
scan.close();
//排序
Collections.sort(list);
//輸出排序結(jié)果
System.out.println(list);
}
}
??程序運(yùn)行結(jié)果如下：
??用sort方法可以很方便地實(shí)現(xiàn)升序排序拱礁，但能否進(jìn)行降序排序琢锋？答案是肯定的，《Java核心技術(shù)卷Ⅰ》中介紹了一種用sort進(jìn)行降序排序的簡(jiǎn)潔方法呢灶。這種方法需要用到sort方法的第二種重載形式：
public static <T> void sort(List<T> list,Comparator<? super T> c)
??如果想采用其他方式進(jìn)行排序吴超，那么可將一個(gè)Comparator對(duì)象作為sort方法的第二個(gè)參數(shù)。當(dāng)要進(jìn)行逆序排序時(shí)填抬，最簡(jiǎn)便的方法是將Collections.reverseOrder()作為第二個(gè)參數(shù)烛芬。
import java.util.*;
public class Sort {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
List<Integer> list = new ArrayList<>();
//用戶(hù)輸入10個(gè)整數(shù)
System.out.println("請(qǐng)輸入10個(gè)整數(shù)：");
for(int i = 0; i < 10; i++)
{
list.add(scan.nextInt());
}
scan.close();
//逆序排序
Collections.sort(list,Collections.reverseOrder());
//輸出排序結(jié)果
System.out.println(list);
}
}
??程序運(yùn)行結(jié)果如下：
更進(jìn)一步：排序?qū)ο蟛皇腔緮?shù)據(jù)類(lèi)型
??在上面的例子中，列表中的元素是整數(shù)飒责，所以排序邏輯是很顯然的：如果是升序排序赘娄，那就小數(shù)在前，大數(shù)在后宏蛉。但是遣臼，如果排序的對(duì)象并非屬于整數(shù)、浮點(diǎn)數(shù)之類(lèi)的基本數(shù)據(jù)類(lèi)型拾并，那么這些對(duì)象之間的“大小”關(guān)系該如何定義揍堰？假設(shè)有這樣一道題：
定義一個(gè)點(diǎn)類(lèi)，其中有整型屬性x和y嗅义，代表其坐標(biāo)屏歹；除了這兩個(gè)屬性以外沒(méi)有其他屬性。隨機(jī)產(chǎn)生10個(gè)點(diǎn)之碗，并按照這些點(diǎn)與原點(diǎn)(0,0)之間的距離大小對(duì)點(diǎn)進(jìn)行降序排序蝙眶。
??如果仍想通過(guò)sort方法進(jìn)行排序的話(huà)，首先點(diǎn)類(lèi)就必須滿(mǎn)足上面曾經(jīng)提過(guò)的約束條件：點(diǎn)對(duì)象是可比的褪那，因此點(diǎn)類(lèi)必須實(shí)現(xiàn)Comparable接口幽纷。查看官方文檔可知式塌，Comparable接口中只有一個(gè)方法：
int compareTo(T o)
??調(diào)用這個(gè)方法的對(duì)象將會(huì)與參數(shù)o進(jìn)行比較，小于o友浸、等于o和大于o分別對(duì)應(yīng)的返回值為負(fù)數(shù)峰尝、0和正數(shù)。對(duì)象之間相對(duì)大小的判斷方法是自定義的收恢，在這個(gè)問(wèn)題中武学，就是通過(guò)比較各點(diǎn)與原點(diǎn)之間的距離來(lái)判斷大小，所以點(diǎn)類(lèi)的實(shí)現(xiàn)如下：
class Point implements Comparable<Point>{
private int x;
private int y;
public Point(int x,int y)
{
this.x = x;
this.y = y;
}
@Override
//如果該點(diǎn)到原點(diǎn)的距離大于o點(diǎn)到原點(diǎn)的距離派诬，則該點(diǎn)大于o點(diǎn)
public int compareTo(Point o) {
int distance1 = (this.x) * (this.x) + (this.y) * (this.y);
int distance2 = (o.x) * (o.x) + (o.y) * (o.y);
return (distance1 > distance2) ? 1 : ((distance1 == distance2) ? 0 : -1);
}
@Override
public String toString() {
return "(" + x + ","+ y + ")";
}
}
??因?yàn)橐M(jìn)行降序排序劳淆，所以可以通過(guò)將Collections.reverseOrder()作為sort方法的第二個(gè)參數(shù)來(lái)實(shí)現(xiàn)：
public class SortDemo {
private static List<Point> list = new ArrayList<>();
public static void main(String[] args) {
//隨機(jī)生成10個(gè)點(diǎn)
for(int i = 0; i < 10; i++)
{
//點(diǎn)的坐標(biāo)取值在[1,20]之間
int x = (int)(Math.random() * 20) + 1;
int y = (int)(Math.random() * 20) + 1;
list.add(new Point(x,y));
}
System.out.print("排序前：");
System.out.println(list);
//降序排序
Collections.sort(list,Collections.reverseOrder());
System.out.print("排序后：");
System.out.println(list);
}
}
??程序結(jié)果如下：
??現(xiàn)在對(duì)sort方法進(jìn)行小結(jié)：
??實(shí)現(xiàn)了Comparable接口的類(lèi)都可以用sort方法進(jìn)行排序，默認(rèn)的排序方法是升序默赂；如果想進(jìn)行降序排序，只需把Collections.reverseOrder作為第二個(gè)參數(shù)傳給sort方法括勺。
了解Comparator接口
??上面反復(fù)提到的Collections.reverseOrder方法返回的是一個(gè)Comparator對(duì)象缆八。其實(shí)Comparator接口并不陌生，常用的equals方法就來(lái)自這個(gè)接口疾捍。Comparator接口用來(lái)定義兩個(gè)對(duì)象之間的比較方法奈辰，它有一個(gè)叫做compare的方法，函數(shù)簽名如下：
int compare(T o1,T o2)
?? o1 > o2乱豆，返回正數(shù)奖恰；o1 = o2，返回0宛裕；o1 < o2瑟啃，返回負(fù)數(shù)。
??從前面的例子可以看出揩尸，可以使用Comparator對(duì)象來(lái)控制sort的排序方法蛹屿，這是如何實(shí)現(xiàn)的？查看sort方法的相關(guān)源碼岩榆，我發(fā)現(xiàn)其中有這樣一段代碼：
??注意看圖中用紅線(xiàn)框起來(lái)的部分错负。經(jīng)分析可知，這段代碼實(shí)現(xiàn)了這樣的邏輯：如果compare的返回值為正數(shù)勇边，就交換進(jìn)行比較的兩個(gè)元素的位置犹撒。于是可以得出這樣一個(gè)結(jié)論，如果讓 x > y 時(shí)compare(x,y)返回正數(shù)粒褒，那么交換 x 和 y 的位置后大的元素在后识颊，這就實(shí)現(xiàn)了升序排序；反之怀浆，如果讓 x < y 時(shí)compare(x,y)返回正數(shù)谊囚，那么交換位置后小的元素在后怕享，這就實(shí)現(xiàn)了降序排序。這就是Comparator對(duì)象控制排序方式的原理镰踏。
??通過(guò)Comparator對(duì)象來(lái)實(shí)現(xiàn)點(diǎn)對(duì)象的降序排序函筋，一種可行的實(shí)現(xiàn)方式如下：
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
//點(diǎn)類(lèi)
class Point {
private int x;
private int y;
public Point(int x,int y)
{
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
@Override
public String toString() {
return "(" + x + ","+ y + ")";
}
}
public class SortDemo {
private static List<Point> list = new ArrayList<>();
public static void main(String[] args) {
//隨機(jī)生成10個(gè)點(diǎn)
for(int i = 0; i < 10; i++)
{
//點(diǎn)的坐標(biāo)取值在[1,20]之間
int x = (int)(Math.random() * 20) + 1;
int y = (int)(Math.random() * 20) + 1;
list.add(new Point(x,y));
}
System.out.print("排序前：");
System.out.println(list);
//降序排序
Collections.sort(list,new Comparator<Point>() {
@Override
//當(dāng) o1 < o2 時(shí)返回正數(shù)
public int compare(Point o1, Point o2) {
int distance1 = (o1.getX()) * (o1.getX()) + (o1.getY()) * (o1.getY());
int distance2 = (o2.getX()) * (o2.getX()) + (o2.getY()) * (o2.getY());
return (distance1 < distance2) ? 1 : ((distance1 == distance2) ? 0 : -1);
}
});
System.out.print("排序后：");
System.out.println(list);
}
}
??程序運(yùn)行結(jié)果如下：
??注意，在上面的程序中Point類(lèi)并沒(méi)有實(shí)現(xiàn)Comparable接口奠伪，這是因?yàn)橐呀?jīng)通過(guò)實(shí)現(xiàn)Comparator接口來(lái)定義Point對(duì)象的比較方法跌帐，所以也就無(wú)需實(shí)現(xiàn)Comparable接口。
