ArrayList中有一個(gè)sort排序方法,只要你實(shí)現(xiàn)了Comparator的接口,按照你自己的排序業(yè)務(wù)進(jìn)行實(shí)現(xiàn),你只要告訴這個(gè)接口按照什么類型進(jìn)行排序就OK了。這種方式類似于設(shè)計(jì)模式中的策略模式，把流程劃分好，具體的業(yè)務(wù)邏輯由用戶指定。這時(shí)候我們需要帶著問題去看看里面具體是如何實(shí)現(xiàn)的..
環(huán)境描述
JDK : 1.8
偽代碼:
public static void main(String[] args) {
// 初始化一組數(shù)據(jù),這組數(shù)據(jù)可以是任意對(duì)象
int[] data = {7, 5, 1, 2, 6, 8, 10, 12, 4, 3, 9, 11, 13, 15, 16, 14};
// 構(gòu)建成一個(gè)集合
List<Integer> list = new ArrayList<>();
for (int i = 0; i < data.length; i++) {
list.add(data[i]);
}
// 設(shè)定自己的比較方式
// 1順序 -1倒序
list.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
int i = o1 > o2 ? 1 : -1;
System.out.println("開始比較 [o1] - " + o1 + "\t [o2] - " + o2);
return i;
}
});
// 打印結(jié)果
System.out.println(JSON.toJSONString(list));
}
問題
- 它是如何實(shí)現(xiàn)的 ?
實(shí)踐
跟蹤代碼
- ArrayList中的 sort方法
public void sort(Comparator<? super E> c) {
// 集合大小
final int expectedModCount = modCount;
// 將排序交給Arrays去實(shí)現(xiàn)
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
- Arrays中的sort方法又是交給一個(gè)TimSort類去實(shí)現(xiàn)的,我們直接看TimSort類的sort方法
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
int nRemaining = hi - lo;
// 這里表示如果大小小于2則沒有排序的必要了
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
// 這里會(huì)根據(jù)數(shù)組的大小來使用不同的排序方式
// 默認(rèn)的如果大小不超過32則會(huì)采用歸并排序
if (nRemaining < MIN_MERGE) {
// 這里面會(huì)根據(jù)你數(shù)組中數(shù)據(jù)是遞增還是遞減的方式來劃分成兩塊
// 舉例 1,4,7,3,6,2 這里一開始是遞增直到7結(jié)束,如果比較方法得出的的值是-1(遞減),
//則會(huì)將1,4,7先進(jìn)行反轉(zhuǎn)得到 7,4,1 然后劃分成兩個(gè)邏輯部分{7,4,1} , {3,6,2} 進(jìn)行歸并運(yùn)算
// 這里的返回值得到的就是劃分成兩部分的下標(biāo)索引比如上面舉例的就是3
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
// 歸并排序
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
//////////////////////////////////// 這里是數(shù)組長度大于32的情況下 //////////////////////////////////////////
/**
* March over the array once, left to right, finding natural runs,
* extending short natural runs to minRun elements, and merging runs
* to maintain stack invariant.
*/
TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
// 得到一個(gè)最小的歸并長度,根據(jù)這個(gè)長度來判斷這組數(shù)據(jù)具體要?dú)w并幾次
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi, c);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen, c);
//運(yùn)行長度
runLen = force;
}
// Push run onto pending-run stack, and maybe merge
// 將運(yùn)行下標(biāo)進(jìn)行記錄
ts.pushRun(lo, runLen);
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}
private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
Comparator<? super T> c) {
assert lo < hi;
// 得到下一個(gè)坐標(biāo)
int runHi = lo + 1;
// 如果都等于1
if (runHi == hi)
return 1;
// Find end of run, and reverse range if descending
//找到運(yùn)行結(jié)束，如果下降，反向范圍
// 這里面會(huì)根據(jù)你數(shù)組中數(shù)據(jù)是遞增還是遞減的方式來劃分成兩塊
// 舉例 1,4,7,3,6,2 這里一開始是遞增直到7結(jié)束,如果比較方法得出的的值是-1(遞減),
//則會(huì)將1,4,7先進(jìn)行反轉(zhuǎn)得到 7,4,1 然后劃分成兩個(gè)邏輯部分{7,4,1} , {3,6,2} 進(jìn)行歸并運(yùn)算
if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
reverseRange(a, lo, runHi);
} else { // Ascending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
}
return runHi - lo;
}
// 具體的歸并排序
private static <T> void binarySort(T[] a, int lo, int hi, int start,
Comparator<? super T> c) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
// 這里的start 是等于上面劃分的臨界點(diǎn)的值,比如上面舉例的就是3,從3的下標(biāo)值開始和一部分進(jìn)行比較
for ( ; start < hi; start++) {
T pivot = a[start];
// Set left (and right) to the index where a[start] (pivot) belongs
// 左邊就相當(dāng)于 {7,4,1}的下標(biāo),默認(rèn)是0
int left = lo;
// 右邊就相當(dāng)于{3,6,2}
int right = start;
assert left <= right;
/*
* Invariants:
* pivot >= all in [lo, left).
* pivot < all in [right, start).
*/
// 找歸并位置,必須左邊小于右邊
while (left < right) {
// 運(yùn)算方式 , 你可以理解成 count / 2 得到的整數(shù)
int mid = (left + right) >>> 1;
// 如果小于0則改變r(jià)ight的位置
if (c.compare(pivot, a[mid]) < 0)
right = mid;
else
// 如果大于 則改變left值,
left = mid + 1;
}
// 直到相等,表示找到了該值應(yīng)該落在的區(qū)間
assert left == right;
/*
* The invariants still hold: pivot >= all in [lo, left) and
* pivot < all in [left, start), so pivot belongs at left. Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that's why this sort is stable.
* Slide elements over to make room for pivot.
*/
// 這里是算出要移動(dòng)的區(qū)間長度,如果區(qū)間長度在2以內(nèi),則交換一下位置就興了,如果大于2,則采用數(shù)據(jù)復(fù)制移動(dòng)的方式
int n = start - left; // The number of elements to move
// Switch is just an optimization for arraycopy in default case
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n);
}
// 最后將右邊預(yù)算的值,填充的合適的區(qū)間內(nèi)
a[left] = pivot;
}
}
畫圖理解一下:
-
初始化數(shù)組:
image.png -
通過countRunAndMakeAscending方法,得到數(shù)據(jù)的走勢(shì),是遞增還是遞減,邏輯上劃分成了兩個(gè)數(shù)組,劃分值是下標(biāo)值3
image.png -
循環(huán)B中的數(shù)據(jù)與A做歸并,這時(shí)候是從下標(biāo)3開始,進(jìn)行運(yùn)算
運(yùn)算流程:開始從第三個(gè)進(jìn)行 , 這時(shí)候會(huì)定義三個(gè)變量 : 1. left 最左邊開始移動(dòng)的數(shù) 2. right 最右邊開始移動(dòng)數(shù) 3.start 開始移動(dòng)數(shù) 初始化值: left = 0; right = 3; start = 3; 移動(dòng)的運(yùn)算公式 int mid = (left + right) >>> 1 ; // 這里可以看作是 移動(dòng)后的值/2 循環(huán)運(yùn)算條件 : left < right 第一次運(yùn)算: mid = 1; // 1的下標(biāo)值是5. // 2 > 5 ? 決定是改變left還是right.. 這時(shí)候是改變r(jià)ight , right = mid; // 這時(shí)候right = 1; left = 0; //循環(huán)條件滿足 第二次運(yùn)算: 1. 1>>>1 = 0 // 0的下標(biāo)值是1 mid = 0; // 2 > 1 ? 這時(shí)候改變的是left left = mid + 1; // 這時(shí)候left = 1; 不會(huì)再做第三次運(yùn)算了,因?yàn)檠h(huán)條件已經(jīng)不滿足了,現(xiàn)在值是 1 > 1 了 這時(shí)候開始進(jìn)行下一步,值移動(dòng) int n = start - left; // n = 3 - 1 =2 表示要移動(dòng)2個(gè)值 switch (n) { case 2: a[left + 2] = a[left + 1]; case 1: a[left + 1] = a[left]; break; default: System.arraycopy(a, left, a, left + 1, n); } // 最后將運(yùn)算的值,填充的合適的區(qū)間內(nèi) a[left] = pivot;這時(shí)候我們看到的"大概"流程:
- 7 移動(dòng)到2的位置
- 5移動(dòng)到7的位置
-
5的位置由pivot代替,開始循環(huán)的變量值,不懂可以去看上面的代碼
image.png
然后開始下一個(gè)值的輪詢,一直到B組中的數(shù)據(jù)全部在A中找到對(duì)應(yīng)的區(qū)間,完成排序.
總結(jié)
- ArrayList中的sort排序是采用歸并排序的。
[一個(gè)數(shù)組的值的趨勢(shì)(增長或者減少)打斷的地方開始劃分] - 當(dāng)數(shù)組中的數(shù)據(jù)非常大的時(shí)候,會(huì)采用幾次歸并來完成排序.具體采用幾次歸并是minRunLength(nRemaining);方法去計(jì)算的.
