.NET Array.Sort 方法原理：快速排序演算法實作、效能特性與多載用法總覽

前言

Array.Sort 採用 快速排序 演算法，平均時間複雜度 O(n log n)，在大量資料排序時效能優異。本文介紹演算法原理、方法多載與實測效能表現。

快速排序演算法原理

1. 選取一個 基準值。
2. 將陣列分割為兩部分：小於基準值、大於基準值。
3. 對兩部分遞迴執行相同步驟。
4. 最終形成有序序列。

屬於 不穩定排序（相等元素相對位置可能改變），但原地排序、空間複雜度低。

Array.Sort 常用多載

// 基本排序（實作 IComparable）
public static void Sort(Array array);

// 指定範圍排序
public static void Sort(Array array, int index, int length);

// 使用自訂比較器
public static void Sort(Array array, IComparer comparer);

// 泛型版本（效能較佳，避免裝箱）
public static void Sort(T[] array);
public static void Sort(T[] array, IComparer<T> comparer);
public static void Sort(T[] array, Comparison<T> comparison);

效能特性

• 小資料量（< 16 筆）：內部切換插入排序，減少遞迴開銷。
• 大資料量：快速排序優勢明顯，遠優於泡沫/選擇排序。
• 幾乎有序資料：.NET Framework 4.5+ 引入 Introsort（混合堆積排序）避免最壞案 O(n²)。

使用建議

• 優先使用泛型版本 Sort(T[])，避免裝箱/拆箱，型別安全。
• 複雜比較邏輯可傳入 Comparison<T> 委派或 IComparer<T> 實作。
• 需穩定排序時改用 OrderBy (LINQ) 或自行實作合併排序。

結語

Array.Sort 是 .NET 陣列排序的首選工具，理解其快速排序基底與多載選擇，能寫出高效能、可維護的排序代碼。