5.4 集合的排序（Java學習筆記）（Collections.sort()，及Arrays.sort()底層分析）

1.Comparable介面

這個介面顧名思義就是用於排序的，如果要對某些對象進行排序，那麼該對象所在的類必須實現

Comparabld介面。Comparable介面只有一個方法CompareTo()，這個方法可以看做是指定的排序規則。

內置類已經實現了CompareTo方法，例如long

小於返回-1，等於返回0，大於返回1.

這裡只舉一個例子，例如int，double，Date等可以排序的內置類都已經實現了CompareTo方法，即指定了排序規則。

2.Collections.sort()和Arrays.sort()方法。

Colections是對集合進行操作的工具類，Collection.sort是對集合排序的方法。

Collections.sort()的底層實質是是調用Arrays.sort();

我們來看下Collections.sort()的源碼：

首先傳遞進去的集合必須是Comparable介面及其子類，而且後續會用到Comparable介面中的CompareTo方法。所以進行排序的類必須實現Comparable，

可以看出如果沒有實現Comparable介面，參數傳遞會出現錯誤。

我們點進list.sort()方法，就會看到下麵代碼：

我們可以看到，它是先將集合轉換成數組，然後調用Arrays.sort()方法。

排序排完後又將數組中元素逐個放入集合。

我們接下點進Arrays.sort()方法的源碼：

參數有兩個，有一個之前轉換成數組的集合a，c是一種排序規則，後面會講到。沒有指定的話，會自動設置為null。

然後判斷是否有排序規則，有就調用使用排序規則的排序方法。這裡看出當設置了排序規則c時，會進入使用排序規則的比較方法進行比較，

此時compareTo（）是不起作用的，起作用的是排序規則c中的compare（）方法。

接著進入sort().

我們可以看到這裡有兩個排序演算法，使用LegacyMergeSort.userRequested控制，第一個是歸併排序，也就是LegacyMergeSort.userRequested為true時進入的語句,

註意預設狀態下LegcyMergeSort是false，所以預設進去的是ComparableTimSort.sort()。這時一種優化的排序演算法，有興趣可以去查詢下，當然這種演算法比較複雜，

不便於理解。legactMergeSort()便於理解些，我們就先分析這個排序演算法。

預設是進入ComparableTimSort（），要想進入legacyMergeSort()我們就需要設置下LegacyMergeSort.userRequested的值。

這時我們可以自己設置LegacyMergeSort.userRequested的值，這句話是加在main中Sort調用之前的。

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

設置為true後我們進入的就是legcyMergeSort（）；

/*
註意：
這裡只是對排序演算法的一種優化，排序時的規則是不變的的。
（例如我現在要進行升序排序，可以用很多演算法，但是最後的結果一定是升序的。）
這裡我們主要看CompareTo（）方法返回值（1，0，-1）在排序中起到的作用，不關心具體演算法的優化，有興趣的可以自行查閱相關演算法。
*/

那麼我們這時就會進入gacyMergeSort();

我們點擊該方法，看它的代碼：

首先將存放集合數組的數組克隆，然後將克隆後的數組作為參數傳遞進aux，這裡c為null進入第一個mergeSort（）；

進入mergeSort（）我們可以看到：

我們先看傳遞進去的參數，srt，dest都是存放數據的數組，str是克隆的數組，dest是原數組，low=0，high=數組長度，off = 0；

首先定義了一個legth = high - low，得到的其實也是數組長度，

一開始進行一個判斷，長度小於INSERTIONSORT_THRESHOLD（常量7）就採用更適合長度小於7的數組的插入排序演算法，

我們可以看到代碼中排序的依據是CompareTo（）的返回值，如果返回值大於0則交換位置，反之則不交換。

如果不小於則採用適合數組長度大於7的其他排序方法。

後面還有更適合數組長度大於7的演算法，這裡沒有貼出這部分代碼，有興趣可自己去瞭解下。

(這裡只是對排序演算法執行次數的一種優化，排序時的規則是不變的的。我們這裡主要看CompareTo方法起到作用，不關心排序演算法的優化。)

這裡我們舉一個簡單的例子，假設現在我在鏈表裡面存放了三個long型數據312；

我們從調用Collections.Sort()方法開始分析源碼執行的過程，理解CompareTo方法的作用。

 進入mergeSort()方法後，我們先來看下傳遞進來的參數：

dest[] = {3,1,2}, low = 0, high = 3(數組長度);

接下來分析代碼執行過程：

首先i=0,然後j = 0，不滿足條件直接跳出，然後i++

此時i = 1,j=1,此時將元素轉換為Comparable介面調用CompareTo方法根據之前看的long裡面的Compare方法(Comparable)dest[0].compareTo(dest[1]) = 1.

