Java 排序大全：Arrays.sort、Collections.sort、Comparable 與 Comparator 完全指南

核心類別速查

• java.util.Arrays：陣列操作工具類（靜態方法）。
• java.util.Collections：集合操作工具類（靜態方法），注意與 Collection 介面區分。

基本型別與 String 陣列排序

int[] arr = {4, 1, 3, -23};
Arrays.sort(arr); // 升序：{-23, 1, 3, 4}

String[] strs = {"z", "a", "C"};
Arrays.sort(strs); // 自然順序：{"C", "a", "z"}
// 忽略大小寫
Arrays.sort(strs, String.CASE_INSENSITIVE_ORDER); // {"a", "C", "z"}
// 區間排序（含頭不含尾）
Arrays.sort(strs, 0, 2); // 僅排前兩個

降序排序

// 基本型別陣列無直接降序，需轉包裝型別或自行反轉
Integer[] arr = {4, 1, 3, -23};
Arrays.sort(arr, Comparator.reverseOrder()); // {4, 3, 1, -23}

// 或排序後反轉
List<Integer> list = Arrays.asList(arr);
Collections.reverse(list);

自訂物件排序：實作 Comparable

class Name implements Comparable<Name> {
    String firstName, lastName;
    // 建構子、getter、toString 省略
    @Override
    public int compareTo(Name o) {
        int cmp = lastName.compareTo(o.lastName);
        return (cmp != 0) ? cmp : firstName.compareTo(o.firstName);
    }
}

// 使用
Name[] names = { new Name("John","Lennon"), new Name("Karl","Marx"), ... };
Arrays.sort(names); // 依 lastName, firstName 升序

集合排序：Collections.sort

List<Integer> list = new LinkedList<>();
list.add(4); list.add(34); list.add(22); list.add(2);
Collections.sort(list); // [2, 4, 22, 34]
Collections.sort(list, Comparator.reverseOrder()); // 降序

策略模式：Comparator 客製化排序

不修改原類別，外部定義比較邏輯：

Comparator<Name> FIRST_NAME_ORDER = (n1, n2) -> {
    int cmp = n1.firstName.compareTo(n2.firstName);
    return (cmp != 0) ? cmp : n1.lastName.compareTo(n2.lastName);
};

List<Name> list = Arrays.asList(names);
Collections.sort(list, FIRST_NAME_ORDER); // 依 firstName 排序

Java 8+ Lambda 與 Stream 風格

// 陣列
Arrays.sort(names, Comparator.comparing(Name::getLastName).thenComparing(Name::getFirstName));

// 集合
list.sort(Comparator.comparing(Name::getFirstName));

// Stream 產生新排序串流
List<Name> sorted = list.stream()
    .sorted(Comparator.comparing(Name::getLastName))
    .collect(Collectors.toList());

效能與穩定性

• TimSort（JDK 7+）：混合歸併與插入排序，穩定排序，平均 O(n log n)，近乎已排序資料 O(n)。
• 基本型別陣列使用雙軸快速排序（不穩定），物件陣列/集合用 TimSort（穩定）。

常見坑點

1. compareTo 與 equals 不一致 → TreeSet/TreeMap 行為異常。
2. 減法溢位：return a - b 錯誤，應用 Integer.compare(a, b)。
3. Comparator 未處理 null → NPE，用 Comparator.nullsFirst() 處理。

排序看似基礎，比較器契約、穩定性、效能特性卻是進階面試必考。掌握 Comparator 組合式 API，讓排序邏輯像積木一樣靈活組合。