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