如果沒有實現Comparable介面，這裡轉型也會出現錯誤。

//調用ComparTo（）返回值不清楚的，回到前面去看long裡面CompareTo方法

交換dest[0],dest[1]位置，此時數組順序：132.，然後j--，不滿足迴圈條件直接跳出，執行i++。

此時i=2，j=2,(Comparable)dest[1].compareTo(dest[2]) = 1，交換dest[1],dest[2],此時數組順序：123.執行i++；

i=3,不滿足迴圈條件，退出執行retun，結束排序，最終數組順序：123；

大家可以自己結合CompareTo方法的返回值分析分析排序過程。

瞭解了CompareTo在排序中起到的作用後，平常我們在實現Comparable介面，

實現其中的CompareTo方法時我們就可以明確CompareTo的返回值。

例如，a<b return 1.再結合CompareTo方法為1則交換位置，此時就是降序排列，

如果是a>b return 1,就變成升序。分析源碼後我們可以自己分析排序到是升序還是降序。

我們也可以這樣理解，如果返回1就代表交換這兩個元素位置。

//一般情況下大於返回1，等於返回0，小於返回-1，更符合我們的思維習慣，這時排序是升序

建議一般情況下這樣寫，此時是升序，如果是要求降序排列，改變返回值，將a>b return -1就是降序了。

再次聲明，要使用排序方法，必須實現Comparable介面。

我們來舉一個具體的例子。例如新聞，我們首先要看時間降序（即最近發生的新聞出現在最前面），

其次按點擊量降序（即點擊量多的出現在前面）。

那麼我們結合CompareTo方法在排序時的作用來考慮時間和點擊量比較的返回值。

首先，最近發生的新聞排在前面，如果A新聞時間在B新聞時間後面（也就是A新聞發生的時間離我們最近），

越在後面的時間的數值越大，Date本質上也是一個long型數。那麼最近發生的排在前面應該降序。也就是if(a時間> b時間)return -1;

對Date這一塊理解有問題的，可參考https://www.cnblogs.com/huang-changfan/p/9495067.html

如果時間相同，我們再來考慮點擊量，點擊量大的排在前面。

那麼這也是一個降序，if(點擊量a > 點擊量b) return -1；

這裡也可以用之前如果返回1，就代表交換位置，-1就不交換位置這樣來理解，理解的方式有很多種，

但歸根結底都是對源碼執行過程的分析，把握這一點就可以以不變應萬變。

接下來我們來看具體的代碼。

NewS類代碼

運行代碼

運行結果：
//排序前新聞
[標題：國慶高峰堵車，各景點爆滿！時間2018-10-07 09-23-53點擊量1000
, 標題：國慶仍有大部分家裡蹲！時間2018-10-07 08-23-54點擊量100
, 標題：驚呆，游客竟在做這種事！！！時間2018-10-07 09-23-54點擊量10000
]

//排序後新聞
[標題：驚呆，游客竟在做這種事！！！時間2018-10-07 09-23-54點擊量10000
, 標題：國慶高峰堵車，各景點爆滿！時間2018-10-07 09-23-53點擊量1000
, 標題：國慶仍有大部分家裡蹲！時間2018-10-07 08-23-54點擊量100
]

我們可以看到，首先按時間（距離我們最近發生的新聞排在最前面）進行排序，時間相同按點擊量排序。

我們可以看出mergeSort中使用Compareto方法只是判斷是否大於0，

當我們的CompareTo()返回的是0或-1時，for（）語句中判斷都是false,那麼我們能否在返回時不要-1，只返回0,1呢？

在當前方法（LeacySort()中的mergeSort()）顯然是可以的,因為0 > 0,-1>0的結果是相同的。

你要確定你進去的是LeacySort()中的mergeSort()，最好設置如下語句：

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

如果沒有設置的話LegcyMergeSort.userRequested預設為false，進去的就是另外一種排序演算法，在另外一種演算法中這樣設置是不行的。

當預設為false時，我們進入另外一個演算法看下：（這個演算法只是簡單點的過一遍，不分析具體步驟）

 為false時進去的是ComparebleTimSort.sort();我們進入這個演算法看下:

首先一個斷言，一般情況下都沒有問題，

然後nRemaing = hi - lo，hi是數組長度，lo是0.

MIN_MERGE是32。

接著就是根據數組a計算initRunLen的值，

我們先進入countRunAndMakeAscending();

但我們將-1也設置為0時，else後面的語句判斷的是返回值>=0。-1和0去判斷得到的結果是不同的。

這裡會造成這個值有問題，而這個值需要傳遞到排序演算法中，就會導致排序出現問題。News中的CompareTo方法的

