在 Java 中，Comparable 和 Comparator 是用于對象排序的重要接口。它們提供了不同的排序方式，適用于不同的需求，同時在 Java 底層排序算法中發揮著關鍵作用。本文將從基礎概念、使用方法、排序實現（包括升序、降序）、底層實現原理以及適用場景等方面進行詳細解析。

---

一、?Comparable 和 Comparator 的基本概念

在 Java 中，排序通常用于 數組 和 集合（List），兩者的排序分別由 Arrays.sort() 和 Collections.sort() 進行，而這兩個方法都依賴于 Comparable 和 Comparator。

1.1 Comparable 接口（自然排序）

• Comparable 是一個 內部比較器，表示對象本身支持排序規則。

• 需要在類中實現 compareTo() 方法，定義默認的排序方式。

• 適用于對象有唯一的自然排序方式，如 Integer、String、Double 等。

代碼示例（按照 age 升序排序）：

class Person implements Comparable<Person> {private String name;private int age;public Person(String name, int age) {this.name = name;this.age = age;}@Overridepublic int compareTo(Person other) {return Integer.compare(this.age, other.age); // 按年齡升序}@Overridepublic String toString() {return name + " (" + age + ")";}
}public class ComparableExample {public static void main(String[] args) {Person[] people = {new Person("Alice", 25),new Person("Bob", 22),new Person("Charlie", 30)};Arrays.sort(people); // 按 `Comparable` 規則排序System.out.println(Arrays.toString(people));}
}

輸出結果：

[Bob (22), Alice (25), Charlie (30)]

Comparable 的排序方式是 類內部固定的，所有調用 sort() 的地方都使用同樣的規則。

---

1.2 Comparator 接口（自定義排序）

• Comparator 是一個 外部比較器，可以用于自定義排序規則。

• 需要實現 compare() 方法，可以在不同場景使用不同的比較邏輯。

• 適用于對象有 多種排序需求，如按年齡、姓名、ID 等。

代碼示例（按 name 進行字母升序排序）：

class NameComparator implements Comparator<Person> {@Overridepublic int compare(Person p1, Person p2) {return p1.name.compareTo(p2.name); // 按名稱字母升序}
}public class ComparatorExample {public static void main(String[] args) {List<Person> people = new ArrayList<>();people.add(new Person("Alice", 25));people.add(new Person("Bob", 22));people.add(new Person("Charlie", 30));people.sort(new NameComparator()); // 使用外部比較器進行排序System.out.println(people);}
}

輸出結果：

[Alice (25), Bob (22), Charlie (30)]

使用 Comparator 可以定義多種排序規則，不同的需求可以使用不同的比較器，非常靈活。

---

二、升序和降序排序實現

2.1 Comparable 的升序和降序

在 Comparable 中，只能通過修改 compareTo() 方法來改變排序順序：

@Override
public int compareTo(Person other) {return Integer.compare(other.age, this.age); // 降序排序
}

2.2 Comparator 的升序和降序

使用 Comparator 可以輕松實現 不同排序方式：

Comparator<Person> ageAscending = Comparator.comparingInt(p -> p.age); // 按年齡升序
Comparator<Person> ageDescending = (p1, p2) -> Integer.compare(p2.age, p1.age); // 按年齡降序

代碼示例：

people.sort(ageAscending); ?// 升序排序
people.sort(ageDescending); // 降序排序

使用 Java 8 的 Lambda 表達式：?

people.sort((p1, p2) -> p1.name.compareTo(p2.name)); // 按姓名排序

---

3. 底層排序實現

在 Java 中，Arrays.sort() 和 Collections.sort() 在不同數據類型下采用不同的排序算法：

3.1 Arrays.sort()（適用于數組）

• Arrays.sort() 主要用于 數組排序，其底層實現因數據類型不同而有所不同：

• 基本類型（int[]、double[] 等）：使用 Dual-Pivot Quicksort（雙軸快速排序），這是 Quicksort 的一種優化版本。

• 對象類型（Integer[]、String[] 等）：使用 TimSort（歸并排序 + 插入排序的優化組合）。

3.1.1?基本類型：雙軸快速排序

對于 int[]、double[] 等基本數據類型的數組排序，Arrays.sort() 使用的是 雙軸快速排序（Dual-Pivot Quicksort），它是由 Vladimir Yaroslavskiy 在 2009 年提出的改進版 快速排序，其核心思想是：

1. 選取兩個基準點（pivot），將數組劃分為 三個部分：

   • 小于第一個 pivot 的部分

   • 介于兩個 pivot 之間的部分

   • 大于第二個 pivot 的部分

2. 遞歸對三個子數組進行排序。

這種優化相比于傳統的單軸快速排序，減少了遞歸調用的次數，提高了排序效率。

源碼分析

在 Arrays.sort(int[] a) 的源碼中：

public static void sort(int[] a) {DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

它會調用 DualPivotQuicksort.sort()，具體實現如下：

static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen) {if (right - left < QUICKSORT_THRESHOLD) {insertionSort(a, left, right); // 小數組使用插入排序return;}int pivot1 = a[left], pivot2 = a[right];if (pivot1 > pivot2) {swap(a, left, right);pivot1 = a[left];pivot2 = a[right];}int less = left + 1;int great = right - 1;for (int k = less; k <= great; k++) {if (a[k] < pivot1) {swap(a, k, less++);} else if (a[k] > pivot2) {swap(a, k, great--);}}sort(a, left, less - 1, work, workBase, workLen);sort(a, less, great, work, workBase, workLen);sort(a, great + 1, right, work, workBase, workLen);
}

可以看出，Dual-Pivot Quicksort 主要優化點：

• 雙軸劃分：比傳統快速排序減少遞歸層數，提高效率。

• 小數據量時使用插入排序，減少不必要的遞歸。

3.1.2對象類型：TimSort（改進版歸并排序）

對于對象數組（如 Integer[]、String[]），Java 采用的是 TimSort，它結合了 歸并排序（MergeSort）+ 插入排序（InsertionSort），并做了一些優化：

1. 數據預處理：TimSort 先尋找 已經排序的子序列（run），如果數據本身有部分有序，它可以減少比較次數。

2. 小規模數據使用插入排序：避免小規模數據使用歸并排序導致開銷大。

3. 智能歸并：選擇合適的子序列進行合并，避免不必要的合并操作，提高效率。

源碼分析:

public static <T> void sort(T[] a, Comparator<? super T> c) {if (c == null) {Arrays.sort(a); // 調用默認的 Comparable 方式排序} else {TimSort.sort(a, c); // 使用 Comparator 進行排序}
}

核心代碼:

static <T> void sort(T[] a, Comparator<? super T> c) {int lo = 0, hi = a.length;if (hi - lo < INSERTION_SORT_THRESHOLD) {insertionSort(a, lo, hi, c); // 小數據量使用插入排序return;}int mid = (lo + hi) >>> 1;sort(a, lo, mid, c);sort(a, mid, hi, c);merge(a, lo, mid, hi, c); // 歸并兩個有序數組
}

TimSort 的優點：

• 適用于部分有序的數據，比傳統歸并排序更快。

• 避免不必要的合并，提高效率。

---

2. Collections.sort() 的底層實現

Collections.sort() 主要用于 List 進行排序，它本質上是 List 的 Arrays.sort()，所以它的底層也是 TimSort。

public static <T extends Comparable<? super T>> void sort(List<T> list) {Object[] array = list.toArray();Arrays.sort(array);for (int i = 0; i < list.size(); i++)list.set(i, (T) array[i]);
}

它的執行過程：

1. 將 List 轉換成數組

2. 調用 Arrays.sort() 進行排序

3. 再把排好序的數組元素賦值回 List

這意味著 Collections.sort() 的底層仍然是 TimSort。

排序方法	適用范圍	底層實現
Arrays.sort(int[])	基本類型數組	Dual-Pivot Quicksort（雙軸快速排序）
Arrays.sort(T[])	對象數組	TimSort（歸并排序 + 插入排序優化）
Collections.sort(List<T>)	List 容器	TimSort（底層調用 Arrays.sort()）
Arrays.sort(arr, Comparator)	自定義對象排序	TimSort（支持 Comparator）

---

四、結論與總結

1. Comparable 適用于對象有固定的排序方式，如 String、Integer，實現 compareTo() 進行排序。

2. Comparator 適用于需要多個排序規則的情況，可以使用 compare() 進行定制排序。

3. 底層排序算法：

   • 基本類型使用 Dual-Pivot QuickSort（雙軸快排）。

   • 對象類型和 List 使用 TimSort（歸并排序 + 插入排序優化）。

4. Comparator 更靈活，可以動態傳遞不同的比較器，適用于多種排序需求。

掌握 Comparable 和 Comparator，可以幫助你在開發中實現更高效的排序邏輯！