Visual C# 常用排序演算法（一）：插入排序遞增建構與 ref 參數傳遞實作

系列前言

專案需求催生排序工具類，順便以 C# 實現經典演算法。閱讀前需理解 ref/out 參數傳遞與面向物件基礎。

基本思想

將待排元素逐一插入已排序序列的適當位置，維持有序性。

排序過程示範

初始：[49] 38 65 97 76 13 27 49

插入 38: [38, 49] 65 97 76 13 27 49
插入 65: [38, 49, 65] 97 76 13 27 49
插入 97: [38, 49, 65, 97] 76 13 27 49
插入 76: [38, 49, 65, 76, 97] 13 27 49
插入 13: [13, 38, 49, 65, 76, 97] 27 49
插入 27: [13, 27, 38, 49, 65, 76, 97] 49
插入 49: [13, 27, 38, 49, 49, 65, 76, 97]

C# 實作

static void InsertionSort(ref double[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        int j = i - 1;
        int current = i;
        
        while (j >= 0)
        {
            if (array[current] < array[j])
            {
                ExchangeValue(ref array[current], ref array[j]);
                current = j;
            }
            j--;
        }
    }
}

static void ExchangeValue(ref double a, ref double b)
{
    double temp = a; a = b; b = temp;
}

關鍵技術點

• ref double[]：陣列本身為參考型別，但 ref 允許在方法內重新指派陣列變數 (如擴容)
• ref double：必須 使用 ref 才能在方法內交換兩個陣列元素的實際值
• 內層 while 實現「向左比較、逐步後移」的插入邏輯

效能特性

.NET 實務

Array.Sort / List.Sort 內建採用內省排序，小區間 (≤ 16) 自動切換插入排序。理解原理有助於正確實作 IComparer 與診斷效能問題。