排序入口
// 1. List 原地排序
Collections.sort(list); // 需元素實現 Comparable
Collections.sort(list, comparator); // 外部 Comparator
// 2. 陣列排序
Arrays.sort(array);
Arrays.sort(array, comparator);
// 3. Java 8+ Stream 排序（非原地，產生新流）
list.stream().sorted().collect(toList());
list.stream().sorted(comparator).collect(toList());
核心契約
| 介面 | 方法 | 返回值語義 | 適用場景 |
|---|
Comparable<T> | int compareTo(T o) | 負/零/正：this < / = / > o | 類的「自然順序」，內部實現 |
Comparator<T> | int compare(T o1, T o2) | 負/零/正：o1 < / = / > o2 | 外部定制順序，多種排序策略 |
實戰：自定義類多條件排序
class User implements Comparable {
String name; int age;
@Override
public int compareTo(User o) {
int nameCmp = this.name.compareTo(o.name); // 主鍵：姓名升序
if (nameCmp != 0) return nameCmp;
return Integer.compare(this.age, o.age); // 次鍵：年齡升序
}
}
// 使用
List users = ...;
Collections.sort(users); // 直接用自然順序
Comparator 靈活定制（Java 8+ 鏈式 API）
// 同類不同序：姓名降序，年齡升序
Comparator cmp = Comparator
.comparing(User::getName, Comparator.reverseOrder())
.thenComparing(User::getAge);
Collections.sort(users, cmp);
// 或
users.sort(cmp); // List.default method
底層演算法演進
| JDK 版本 | Collections.sort | Arrays.sort (Object[]) | Arrays.sort (Primitive[]) |
|---|
| ≤ 6 | MergeSort | MergeSort | QuickSort (雙樞軸) |
| 7 | TimSort | TimSort | Dual-Pivot QuickSort |
| 8+ | TimSort | TimSort | Dual-Pivot QuickSort |
TimSort 核心特點
- 混合 MergeSort + InsertionSort
- 利用數據中已有「有序段」
- 穩定排序、最壞 O(n log n)、最好 O(n)（近乎有序）
- 需額外 O(n) 空間（合併暫存陣列）
Primitive 陣列用 QuickSort 原因
- 無穩定性要求（基本類型無身份）
- 原地排序，空間 O(log n) 棧深度
- 雙樞軸優化分區效率
效能對比（100 萬隨機整數）
Arrays.sort(int[]) : ~180 ms (Dual-Pivot QuickSort)
Arrays.sort(Integer[]) : ~320 ms (TimSort + 裝箱/拆箱)
Collections.sort(List) : ~340 ms (轉陣列 + TimSort + 回寫)
List.stream().sorted() : ~360 ms (Stream 管道開銷)
避坑與最佳實踐
- compareTo 一致性：
x.compareTo(y) == 0 應隱含 x.equals(y) == true（TreeSet/Map 依賴）
- 避免減法溢出：
return this.id - o.id ❌ → return Integer.compare(this.id, o.id) ✅
- 空值處理：
Comparator.nullsFirst() / nullsLast()
- 並行排序：
Arrays.parallelSort(largeArray) 多核加速
- 不可變集合：
List.copyOf(list).sort(...) 避免副作用
總結
Java 排序體系設計優雅：Comparable 定義自然序，Comparator 靈活定制序，TimSort 保證穩定高效。掌握鏈式 Comparator API 與底層演算法特性，能在效能與可讀性間做最佳權衡。
