快速排序不穩定特性深度解析：為何 Java/.NET 仍採用及正確使用姿勢

什麼是「不穩定排序」？

**定義**：若待排序序列中存在鍵值相等的元素，排序後它們的**相對順序可能改變**。

例子：排序 [(5, A), (3, B), (5, C)] 按第一欄升序。
穩定排序結果：**[(3, B), (5, A), (5, C)]** (A 在 C 前)。
不穩定排序可能結果：**[(3, B), (5, C), (5, A)]** (C 跑到 A 前)。

為何 Java/.NET 標準庫仍使用快速排序？

核心結論

• 基本型別：沒有「身份」，不穩定**完全無副作用**，選最快的 (快速排序/內省排序)。
• 參考型別/物件：有身份，**穩定性至關重要** (如多關鍵字排序：先按姓名排，再按年齡排，要求同年齡下姓名順序保持)。Java/.NET 物件排序**均保證穩定**。

如何將不穩定排序「變穩定」？

方法一：鍵值對 + 原始索引

// 排序前附加原始索引
var indexed = arr.Select((v, i) => new { Value = v, Index = i }).ToArray();
// 比較器：先比 Value，再比 Index
Array.Sort(indexed, (a, b) => {
    int c = a.Value.CompareTo(b.Value);
    return c != 0 ? c : a.Index.CompareTo(b.Index);
});
// 還原
for (int i = 0; i < arr.Length; i++) arr[i] = indexed[i].Value;

方法二：使用穩定排序庫函式

• Java: Arrays.sort(Object[])、Collections.sort、Stream.sorted() 皆穩定。
• .NET: List.Sort、Enumerable.OrderBy、Array.Sort (配合 IComparer 但 .NET 6+ 已穩定)。
• C++: std::stable_sort (歸併排序，O(n log n) 額外空間)。

方法三：避免在不穩定排序上做多關鍵字排序

錯誤做法：

// 先按姓名排，再按年齡排 -> 年齡排序若不穩定，姓名順序被破壞
Array.Sort(arr, (a,b) => a.Name.CompareTo(b.Name));
Array.Sort(arr, (a,b) => a.Age.CompareTo(b.Age)); // 危險！

正確做法：

// 單次排序，比較器組合多關鍵字
Array.Sort(arr, (a,b) => {
    int c = a.Age.CompareTo(b.Age);
    return c != 0 ? c : a.Name.CompareTo(b.Name);
});

實戰建議

1. **基本型別陣列** → 直接用 Array.Sort/Arrays.sort，最快且無副作用。
2. **物件/複雜類型** → 用保證穩定的 API (List.Sort, OrderBy, Collections.sort)。
3. **多關鍵字** → **單次排序組合比較器**，切勿多次排序疊加。
4. **極大數據/外部排序** → 歸併排序 (天然穩定、適合流式處理)。

總結

「不穩定」≠「不正確」。快速排序在基本型別、單關鍵字、不需保持相對順序場景下是**最優選擇**。理解資料類型與業務需求，選對 API 才是關鍵。