您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 程式設計入門

Java Arrays.sort() 深度解析：從源碼原理到生產級排序最佳實踐

編輯：Java 程式設計入門

前言：排序是程序的靈魂

java.util.Arrays.sort() 是 Java 開發者最高頻調用的庫方法之一。但許多開發者僅知「能排序」，不知雙軸快排、TimSort、基本類型 vs 引用類型分流、比較器契約、穩定性、性能陷阱。本文將基於 JDK 17/21 源碼，徹底講透排序實現、API 選型、避坑指南、效能調優。

1. 核心架構：基本類型走雙軸快排，引用類型走 TimSort

類型	算法	穩定性	時間複雜度	空間複雜度	JDK 版本演進
基本類型 (int[], double[]...)	Dual-Pivot Quicksort (雙軸快排)	不穩定	平均 O(n log n) 最壞 O(n²)	O(log n) 棧	JDK 7 引入，替換單軸快排
引用類型 (Object[], T[])	TimSort (合併插入混合)	穩定	O(n log n)	O(n) 輔助陣列	JDK 7 引入，替換合併排序

為什麼分流？

基本類型：無身份、不可變、比較極快 → 激進優化（雙軸、原地分區、避免物件分配）
引用類型：有身份、可變、比較較慢、需穩定性（保持相等元素相對序） → TimSort 利用現有有序片段

2. 雙軸快排核心原理

傳統單軸快排：選一個 pivot，分區為 < pivot 和 > pivot。

雙軸快排：選兩個 pivot P1 < P2，分區為三段：

[ < P1 ] [ P1 ≤ x ≤ P2 ] [ > P2 ]
  ↑          ↑              ↑
 left       center         right

減少遞歸深度，提升緩存命中率
對重複鍵值數據極其友好（中間區直接歸類）
閾值 < 44 用插入排序，< 286 用雙軸快排，≥ 286 並行排序

3. TimSort 核心原理

源自 Python，結合歸併排序與插入排序：

掃描陣列識別 Run（自然有序片段）
短 Run 用二分插入排序延長至 minRun (32-64)
將 Run 壓入棧，按合併不變式合併：run[n-2] > run[n-1] + run[n] 且 run[n-1] > run[n]
合併時用 galloping mode（指數搜索）加速

穩定性保證：合併時左 Run 元素優先，相等不交換位置。

4. API 全景與選型指南


// 基本類型：僅升序，無 Comparator 重載
Arrays.sort(int[] a)
Arrays.sort(int[] a, int fromIndex, int toIndex) // 區間排序
Arrays.parallelSort(int[] a) // JDK 8+ 並行排序，大數據量顯著加速

// 引用類型：天然支援 Comparator
Arrays.sort(Object[] a)
Arrays.sort(T[] a, Comparator c)
Arrays.sort(T[] a, int fromIndex, int toIndex, Comparator c)
Arrays.parallelSort(T[] a, Comparator c)

基本類型降序排序三種方案對比

方案	代碼	優點	缺點
包裝類 + Comparator	`Arrays.sort(boxedArray, Collections.reverseOrder())`	語義清晰	自動裝箱/拆箱開銷大，內存佔用高
升序後反轉	`Arrays.sort(arr); reverse(arr);`	零額外內存，極快	需額外 O(n) 反轉步驟
自定義快排	複製源碼改比較邏輯	單遍歷完成	維護成本高，易出錯

推薦：升序後反轉，代碼簡潔、效能最優：


public static void sortDesc(int[] arr) {
    Arrays.sort(arr);
    for (int i = 0, j = arr.length - 1; i < j; i++, j--) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

5. Comparator 契約與常見違規


// 錯誤：違反傳遞性
Comparator bad = (u1, u2) -> u1.getAge() - u2.getAge(); // 整數溢出風險！
// 正確：
Comparator good = Comparator.comparingInt(User::getAge);
// 或
Comparator good = (u1, u2) -> Integer.compare(u1.getAge(), u2.getAge());

契約	要求	違規後果
自反性	`compare(x, x) == 0`	拋出 IllegalArgumentException
反對稱性	`sign(compare(x,y)) == -sign(compare(y,x))`	排序結果不可預測、死循環
傳遞性	`compare(x,y)>0 && compare(y,z)>0 → compare(x,z)>0`	TimSort 合併階段拋出異常
一致性	`compare(x,y)==0 → equals(x,y)` (建議)	TreeSet/TreeMap 行為異常

6. 並行排序：Arrays.parallelSort()

JDK 8 引入，ForkJoinPool 共用池
閾值：基本類型 ≥ 8192，引用類型 ≥ 8192
大數據量 (10⁶+) 速度提升 2-4 倍（視 CPU 核心數）
小數據量開銷大於收益，請勿濫用

7. 避坑實錄

坑 1：基本類型數組無法直接降序


// 編譯錯誤：無 Comparator 重載
// Arrays.sort(intArray, Comparator.reverseOrder());

坑 2：Comparator 返回 `a - b` 整數溢出


// 錯誤：Integer.MAX_VALUE - (-1) 溢出為負
// 正確：
Integer.compare(a, b)  // JDK 7+
Comparator.comparingInt(...)

坑 3：排序後原數組被修改（副作用）


int[] original = {3,1,2};
int[] copy = original.clone(); // 或 Arrays.copyOf(original, original.length)
Arrays.sort(copy);
// original 保持不變

坑 4：null 元素導致 NPE


String[] arr = {"b", null, "a"};
Arrays.sort(arr); // NPE
// 解決：
Arrays.sort(arr, Comparator.nullsFirst(Comparator.naturalOrder()));
// 或
Arrays.sort(arr, (a,b) -> a==null ? (b==null?0:-1) : (b==null?1:a.compareTo(b)));

坑 5：自定義對象未實現 Comparable 卻調用無參 sort


class User { String name; } // 未實現 Comparable
User[] users = ...;
Arrays.sort(users); // ClassCastException
// 解決：實現 Comparable 或傳入 Comparator

8. 效能基準測試參考 (JDK 21, 1000萬 int)

方法	隨機數據	有序數據	逆序數據	重複度高
Arrays.sort	~1.2s	~0.15s	~0.18s	~0.08s
Arrays.parallelSort	~0.35s	~0.12s	~0.14s	~0.06s
Collections.sort (List)	~1.5s	~0.2s	~0.25s	~0.1s

9. 總結：生產級排序決策樹

需要排序？
├─ 基本類型？
│   ├─ 升序 → Arrays.sort / parallelSort(大數據)
│   └─ 降序 → Arrays.sort + 反轉
└─ 引用類型？
    ├─ 自然序 (實現 Comparable) → Arrays.sort
    ├─ 自定義序 → Arrays.sort(array, comparator)
    ├─ 多條件 → Comparator.comparing().thenComparing()
    ├─ 含 null → Comparator.nullsFirst/Last()
    ├─ 大數據 (＞100萬) → parallelSort
    └─ 需保持原數組 → copyOf 後排序

掌握 Arrays.sort 的算法分流邏輯、Comparator 契約、基本類型降序技巧、並行排序閾值、null 安全處理，即可在面試、調優、架構設計中游刃有餘。