在專案開發中，我們經常需要對數據集合進行排序。雖然 .NET Framework 內建了 Array.Sort 與 List<T>.Sort 等高效方法，但深入理解經典排序算法的原理與實現，對於優化效能、解決特殊排序需求以及面試準備都極具價值。本文將以 C# 為載體，系統整理插入、選擇、冒泡、快速、堆等五大經典排序算法，附帶完整代碼、圖解流程與效能分析，助你構建扎實的算法內功。
將待排序元素逐個「插入」到已排好序的序列適當位置，保持有序性，直到所有元素插入完畢。就像我們打撲克牌攤牌時，抓到一張新牌就插到手中合適位置一樣。
以數組 [49, 38, 65, 97, 76, 13, 27, 49] 為例：
初始：[49] 38 65 97 76 13 27 49
第1趟：(38) [38 49] 65 97 76 13 27 49
第2趟：(65) [38 49 65] 97 76 13 27 49
第3趟：(97) [38 49 65 97] 76 13 27 49
第4趟：(76) [38 49 65 76 97] 13 27 49
第5趟：(13) [13 38 49 65 76 97] 27 49
第6趟：(27) [13 27 38 49 65 76 97] 49
第7趟：(49) [13 27 38 49 49 65 76 97]/// <summary>
/// 插入排序（原地排序，穩定）
/// </summary>
/// <param name="arr">待排序雙精度陣列</param>
static void InsertSort(ref double[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int j = i;
// 將當前元素向前比較、交換，直到找到合適位置
while (j > 0 && arr[j] < arr[j - 1])
{
Swap(ref arr[j], ref arr[j - 1]);
j--;
}
}
}
/// <summary>
/// 交換兩個 double 值
/// </summary>
static void Swap(ref double a, ref double b)
{
double tmp = a; a = b; b = tmp;
}特點：時間複雜度 O(n²)，最好情況 O(n)（已有序），空間 O(1)，穩定排序。適合小規模或近乎有序數據。
每一趟從無序區選出最小（或最大）元素，與無序區首位交換，有序區逐漸擴大。思路直觀，但無論數據狀態如何，比較次數固定。
初始：[49 38 65 97 76 13 27 49]
第1趟：13 [38 65 97 76 49 27 49]
第2趟：13 27 [65 97 76 49 38 49]
第3趟：13 27 38 [97 76 49 65 49]
第4趟：13 27 38 49 [49 97 65 76]
第5趟：13 27 38 49 49 [97 97 76]
第6趟：13 27 38 49 49 76 [76 97]
第7趟：13 27 38 49 49 76 76 [97]
結果：13 27 38 49 49 76 76 97/// <summary>
/// 選擇排序（原地，不穩定）
/// </summary>
static void SelectSort(ref double[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
int minIdx = i;
for (int j = i + 1; j < arr.Length; j++)
if (arr[j] < arr[minIdx]) minIdx = j;
if (minIdx != i) Swap(ref arr[i], ref arr[minIdx]);
}
}特點：時間複雜度固定 O(n²)，空間 O(1)，不穩定。交換次數少（最多 n-1 次），適合寫入成本高的存儲介質。
相鄰元素兩兩比較，逆序則交換。每一趟將最大（或最小）元素「冒泡」到序列末端。可加入標誌位優化：若某趟無交換，說明已有序，提前結束。
/// <summary>
/// 冒泡排序（可指定升/降序）
/// </summary>
/// <param name="arr">待排序陣列</param>
/// <param name="ascending">true=升序，false=降序</param>
/// <returns>排序後的陣列（原地修改並返回）</returns>
static double[] BubbleSort(double[] arr, bool ascending = true)
{
if (arr.Length == 0) return arr;
for (int i = arr.Length - 1; i > 0; i--)
{
bool swapped = false;
for (int j = 0; j < i; j++)
{
bool needSwap = ascending
? arr[j] > arr[j + 1] // 升序：前大後小則交換
: arr[j] < arr[j + 1]; // 降序：前小後大則交換
if (needSwap)
{
Swap(ref arr[j], ref arr[j + 1]);
swapped = true;
}
}
if (!swapped) break; // 本趟無交換，提前結束
}
return arr;
}特點：時間 O(n²)，最好 O(n)，空間 O(1)，穩定。代碼簡潔，教學價值高，實際工程較少直接使用。
選取基準，將數組分為「小於基準」與「大於基準」兩個子區，遞歸處理子區。原地分區版本空間複雜度僅 O(log n)（遞歸棧），平均時間 O(n log n)，是實務中最常用的高效排序之一。
/// <summary>
/// 快速排序（遞歸，原地分區）
/// </summary>
/// <param name="arr">待排序陣列</param>
/// <param name="left">左邊界索引</param>
/// <param name="right">右邊界索引</param>
static void QuickSort(ref double[] arr, int left, int right)
{
if (left >= right) return;
int pivotIdx = left; // 簡單選取最左元素為基準
bool leftToRight = true; // 掃描方向標誌
while (left < right)
{
if (leftToRight)
{
// 從右向左找第一個 < 基準的元素
if (arr[right] < arr[pivotIdx])
{
Swap(ref arr[right], ref arr[pivotIdx]);
pivotIdx = right;
leftToRight = false;
}
else right--;
}
else
{
// 從左向右找第一個 > 基準的元素
if (arr[left] > arr[pivotIdx])
{
Swap(ref arr[left], ref arr[pivotIdx]);
pivotIdx = left;
leftToRight = true;
}
else left++;
}
}
// 遞歸處理左右子區
QuickSort(ref arr, left, pivotIdx - 1);
QuickSort(ref arr, pivotIdx + 1, right);
}工程建議：生產環境建議使用「三數取中」選基準、小區間改用插入排序、尾遞歸優化等技巧，或直接調用 Array.Sort（內部採用 Introspective Sort：快排+堆排+插排混合）。
將數組視為完全二叉樹，構建大根堆（父節點 ≥ 子節點），堆頂即為最大值。將堆頂與末尾元素交換，縮小堆範圍，重新調整堆，重複直到有序。時間複雜度穩定 O(n log n)，空間 O(1)，不穩定。
/// <summary>
/// 堆排序（小根堆，遞增序）
/// </summary>
static void HeapSort(ref double[] arr)
{
// 1. 自下而上構建初始小根堆
for (int i = (arr.Length - 2) / 2; i >= 0; i--)
SiftDown(ref arr, i, arr.Length - 1);
// 2. 反覆取堆頂、縮小堆、調整
for (int end = arr.Length - 1; end > 0; end--)
{
Swap(ref arr[0], ref arr[end]); // 堆頂(最小)換到末尾
SiftDown(ref arr, 0, end - 1); // 重新調整堆
}
}
/// <summary>
/// 向下篩選調整堆（迭代寫法，避免遞歸開銷）
/// </summary>
/// <param name="arr">陣列</param>
/// <param name="start">起始父節點索引</param>
/// <param name="end">堆尾部索引</param>
static void SiftDown(ref double[] arr, int start, int end)
{
int parent = start;
while (true)
{
int leftChild = parent * 2 + 1;
if (leftChild > end) break; // 無子節點
// 找出較小的子節點
int minChild = leftChild;
int rightChild = leftChild + 1;
if (rightChild <= end && arr[rightChild] < arr[leftChild])
minChild = rightChild;
// 若父節點已 ≤ 最小子節點，堆性質滿足
if (arr[parent] <= arr[minChild]) break;
Swap(ref arr[parent], ref arr[minChild]);
parent = minChild; // 繼續向下篩選
}
}圖解堆結構：
完全二叉樹順序存儲：父節點 i，左子節點 2i+1，右子節點 2i+2
| 算法 | 平均時間 | 最壞時間 | 空間 | 穩定性 | 適用場景 |
|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | 穩定 | 小數據量、近乎有序 |
| 選擇排序 | O(n²) | O(n²) | O(1) | 不穩定 | 寫入成本極高、教學演示 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 穩定 | 教學、極小數據、檢測有序性 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不穩定 | 通用高效排序、內存敏感場景 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不穩定 | 實時系統、嵌入式、保證最壞情況 |
| Array.Sort | O(n log n) | O(n log n) | O(log n) | 不穩定 | 生產環境首選（內省排序） |
「算法是程序的靈魂」，這句話在 AI 生成代碼盛行的今天依然振聾發聩。掌握經典排序算法不僅是為了應付面試，更是為了在面對效能瓶頸、特殊排序規則、海量數據外部排序等場景時，能夠從容設計最優方案。
實戰建議：
List<T>.Sort() / Array.Sort() / LINQ OrderBy()，少造輪子。IComparer<T> 或傳入 Lambda，而非重寫排序邏輯。如有疏漏或更優雅的寫法，歡迎留言指正，共同精進！
