---

前言

在Java中，Arrays.sort()是開發者最常用的排序方法之一。但你是否思考過它的底層實現？本文將基于OpenJDK 17源碼，深入分析其使用的排序算法和優化策略，涵蓋基本類型與對象數組的不同實現。

---

一、基本類型數組：雙軸快速排序

源碼路徑：java.util.DualPivotQuicksort

核心算法：
對于int[]、long[]等基本類型，Java使用雙軸快速排序（自Java 7引入），其核心思想是：

1. 選擇兩個軸（Pivot）將數組分為三部分：
   • 左段：< P1
   • 中段：P1 ≤ & ≤ P2
   • 右段：> P2
2. 遞歸排序三個子段

關鍵優化策略

1. 小數組插入排序：當數組長度 < 47 時，切換為插入排序

if (length < INSERTION_SORT_THRESHOLD) {insertionSort(a, low, high);return;
}

2. 五取樣法選擇軸元素：通過取5個等距位置的元素，用中位數法確定雙軸

int e1 = a[k], e5 = a[n]; // 等距取5個點
// ... 中位數計算確保P1<P2

3. 三向切分處理重復元素：分區時采用三向切分，高效處理重復值

while (k <= great) {if (ak < pivot1) { // 左段swap(a, k, left++);} else if (ak > pivot2) { // 右段while (a[great] > pivot2 && k < great) great--;swap(a, k, great--);}// 中段無需交換
}

4. 大數組歸并排序兜底：當遞歸深度超過log2(n) × 2時，切換為歸并排序避免最壞情況

if (depth == 0) {heapSort(a, low, high); // 實際是歸并排序return;
}

二、對象數組：TimSort

TimSort 是一種自適應的混合排序算法，通過智能識別和擴展數組中的自然有序片段（Run），結合二分插入排序優化小段數據、歸并排序平衡合并有序段，并利用Galloping Mode加速歸并過程，從而在各類現實數據（尤其是部分有序或包含重復值的數據集）上實現高效穩定的排序，其時間復雜度為O(n log n)，在最佳情況下可接近O(n)。

源碼路徑：java.util.TimSort
核心算法：
對象數組（如String[]）使用TimSort，這是一種混合排序：

• 歸并排序為框架
• 插入排序處理小片段

關鍵優化策略

1. 分段（Run）檢測：掃描數組，將自然有序片段（升序或嚴格降序）作為基礎單元

int runLen = countRunAndMakeAscending(a, lo, hi);

2. 動態最小Run長度：根據數組大小動態計算最小Run長度（16~32），確保后續歸并效率。

int minRun = minRunLength(nRemaining);

3. 二分插入排序擴展Run：若自然Run長度不足，用二分插入排序擴展到minRun。

binarySort(a, lo, hi, lo + initRunLen);

4. 歸并棧（Stack）管理：維護待歸并Run的棧，確保棧內Run長度滿足。
   stack[n-2] > stack[n-1] + stack[n]
   stack[n-1] > stack[n]

while (stackSize > 1) {int n = stackSize - 2;if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {mergeAt(n); // 歸并相鄰Run}
}

5. 高效內存利用
   • 歸并時復制小Run到臨時數組（避免大數組復制）
   • Galloping Mode：當一方連續勝出時，指數搜索加速歸并

三、性能對比總結

數組類型	算法	時間復雜度	優化重點
基本類型	雙軸快速排序	平均O(n log n)	小數組插入、三向切分
對象數組	TimSort	最差O(n log n)	自然Run利用、歸并棧

---

總結

Java的Arrays.sort()通過精妙的算法選擇和工程優化，實現了：

• 基本類型：雙軸快排為主，插入/歸并兜底
• 對象數組：TimSort最大化利用數據特性

這些設計使其在各類場景下保持高性能，成為Java集合框架的基石。