最近Algorithms 4 課上提到了排序酪惭。趁著這個(gè)機(jī)會(huì)兄世，梳理一下伤哺。
1. 介紹
Comparable<T>接口和Comparator<T>接口都是JDK中提供的和比較相關(guān)的接口纸巷。使用它們可以對(duì)對(duì)象進(jìn)行比較大小贞绵，排序等操作厉萝。這算是之后排序的先導(dǎo)知識(shí)吧。
Comparable榨崩， 字面意思是“可以比較的”谴垫，所以實(shí)現(xiàn)它的類的多個(gè)實(shí)例應(yīng)該可以相互比較“大小”或者“高低”等等。
Comparator蜡饵， 字面意思是“比較儀弹渔，比較器”， 它應(yīng)該是專門用來(lái)比較用的“工具”溯祸。
2. Comparable
Comparable<T>接口
public interface Comparable<T> {
public int compareTo(T o);
}
首先看看JDK中怎么說(shuō)的：
This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's <i>natural ordering</i>, and the class's <tt>compareTo</tt> method is referred to as its <i>natural comparison method</i>.<p>
大意是: 任何實(shí)現(xiàn)這個(gè)接口的類肢专，其多個(gè)實(shí)例能以固定的次序進(jìn)行排列舞肆。次序具體由接口中的方法compareTo方法決定。
Lists (and arrays) of objects that implement this interface can be sorted automatically by {@link Collections#sort(List) Collections.sort} (and {@link Arrays#sort(Object[]) Arrays.sort}).
如果某個(gè)類實(shí)現(xiàn)了這個(gè)接口博杖，則它的List或數(shù)組都能使用Collections.sort()或Arrays.sort()進(jìn)行排序椿胯。
常見(jiàn)的類如Integer, Double, String都實(shí)現(xiàn)了此類。一會(huì)兒會(huì)結(jié)合源碼進(jìn)行分析剃根。
我們先來(lái)看Integer中的實(shí)現(xiàn)：
public final class Integer extends Number implements Comparable<Integer> {
private final int value;
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
public static int compareUnsigned(int x, int y) {
return compare(x + MIN_VALUE, y + MIN_VALUE);
}
我們只貼出了和比較相關(guān)的方法哩盲。
可以看到，compareTo方法其中調(diào)用了compare方法狈醉，這是JDK1.7增加的方法廉油。在Integer中新增這個(gè)方法是為了減少不必要的自動(dòng)裝箱拆箱。傳入compare方法的是兩個(gè)Integer的值x和y苗傅。
如果x < y抒线， 返回-1；如果x = y渣慕， 返回0嘶炭；如果x > y， 返回1逊桦。
順便一說(shuō)眨猎，JDK中的實(shí)現(xiàn)非常簡(jiǎn)潔，只有一行代碼强经， 當(dāng)判斷情況有三種時(shí)睡陪，使用這種嵌套的判斷 x ? a : b 可以簡(jiǎn)潔不少，這是該學(xué)習(xí)的匿情。
后面的compareUnsigned是JDK1.8新加入的方法, 用來(lái)比較無(wú)符號(hào)數(shù)宝穗。這里的無(wú)符號(hào)數(shù)意思是默認(rèn)二進(jìn)制最高位不再作為符號(hào)位，而是計(jì)入數(shù)的大小码秉。
其實(shí)現(xiàn)是
public static int compareUnsigned(int x, int y) {
return compare(x + MIN_VALUE, y + MIN_VALUE);
}
直接為每個(gè)值加了Integer的最小值 -231。我們知道Java中int類型為4個(gè)字節(jié)鸡号，共32位转砖。符號(hào)位占用一位的話，則其范圍為-231 到231 - 1鲸伴。
使用此方法時(shí)府蔗，所有正數(shù)都比負(fù)數(shù)小。最大值為 -1汞窗，因?yàn)?-1的二進(jìn)制所有位均為 1姓赤。
也就是1111 1111 1111 1111 1111 1111 1111 1111 > 其它任何32位數(shù)。
具體是什么情況呢仲吏？
2.1 計(jì)算機(jī)編碼
首先我們知道不铆，在計(jì)算機(jī)中蝌焚，所有數(shù)都是以二進(jìn)制存在，也就是0和1的組合誓斥。
為了使數(shù)字在計(jì)算機(jī)中運(yùn)算不出錯(cuò)只洒，出現(xiàn)了原碼，反碼和補(bǔ)碼劳坑。原碼就是一個(gè)數(shù)的二進(jìn)制表示毕谴，其中最高位為符號(hào)位，表示其正負(fù)距芬。
正數(shù)的原碼反碼補(bǔ)碼都一樣涝开，負(fù)數(shù)的反碼是除符號(hào)位以外全部取反，補(bǔ)碼為反碼加1框仔，如圖所示為32位bits（也就是4比特bytes）數(shù)的原碼反碼和補(bǔ)碼舀武。
為什么要使用反碼和補(bǔ)碼呢？用四位二進(jìn)制數(shù)舉例：
1的二進(jìn)制為0001存和，-1的二進(jìn)制為1001奕剃，如果直接相加，則1 + （-1） = 0捐腿，二進(jìn)制表示為0001 + 1001 = 1010 != 0纵朋，所以不能直接使用原碼做運(yùn)算。
后來(lái)出現(xiàn)了反碼茄袖，除符號(hào)位之外其他位取反操软，1001（-1）取反后為1110， 現(xiàn)在做加法 0001 （1） + 1110 （-1） = 1111 宪祥。由于1111是負(fù)數(shù)聂薪，所以取反之后才是其真實(shí)值，取反后為1000蝗羊，也就是-0藏澳。這能滿足條件了，但是美中不足的是耀找，0帶了負(fù)號(hào)翔悠。唯一的問(wèn)題其實(shí)就出現(xiàn)在0這個(gè)特殊的數(shù)值上。 雖然人們理解上+0和-0是一樣的野芒， 但是0帶符號(hào)是沒(méi)有任何意義的蓄愁。 而且會(huì)有0000原和1000原兩個(gè)編碼表示0。怎么辦呢狞悲？
人們又想出了補(bǔ)碼撮抓，它是反碼加1。-1的補(bǔ)碼是 1111摇锋，以上的運(yùn)算用補(bǔ)碼表示就是0001 （1） + 1111 （-1） = 0000 = 0丹拯。神奇的發(fā)現(xiàn)站超，這個(gè)式子完美契合了十進(jìn)制加法！
同時(shí)我們留出了1000咽笼，可以用它表示-8
(-1) + (-7) = (補(bǔ)碼) 1111 + 1001 = 1000 = -8顷编。注意，由于此處的-8使用了之前-0的補(bǔ)碼來(lái)表示剑刑，所以-8沒(méi)有沒(méi)有原碼和反碼表示（針對(duì)的四位媳纬，如果是八位，則沒(méi)有原碼和反碼的是-128施掏，依次類推）钮惠。
使用補(bǔ)碼, 不僅僅修復(fù)了0的符號(hào)以及存在兩個(gè)編碼的問(wèn)題, 而且還能夠多表示一個(gè)最低數(shù). 這就是為什么4位二進(jìn)制, 使用原碼或反碼表示的范圍為[-7, +7], 而使用補(bǔ)碼表示的范圍為[-8, 7].
這就是簡(jiǎn)單的要用反碼和補(bǔ)碼的原因。
2.2 大數(shù)溢出問(wèn)題
int類型在32位系統(tǒng)中占4個(gè)字節(jié)七芭、32bit素挽，補(bǔ)碼表示的的數(shù)據(jù)范圍為：
[10000000 00000000 00000000 00000000] ~ [01111111 11111111 11111111 11111111]
[?231,231?1]
[-2147483648, 2147483647]
在java中表示為：
[Integer.MIN_VALUE, Integer.MAX_VALUE]
與byte類型的表示一樣，由于負(fù)數(shù)比正數(shù)多表示了一個(gè)數(shù)字狸驳。對(duì)下限去相反數(shù)后的數(shù)值會(huì)超過(guò)上限值预明，溢出到下限，因此下限的相反數(shù)與下限相等耙箍；對(duì)上限去相反數(shù)的數(shù)值為負(fù)值撰糠，該負(fù)值比下限的負(fù)值大1，在可以表示的范圍內(nèi)辩昆，因此上限的相反數(shù)是上限直接取負(fù)值阅酪。
2.3 String類型的compareTo方法
看完Integer后，我們?cè)賮?lái)看String中compareTo的實(shí)現(xiàn)方式：
public final class String
implements java.io.Serializable, Comparable<String>, CharSequence {
/** The value is used for character storage. */
private final char value[]; // String的值
public int compareTo(String anotherString) {
int len1 = value.length;
int len2 = anotherString.value.length;
int lim = Math.min(len1, len2); // limit汁针， 表示兩個(gè)String中長(zhǎng)度較小的String長(zhǎng)度
char v1[] = value;
char v2[] = anotherString.value;
int k = 0;
while (k < lim) {
char c1 = v1[k];
char c2 = v2[k];
if (c1 != c2) {
return c1 - c2; // 如果char不相同术辐，則取其差值
}
k++; // 如果char值相同，則繼續(xù)往后比較
}
return len1 - len2; // 如果所有0 ~ (lim - 1)的char均相同施无，則比較兩個(gè)String的長(zhǎng)短
}
// 字面意思是對(duì)大小寫不敏感的比較器
public static final Comparator<String> CASE_INSENSITIVE_ORDER
= new CaseInsensitiveComparator();
private static class CaseInsensitiveComparator
implements Comparator<String>, java.io.Serializable {
private static final long serialVersionUID = 8575799808933029326L;
public int compare(String s1, String s2) {
int n1 = s1.length();
int n2 = s2.length();
int min = Math.min(n1, n2); // 和上面類似辉词，均是取兩個(gè)String間的最短長(zhǎng)度
for (int i = 0; i < min; i++) {
char c1 = s1.charAt(i);
char c2 = s2.charAt(i);
if (c1 != c2) {
c1 = Character.toUpperCase(c1); // 統(tǒng)一換成大寫
c2 = Character.toUpperCase(c2); // 統(tǒng)一換成大寫
if (c1 != c2) { // 大寫如果不相等則再換為小寫試試
c1 = Character.toLowerCase(c1);
c2 = Character.toLowerCase(c2);
if (c1 != c2) { // 到此處則確定不相等
// No overflow because of numeric promotion
return c1 - c2;
}
}
}
}
return n1 - n2;
}
/** Replaces the de-serialized object. */
private Object readResolve() { return CASE_INSENSITIVE_ORDER; }
}
// String的方法，可以直接使用這個(gè)方法和其它String進(jìn)行比較猾骡，
// 內(nèi)部實(shí)現(xiàn)是調(diào)用內(nèi)部比較器的compare方法
public int compareToIgnoreCase(String str) {
return CASE_INSENSITIVE_ORDER.compare(this, str);
}
}
String中的關(guān)于compare的方法相對(duì)復(fù)雜一點(diǎn)较屿，但還是比較簡(jiǎn)單。我們先不看其他的代碼卓练，只重點(diǎn)關(guān)注compareTo方法。
public int compareTo(String anotherString) {
int len1 = value.length;
int len2 = anotherString.value.length;
int lim = Math.min(len1, len2); // limit购啄， 表示兩個(gè)String中長(zhǎng)度較小的String長(zhǎng)度
char v1[] = value;
char v2[] = anotherString.value;
int k = 0;
while (k < lim) {
char c1 = v1[k];
char c2 = v2[k];
if (c1 != c2) {
return c1 - c2; // 如果char不相同襟企，則取其差值
}
k++; // 如果char值相同，則繼續(xù)往后比較
}
return len1 - len2; // 如果所有0 ~ (lim - 1)的char均相同狮含，則比較兩個(gè)String的長(zhǎng)短
}
內(nèi)容很簡(jiǎn)潔顽悼，就是取兩個(gè)String的長(zhǎng)度中較小的曼振，作為限定值(lim)。之后對(duì)數(shù)組下標(biāo)為從0到lim - 1的char變量進(jìn)行遍歷比較蔚龙，如果遇到不相同的值冰评，返回其差值。一般我們只用其正負(fù)性木羹，如果返回負(fù)數(shù)則說(shuō)明第一個(gè)對(duì)象比第二個(gè)對(duì)象“小”甲雅。
例如比較 "abc"和"bcd"，當(dāng)對(duì)各自第一個(gè)字符'a'和 'b'進(jìn)行比較時(shí)坑填，發(fā)現(xiàn) 'a' != 'b'抛人，則返回 'a' - 'b' ，這個(gè)值是負(fù)數(shù)脐瑰， char類型的-1妖枚，Java會(huì)自動(dòng)將其類型強(qiáng)轉(zhuǎn)為int型。最后得出結(jié)論"abc"比"bcd"小苍在。
3. Comparator
Comparator<T>接口
public interface Comparator<T> {
int compare(T o1, T o2);
}
這是一個(gè)外部排序接口绝页，它的功能是規(guī)定“比較大小”的方式。實(shí)現(xiàn)它的類可以作為參數(shù)傳入Collections.sort()或Arrays.sort()寂恬，使用它的比較方式進(jìn)行排序续誉。
它可以為沒(méi)有實(shí)現(xiàn)Comparable接口的類提供排序方式。
String類中以及Array類等都有實(shí)現(xiàn)此接口的內(nèi)部類掠剑。
在上面String的源碼中就有一個(gè)內(nèi)部的自定義Comparator類CaseInsensitiveComparator屈芜， 我們看看它的源碼。
public static final Comparator<String> CASE_INSENSITIVE_ORDER
= new CaseInsensitiveComparator();
private static class CaseInsensitiveComparator
implements Comparator<String>, java.io.Serializable {
private static final long serialVersionUID = 8575799808933029326L;
public int compare(String s1, String s2) {
int n1 = s1.length();
int n2 = s2.length();
int min = Math.min(n1, n2); // 和上面類似朴译，均是取兩個(gè)String間的最短長(zhǎng)度
for (int i = 0; i < min; i++) {
char c1 = s1.charAt(i);
char c2 = s2.charAt(i);
if (c1 != c2) {
c1 = Character.toUpperCase(c1); // 統(tǒng)一換成大寫
c2 = Character.toUpperCase(c2); // 統(tǒng)一換成大寫
if (c1 != c2) { // 大寫如果不相等則再換為小寫試試
c1 = Character.toLowerCase(c1);
c2 = Character.toLowerCase(c2);
if (c1 != c2) { // 到此處則確定不相等
// No overflow because of numeric promotion
return c1 - c2;
}
}
}
}
return n1 - n2;
}
/** Replaces the de-serialized object. */
private Object readResolve() { return CASE_INSENSITIVE_ORDER; }
}
// String的方法井佑，可以直接使用這個(gè)方法和其它String進(jìn)行比較，
// 內(nèi)部實(shí)現(xiàn)是調(diào)用內(nèi)部比較器的compare方法
public int compareToIgnoreCase(String str) {
return CASE_INSENSITIVE_ORDER.compare(this, str);
}
}
CaseInsensitiveComparator, 字面意思是對(duì)大小寫不敏感的比較器眠寿。
我們觀察它的compare方法躬翁，可以發(fā)現(xiàn)，它和上面的compareTo方法實(shí)現(xiàn)類似盯拱，都是取兩個(gè)String中長(zhǎng)度較小的盒发，作為限定值min，之后對(duì)數(shù)組下標(biāo)為從0到min - 1的char變量進(jìn)行遍歷比較狡逢。和上面稍有不同的是宁舰，此處先將char字符統(tǒng)一換成大寫（upper case）， 如果仍然不相等奢浑，再將其換為小寫（lower case）比較蛮艰。一個(gè)字母只有大寫或者小寫兩種情形，如果這兩種情況都不想等則確定不相等雀彼，返回其差值壤蚜。如果限定值內(nèi)所有的char都相等的話即寡，再去比較兩個(gè)String類型的長(zhǎng)度。
例如比較 "abC"和"ABc"袜刷，compareTo會(huì)直接返回 'a' - 'A'聪富，而compareToIgnoreCase方法由于使用了CaseInsensitiveComparator，比較結(jié)果最終會(huì)返回true著蟹。
參考文章
[1] Java源碼學(xué)習(xí)之Integer類（二）——1.8新增的幾個(gè)函數(shù)和變量
[2] 計(jì)算機(jī)原碼墩蔓、反碼、補(bǔ)碼詳解