返回值只有0，1的話這裡的runHi - lo是3，如果是按照正常的1,0，-1來的話runHi - lo是2。這個可以結合源碼自己分析一下。

這個執行完之後就要將得到的值，傳入我們的排序演算法中開始排序了。（上述分析都是基於之前代碼中創建的三個新聞對象來分析的）

返回runHi-lo後，我們回到上一級

我們將值傳入binarSort()中，然後點擊binarySort：

這個具體過程就不一一分析了，有興趣的可以分析下這些演算法。

start就是之前的返回值（runHi - lo），如有隻有1,0返回的是3，如果是正常的-1,0,1返回的是2.

我們來看第一個for語句，如果start是3就直接跳出迴圈(hi是數組長度，這裡為3)不進行排序，原有數據不會發生變化。

如果是2，進行排序，最後輸出是按照規則排序好的數據。

大家可以試下修改上面代碼中Nwes的compareTo()方法的返回值和運行代碼中設置true，false的部分：

（1）將 return -1改成return 0，LegacyMergeSort.userRequested為false時，輸出未正常排序結果。

                                                    LegacyMergeSort.userRequested為true時，輸出正常排序結果。

結合上述內容理解下整個的過程。

無論是哪種排序方法，嚴格按照（1，0，-1）返回，都可以輸出對應邏輯排序結果。

結合例子、源碼與上述內容分析分析，就可以清楚的知道排序執行的流程以及compareTo()返回值的作用。

3.Comparator介面

Comparator和Comparable類似，底層實現是一樣的，理解了Comparable中CompareTo()方法的作用後

理解Comparator就很簡單了。

我們之前說的實現Comparable介面的CompareTo方法是寫在需要進行排序的類裡面的，可以說這種方法就從屬於這個類。

但Comparator就不一樣了，它只是制定了一種排序規則，不需要從屬於誰，誰需要用這個規則拿來用就可以了。

具體的操作是，新建一個規則類，例如我要按照新聞點擊量排序，那麼我可以把這個類命名為NwesClickSort

這個類需要實現Comparator介面，並且實現裡面的ompare（）方法。 

我們來看下Comparator介面中compare方法：

這個作用和compareTo()方法的作用一樣，也是比較兩個值（o1,o2），然後返回1,0，-1.

使用compare排序時，就是調用這個方法來進行排序。

使用時，我們需要為NewsClickSort這個類實例化一個對象，這個對象代表一種排序規則。

然後將集合和對象（排序規則）傳遞到Collections.sort()中。

我們先來看個例子：//這裡面我們指定了一種排序規則，按照點擊量來排序，Nwes類還是之前的代碼，沒有任何修改。

運行結果：
//排序前結果
[標題：國慶高峰堵車，各景點爆滿！時間2018-10-10 08-40-50點擊量1000
, 標題：國慶仍有大部分家裡蹲！時間2018-10-10 07-40-50點擊量100
, 標題：驚呆，游客竟在做這種事！！！時間2018-10-10 08-40-50點擊量10000
]
//排序後結果
[標題：驚呆，游客竟在做這種事！！！時間2018-10-10 08-40-50點擊量10000
, 標題：國慶高峰堵車，各景點爆滿！時間2018-10-10 08-40-50點擊量1000
, 標題：國慶仍有大部分家裡蹲！時間2018-10-10 07-40-50點擊量100
]

排序規則中只指定了點擊量，所以排序後的結果是按點擊量來排序的。

我們可以看到上面代碼也設置了 

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");//

 我們就來分析下使用comparator介面中的compare方法的執行過程。

第一步當然是點進main中的

Collections.sort

註意那個c，就是實例化的比較規則。

我們繼續點擊sort（）：

我們會發現和之前看Comparable介面排序的執行過程是一樣的。

只是這時候c是實例化的排序規則，不是null了。

繼續點擊sort（）

這時c不等於null，所以進入後面的if(LegcyMergeSort.userRequested)進行判斷

前面說了預設LegayMergeSort.userRequested是false，這裡我們設置了為true，

所以我們點進legacyMergeSort():

c不等於null，我們點進第二個分支：

我們會發現和之前sort排序過程及CompareTo()的實現思路是一樣的，只是一個調用的是compareTo方法，

一個調用的是c.compare()方法。

LegayMergeSort.userRequested為false時，也和之前分析的sort排序過程及compareTo()的實現思路是一樣的，區別隻是一個調用

的是compareTo()方法，一個調用的是c.compare()方法。

LegayMergeSort.userRequested為false時的後續執行過程有興趣可以去看下，會發現和前面講的一樣。

到這裡整個比較過程就很清楚了。