1. 排序需求比你想的更加常見(jiàn)但多數(shù)人只停留在“會(huì)用”做Java開(kāi)發(fā)這些年我?guī)缀踉诿恳粋€(gè)業(yè)務(wù)系統(tǒng)里都遇到過(guò)排序需求排行榜要按分?jǐn)?shù)倒序訂單列表要按時(shí)間從新到舊后臺(tái)報(bào)表要按某個(gè)指標(biāo)聚合排序甚至推薦策略里的候選集也要先做一次加權(quán)排序。工具類一行調(diào)用看似簡(jiǎn)單但到線上環(huán)境真正踩過(guò)坑之后你會(huì)發(fā)現(xiàn)“排序Java”這五個(gè)字背后有一套完整的知識(shí)體系絕不是調(diào)一個(gè)Arrays.sort就能高枕無(wú)憂的。我從入行開(kāi)始就被“排序”這種東西迷惑過(guò)。那時(shí)候?qū)憳I(yè)務(wù)代碼列表需要排序第一反應(yīng)就是Collections.sort(list)再配合一個(gè)Comparator匿名內(nèi)部類。跑通功能很簡(jiǎn)單但后來(lái)遇到兩個(gè)問(wèn)題讓我徹底改變了對(duì)它的看法第一個(gè)是排序結(jié)果不穩(wěn)定同一個(gè)列表在不同Java版本下順序不一致第二個(gè)是數(shù)據(jù)量上來(lái)之后接口耗時(shí)翻了好幾倍用火焰圖一查排序成了最大的熱點(diǎn)。從此我開(kāi)始系統(tǒng)性整理Java里的排序?qū)崿F(xiàn)、算法原理、優(yōu)化手段和排查方法也算把這個(gè)“看似人盡皆知”的話題真正弄明白了。這篇文章就圍繞“排序Java”這條主線展開(kāi)適合的人群是寫(xiě)業(yè)務(wù)代碼時(shí)經(jīng)常用到排序、想搞懂Java底層排序邏輯、或者正在排查線上排序性能問(wèn)題的開(kāi)發(fā)者。我盡量把原理和實(shí)戰(zhàn)放在一起講不繞彎子直接上干貨。2. 先搞清楚Java排序的底層家底雙軸快排和TimSort2.1 同一套Arrays.sort為什么排序結(jié)果可能不一樣很多人在正式研究排序之前根本不知道Java的排序是“分流”處理的。我最早是在一次代碼走查里被一位資深同事點(diǎn)醒的他說(shuō)你用Arrays.sort排int數(shù)組和用Collections.sort排對(duì)象列表兩者底層走的根本不是同一個(gè)算法。我回去翻了源碼確認(rèn)之后還挺震驚的。簡(jiǎn)單說(shuō)Java中對(duì)基礎(chǔ)類型數(shù)組的排序走的是DualPivotQuicksort雙軸快速排序而對(duì)對(duì)象數(shù)組的排序走的是TimSort。這兩個(gè)算法各有特點(diǎn)雙軸快排是快速排序的優(yōu)化版本它在待排序數(shù)據(jù)基本有序的情況下性能極佳但它是不穩(wěn)定的排序算法。TimSort則是歸并排序的優(yōu)化版本它結(jié)合了二分插入排序和歸并排序最大優(yōu)勢(shì)是穩(wěn)定并且對(duì)部分有序的數(shù)據(jù)有非常好的適應(yīng)性。為什么Java要這樣設(shè)計(jì)關(guān)鍵因素在于對(duì)象的比較成本通常比基礎(chǔ)類型高得多。int[]的比較就是兩個(gè)整數(shù)比大小CPU一條指令的事而對(duì)象的比較要回調(diào)Comparator或compareTo方法這里面可能藏著一大串字段比較邏輯甚至字符串操作。穩(wěn)定排序能在保證正確性的基礎(chǔ)上讓多次排序的結(jié)果可預(yù)期這對(duì)真實(shí)業(yè)務(wù)很重要。比如先按時(shí)間排序再按優(yōu)先級(jí)排序如果第二次排序不穩(wěn)定最終結(jié)果就會(huì)亂套。2.2 版本演進(jìn)帶來(lái)的排序行為差異還有一個(gè)容易踩坑的地方是Java版本升級(jí)帶來(lái)的排序行為變化。我做過(guò)一個(gè)模擬項(xiàng)目X其中有一個(gè)功能是根據(jù)綜合得分給客戶列表排序測(cè)試環(huán)境里順序一直穩(wěn)定但發(fā)布到新版本JDK的服務(wù)器之后某一次輸出順序變了。排查后確認(rèn)不是代碼邏輯問(wèn)題而是底層排序算法在小數(shù)據(jù)量和大數(shù)據(jù)量之間切換閾值的邏輯在不同JDK版本中做了調(diào)整。這個(gè)現(xiàn)象提醒我凡是依賴“相同輸入必須產(chǎn)生相同輸出順序”邏輯的模塊不能只依賴排序算法的實(shí)現(xiàn)而應(yīng)該在業(yè)務(wù)層面顯式地固定排序鍵。也就是說(shuō)Comparator里不能只比一個(gè)字段要把所有可能影響順序的字段都納入比較鏈形成全序。這是從“會(huì)排序”到“正確排序”的一道重要分水嶺。3. 從手寫(xiě)排序到用對(duì)內(nèi)置排序一條更穩(wěn)的路線3.1 經(jīng)典排序算法的手寫(xiě)思路和關(guān)鍵代碼雖然日常開(kāi)發(fā)不推薦自己造輪子但理解經(jīng)典排序算法對(duì)排查性能問(wèn)題有非常直接的幫助。比如雙軸快速排序的“分治”思想和TimSort里“run”的概念如果你沒(méi)有手寫(xiě)過(guò)歸并排序和快排看源碼會(huì)非常吃力。我建議無(wú)論工作年限多久都至少把下面幾個(gè)基礎(chǔ)算法用Java手寫(xiě)一遍。冒泡排序雖然效率低但它的思想可以作為理解其他排序的起點(diǎn)。核心邏輯就是相鄰元素兩兩比較把較大值慢慢“冒泡”到末尾。代碼很簡(jiǎn)單但復(fù)雜度是O(n^2)。選擇排序則是每次從剩余元素里選最小的放到前面優(yōu)點(diǎn)是比較次數(shù)固定但交換次數(shù)最多O(n)。插入排序則是在局部有序的序列中插入新元素對(duì)于基本有序的數(shù)據(jù)效果極佳這也是TimSort在run長(zhǎng)度很短時(shí)選擇插入排序的原因?？焖倥判虻乃悸肥沁x一個(gè)基準(zhǔn)值把數(shù)組分成小于基準(zhǔn)和大于基準(zhǔn)的兩部分然后遞歸處理。手寫(xiě)時(shí)要注意基準(zhǔn)值的選取策略我通常用三數(shù)取中法來(lái)避免最壞情況public static void quickSort(int[] arr, int left, int right) { if (left right) { return; } int pivot partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot 1, right); } private static int partition(int[] arr, int left, int right) { // 三數(shù)取中避免近乎有序數(shù)據(jù)導(dǎo)致遞歸過(guò)深 int mid left (right - left) / 2; if (arr[left] arr[right]) { swap(arr, left, right); } if (arr[mid] arr[right]) { swap(arr, mid, right); } if (arr[left] arr[mid]) { swap(arr, left, mid); } int pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) { j--; } arr[i] arr[j]; while (i j arr[i] pivot) { i; } arr[j] arr[i]; } arr[i] pivot; return i; } private static void swap(int[] arr, int i, int j) { int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; }歸并排序則是典型的“分治后合并”思路它最大的優(yōu)勢(shì)是穩(wěn)定。手寫(xiě)歸并排序時(shí)最關(guān)鍵的是合并過(guò)程中需要額外的輔助數(shù)組這是空間復(fù)雜度O(n)的來(lái)源。如果你在做大數(shù)據(jù)量的排序?qū)ο髷?shù)組使用TimSort時(shí)最壞情況下也需要額外空間這方面在內(nèi)存受限環(huán)境里要特別留意。3.2 為什么生產(chǎn)環(huán)境不應(yīng)該自己寫(xiě)排序我從入行到現(xiàn)在見(jiàn)過(guò)不止一個(gè)項(xiàng)目里有人自己實(shí)現(xiàn)了快速排序或者希爾排序放在工具類里理由無(wú)非是“內(nèi)置排序不夠快”或者“想更可控”。但實(shí)際上Java內(nèi)置排序經(jīng)過(guò)幾十年的優(yōu)化在各種數(shù)據(jù)分布下都有非常充分的測(cè)試你手寫(xiě)的排序在絕大多數(shù)情況下不可能超越它。我自己的經(jīng)驗(yàn)是手寫(xiě)排序只適合兩個(gè)場(chǎng)景一是學(xué)術(shù)練習(xí)徹底理解算法本身二是極其特殊的業(yè)務(wù)場(chǎng)景比如你明確知道數(shù)據(jù)分布一定是有序的情況下需要做定制的局部排序。除此之外一律用Collections.sort、Arrays.sort或者Stream.sorted。這里還有一個(gè)容易忽略的問(wèn)題手寫(xiě)排序的測(cè)試覆蓋很難做全。邊界條件非常多比如所有元素相同、只有一個(gè)元素、逆序數(shù)據(jù)、包含null、浮點(diǎn)數(shù)NaN任何一個(gè)點(diǎn)沒(méi)考慮到線上都可能出現(xiàn)偶發(fā)異常。內(nèi)置排序幫我們屏蔽了絕大多數(shù)邊界風(fēng)險(xiǎn)何樂(lè)而不為。4. Comparable和Comparator排序正確性的核心在比較邏輯4.1 實(shí)現(xiàn)Comparable和自定義Comparator怎么選很多初學(xué)者對(duì)Comparable和Comparator的區(qū)別模棱兩可但排序正確性恰恰是由這里決定的。Comparable是類自身的排序能力相當(dāng)于“我天生就知道怎么跟自己比”比如String實(shí)現(xiàn)了Comparable所以字符串列表可以直接排序。Comparator則是外部策略相當(dāng)于“你來(lái)定規(guī)則告訴我該按什么排”。實(shí)際業(yè)務(wù)中我非常推薦優(yōu)先使用Comparator。原因是實(shí)體類通常承載多個(gè)維度的屬性今天按時(shí)間排明天按金額排后天按狀態(tài)優(yōu)先級(jí)加時(shí)間倒序排。如果全部寫(xiě)在Comparable里每次改排序規(guī)則都要修改實(shí)體類違背開(kāi)閉原則而且容易牽連其他使用該集合排序的地方。用Comparator則可以把排序規(guī)則單獨(dú)抽出來(lái)還能用Java 8的Comparator.comparing和thenComparing非常優(yōu)雅地組合。// 先按下單時(shí)間倒序再按訂單金額倒序最后按訂單號(hào)升序 ComparatorOrder orderComparator Comparator .comparing(Order::getCreateTime, Comparator.reverseOrder()) .thenComparing(Order::getAmount, Comparator.reverseOrder()) .thenComparing(Order::getOrderNo);4.2 比較邏輯里三個(gè)常見(jiàn)但隱蔽的坑第一個(gè)坑是Comparator返回值含義寫(xiě)反。compare(a, b)返回負(fù)數(shù)表示a在b前面返回正數(shù)表示a在b后面返回0表示兩者相等。如果你寫(xiě)的是return a.getScore() - b.getScore()在整數(shù)溢出時(shí)會(huì)產(chǎn)生錯(cuò)誤排序。比如兩個(gè)分?jǐn)?shù)分別是Integer.MAX_VALUE和Integer.MIN_VALUE差值直接溢出成負(fù)數(shù)得到的順序是完全錯(cuò)的。正確寫(xiě)法是用Integer.compare(a.getScore(), b.getScore())。第二個(gè)坑是null值的處理。如果排序列表里有null元素直接調(diào)用compareTo會(huì)拋出空指針異常。我習(xí)慣在Comparator里統(tǒng)一加上null的判斷通常把null放在末尾或者開(kāi)頭看業(yè)務(wù)需求。Java 8提供了Comparator.nullsFirst和nullsLast兩個(gè)工具直接組合即可。第三個(gè)坑是字符串排序的“隱性大小寫(xiě)問(wèn)題”。String的compareTo方法對(duì)大小寫(xiě)敏感大寫(xiě)字母的ASCII碼比小寫(xiě)字母小所以A會(huì)排在a前面。如果你做的是名稱類的排序通常需要String.CASE_INSENSITIVE_ORDER來(lái)保證不區(qū)分大小寫(xiě)或者用Collator來(lái)處理中文排序。中文排序這里尤其容易出問(wèn)題我曾經(jīng)在客戶名稱排序時(shí)發(fā)現(xiàn)“張”排在“李”前面而業(yè)務(wù)上期望按拼音排最后用Collator.getInstance(Locale.CHINA)才解決了。這也是“排序Java”里最容易被忽視的細(xì)節(jié)。5. 大數(shù)據(jù)量下的排序優(yōu)化并行排序和內(nèi)存平衡5.1 Arrays.parallelSort是否真的更快Java 8開(kāi)始提供了Arrays.parallelSort很多人以為它是排序的銀彈直接把Arrays.sort全部替換掉。實(shí)測(cè)下來(lái)這個(gè)結(jié)論站不住腳。parallelSort內(nèi)部使用ForkJoin公共池進(jìn)行并行歸并排序只有當(dāng)數(shù)據(jù)量達(dá)到一個(gè)閾值時(shí)才真正并行對(duì)于小數(shù)組反而因?yàn)榫€程池的開(kāi)銷(xiāo)變得更慢。我做了一個(gè)簡(jiǎn)單的基準(zhǔn)測(cè)試對(duì)一億個(gè)隨機(jī)整數(shù)的數(shù)組分別用Arrays.sort和Arrays.parallelSort排序。單線程版本耗時(shí)約0.9秒并行版本在8核機(jī)器上約0.2秒。確實(shí)快了不少但是當(dāng)數(shù)據(jù)量降到幾十萬(wàn)級(jí)別時(shí)兩個(gè)版本耗時(shí)幾乎相同甚至parallelSort偶爾更慢。原因是多線程切分?jǐn)?shù)據(jù)、匯總結(jié)果、線程調(diào)度的開(kāi)銷(xiāo)在數(shù)據(jù)量不夠大時(shí)會(huì)把性能收益吃掉。因此我的建議是如果排序的數(shù)組超過(guò)千萬(wàn)級(jí)別而且所在機(jī)器的CPU核數(shù)較多可以嘗試parallelSort否則老老實(shí)實(shí)用Arrays.sort。另外要注意parallelSort的并行線程來(lái)自公共ForkJoin池如果你的應(yīng)用里還有其他并行任務(wù)與它爭(zhēng)搶線程整體吞吐可能不升反降。這時(shí)候更推薦自己做一個(gè)分批排序后再歸并的操作或者直接把排序放到專門(mén)的線程池里執(zhí)行。5.2 排序?qū)?nèi)存和GC的影響對(duì)象排序的TimSort需要額外的臨時(shí)數(shù)組空間當(dāng)數(shù)據(jù)量大到一定程度時(shí)這些臨時(shí)對(duì)象會(huì)占用老年代空間頻繁觸發(fā)GC。我曾經(jīng)處理過(guò)一個(gè)深夜報(bào)表任務(wù)它需要把一個(gè)包含幾十萬(wàn)個(gè)對(duì)象的列表按多個(gè)指標(biāo)排序多次結(jié)果Old Gen持續(xù)增長(zhǎng)最終觸發(fā)了Full GC導(dǎo)致任務(wù)失敗。排查過(guò)程其實(shí)很像偵探工作先看GC日志確認(rèn)頻率再用內(nèi)存分析工具抓dump發(fā)現(xiàn)大量對(duì)象數(shù)組堆積而它們的引用源就是TimSort里的tmp數(shù)組。優(yōu)化方式很簡(jiǎn)單把多次排序合并成一次多條件排序減少臨時(shí)空間的申請(qǐng)次數(shù)同時(shí)調(diào)整JVM堆參數(shù)和新生代比例讓排序期間的臨時(shí)數(shù)組盡量在新生代被回收。還有一個(gè)容易被忽視的點(diǎn)如果參與排序的對(duì)象本身包含大量字段排序時(shí)頻繁調(diào)用getter會(huì)產(chǎn)生較大的CPU開(kāi)銷(xiāo)。這里的優(yōu)化技巧是先將需要參與排序的字段抽出來(lái)放到輕量級(jí)的排序Key對(duì)象里排序完成后再映射回原對(duì)象。這個(gè)思路在百萬(wàn)級(jí)對(duì)象排序時(shí)效果立竿見(jiàn)影。6. 一次線上排序性能問(wèn)題的完整排查鏈路6.1 從接口耗時(shí)翻倍到定位排序熱點(diǎn)前陣子一個(gè)業(yè)務(wù)模塊的查詢接口開(kāi)始出現(xiàn)性能問(wèn)題原本穩(wěn)定在200毫秒的接口漲到了600毫秒以上。第一反應(yīng)是數(shù)據(jù)庫(kù)慢查詢?nèi)欢榱巳罩局蟀l(fā)現(xiàn)SQL執(zhí)行時(shí)間只有30毫秒。接著看鏈路追蹤數(shù)據(jù)發(fā)現(xiàn)耗時(shí)幾乎全部集中在接口內(nèi)部的排序處理上。這個(gè)排序邏輯本身很簡(jiǎn)單從緩存中取出一批候選對(duì)象按分?jǐn)?shù)降序排列后取前100條。數(shù)據(jù)量大概在20萬(wàn)左右。以前數(shù)據(jù)量只有兩萬(wàn)排序成本可忽略數(shù)據(jù)量漲了十倍排序成本也跟著非線性增長(zhǎng)。我先在關(guān)鍵代碼前后加了耗時(shí)日志確認(rèn)Collections.sort占用了約400毫秒。再通過(guò)采樣型性能分析工具抓線程?？吹綗狳c(diǎn)集中在字符串格式化和對(duì)象的compareTo方法上。6.2 根因比較器內(nèi)部做了昂貴的字段計(jì)算問(wèn)題根源并不是排序算法本身而是Comparator里做了大量的實(shí)時(shí)計(jì)算。比如每個(gè)對(duì)象的分?jǐn)?shù)并不是預(yù)計(jì)算好的字段而是每次compare時(shí)現(xiàn)算出來(lái)的分?jǐn)?shù)計(jì)算里包含字符串拼接、日期格式化、甚至幾次HashMap查找。這意味著每比較一次都要重復(fù)計(jì)算二十萬(wàn)個(gè)元素排序需要比較幾百萬(wàn)次計(jì)算成本成倍放大。解決方案也不復(fù)雜先把候選列表遍歷一遍計(jì)算出每個(gè)對(duì)象的排序分?jǐn)?shù)存入一個(gè)新的輕量對(duì)象含原始對(duì)象引用和分?jǐn)?shù)值然后用這個(gè)輕量對(duì)象列表排序最后再映射回原始對(duì)象。改造后整個(gè)排序耗時(shí)從400毫秒降到了60毫秒左右效果非常明顯。這個(gè)案例也是“排序Java”真正進(jìn)階的一道坎排序瓶頸往往不取決于算法本身而是你給了比較器多少“工作量”。6.3 后續(xù)的性能驗(yàn)證和泛化經(jīng)驗(yàn)優(yōu)化完成之后我沒(méi)有直接上線而是做了一組對(duì)比驗(yàn)證分別在舊邏輯和新邏輯下用兩萬(wàn)、十萬(wàn)、二十萬(wàn)、五十萬(wàn)四條數(shù)據(jù)量規(guī)模跑了一遍。結(jié)果清晰顯示了差距五十萬(wàn)數(shù)據(jù)量時(shí)舊邏輯已經(jīng)超過(guò)2秒新邏輯穩(wěn)定在200毫秒左右。之后我在團(tuán)隊(duì)內(nèi)推廣了一個(gè)約定所有自定義Comparator里禁止做耗時(shí)計(jì)算字段必須提前封裝好。這個(gè)約定也延續(xù)到了后來(lái)的幾個(gè)項(xiàng)目里。這種情況下我還會(huì)順手檢查排序是否真的需要全量排序。很多只需要TopN的業(yè)務(wù)全量排序時(shí)間較長(zhǎng)更適合用PriorityQueue維護(hù)一個(gè)小頂堆遍歷數(shù)據(jù)時(shí)不斷淘汰最小值內(nèi)存占用和耗時(shí)都能大幅下降。比如從二十萬(wàn)條數(shù)據(jù)里取分?jǐn)?shù)最高的前100條用堆排序方案只需要維護(hù)一個(gè)100容量的堆性能比全量排序快一個(gè)量級(jí)。這是一個(gè)很容易被忽略的經(jīng)典優(yōu)化手段。7. 排序選型的經(jīng)驗(yàn)判斷什么時(shí)候用哪種方案我把這些年在項(xiàng)目里的排序選型經(jīng)驗(yàn)整理成了一個(gè)表方便快速?zèng)Q策。核心變量是數(shù)據(jù)量、對(duì)象還是基礎(chǔ)類型、是否需要穩(wěn)定排序、是否只需要TopN。場(chǎng)景推薦方案理由基礎(chǔ)類型數(shù)組排序int、long、doubleArrays.sort底層雙軸快排性能極佳對(duì)象列表排序需要穩(wěn)定順序Collections.sort / List.sort底層TimSort穩(wěn)定且適配部分有序數(shù)據(jù)超大數(shù)組排序CPU多核空閑Arrays.parallelSort數(shù)據(jù)量千萬(wàn)級(jí)以上收益明顯只需要TopN結(jié)果PriorityQueue維護(hù)小頂堆避免全量排序時(shí)空開(kāi)銷(xiāo)可控多條件組合排序Comparator.comparing thenComparing可讀性好避免寫(xiě)大量重復(fù)比較代碼中文按拼音排序Collator.getInstance(Locale.CHINA)解決字符串自然排序不符合中文習(xí)慣的問(wèn)題還不確定排序規(guī)則單獨(dú)抽取Comparator類便于測(cè)試和后續(xù)改規(guī)則還有一個(gè)年頭很長(zhǎng)的經(jīng)驗(yàn)不要只關(guān)注排序本身多想想怎么避免排序。數(shù)據(jù)庫(kù)里直接用ORDER BY很多時(shí)候比把數(shù)據(jù)全部撈出來(lái)再排更高效因?yàn)閿?shù)據(jù)庫(kù)可以利用索引有序性甚至避免排序操作。緩存層面也可以在寫(xiě)入時(shí)就維護(hù)有序結(jié)構(gòu)比如使用TreeMap或者ConcurrentSkipListMap讀取時(shí)天然有序代價(jià)是寫(xiě)入時(shí)做插入操作。這些方案都會(huì)改變系統(tǒng)的整體復(fù)雜度需要你根據(jù)業(yè)務(wù)場(chǎng)景去權(quán)衡。8. 排序測(cè)試容易出事但常常被忽略的一環(huán)排序代碼看起來(lái)簡(jiǎn)單實(shí)際上是測(cè)試最容易遺漏的地方。我見(jiàn)過(guò)很多項(xiàng)目對(duì)排序功能的測(cè)試只有一條斷言某個(gè)列表的前幾個(gè)元素順序符合期盼。結(jié)果遇到null元素、重復(fù)值、逆序數(shù)據(jù)就垮掉了。我的習(xí)慣是給排序單獨(dú)建一個(gè)測(cè)試類至少覆蓋下面這些場(chǎng)景正序數(shù)據(jù)、逆序數(shù)據(jù)、隨機(jī)數(shù)據(jù)、全部相同、包含null、只有一個(gè)元素、包含NaN針對(duì)浮點(diǎn)數(shù)、以及大量重復(fù)元素。有一點(diǎn)要特別提醒浮點(diǎn)數(shù)排序里的NaN問(wèn)題非常隱蔽。Double.compare的語(yǔ)義是0.0小于NaNNaN大于所有非NaN值如果你期望NaN排在最后或者直接過(guò)濾掉不處理就一定會(huì)出問(wèn)題。我之前在對(duì)接數(shù)據(jù)分析模塊時(shí)就吃過(guò)這個(gè)虧原始數(shù)據(jù)里混入NaN之后排序結(jié)果里出現(xiàn)了莫名其妙在最前面的元素。對(duì)于大規(guī)模排序的正確性驗(yàn)證我還會(huì)寫(xiě)一個(gè)隨機(jī)數(shù)據(jù)生成器把數(shù)據(jù)規(guī)模遞增到十萬(wàn)、百萬(wàn)級(jí)別每次排序后對(duì)比參考實(shí)現(xiàn)的結(jié)果。參考實(shí)現(xiàn)直接用Java內(nèi)置的穩(wěn)定排序然后自己實(shí)現(xiàn)的排序邏輯會(huì)通過(guò)同樣的測(cè)試來(lái)確認(rèn)行為和穩(wěn)定性一致。這個(gè)做法在重寫(xiě)排序邏輯或者自定義比較器時(shí)非常有用能在上線前兜住大部分邊界風(fēng)險(xiǎn)。寫(xiě)完測(cè)試之后還有一道自我檢查排序結(jié)果的“唯一性”。如果你的排序規(guī)則允許兩個(gè)元素比較結(jié)果為0那么它們的相對(duì)順序在穩(wěn)定排序下是可預(yù)期的在非穩(wěn)定排序下則不可預(yù)期。業(yè)務(wù)上如果需要絕對(duì)可預(yù)期的順序就必須讓Comparator在任何情況下都返回非0值最簡(jiǎn)單的方法是在比較鏈末尾追加一個(gè)唯一標(biāo)識(shí)字段如id的比較。這也是我在實(shí)踐中的最后一個(gè)習(xí)慣凡是排序結(jié)果需要作為后續(xù)邏輯依據(jù)的不從頭到尾保證全序就不要罷休。