C# 排序演算法實作：插入排序

插入排序是一種簡單直觀的排序演算法，其核心思想是將陣列分為「已排序」與「未排序」兩部分，每次從未排序區取出一個元素，在已排序區中從後向前掃描並找到適當位置插入。雖然平均時間複雜度為 O(n²)，但在資料量小或近乎有序時表現優異，且為穩定排序、原地排序 (空間複雜度 O(1))。

演算法步驟

1. 從索引 1 開始遍歷陣列 (索引 0 視為已排序)。
2. 保存當前元素 key = arr[i]。
3. 從 i-1 向前比較，若元素大於 key 則向後移動一位。
4. 找到插入位置後將 key 放入。

C# 實作程式碼

public static class InsertSort
{
    public static void Sort(int[] arr)
    {
        for (int i = 1; i < arr.Length; i++)
        {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

// 測試
static void Main()
{
    int[] data = { 20, 41, 27, 14, 16, 1, 8, 55, 9, 35, 22, 14 };
    InsertSort.Sort(data);
    Console.WriteLine("插入排序結果：" + string.Join(", ", data));
}

複雜度分析

適用場景與優化

• 小型資料集 (n < 50) 時常快於快速排序。
• 近乎有序資料：插入排序接近 O(n)。
• 混合演算法：如 Timsort (Python/Java 預設) 在小分區使用插入排序。
• 二分搜尋優化：查找插入位置時改用二分搜尋可減少比較次數，但移動次數不變，仍為 O(n²)。

實務建議

實際專案中極少手寫排序，應優先使用 Array.Sort 或 List<T>.Sort (內部採用 Introspective Sort：快速排序 + 堆積排序 + 插入排序混合)。理解演算法原理有助於：

1. 面試與電腦科學基礎紮根。
2. 分析第三方庫效能特徵。
3. 特定場景 (嵌入式、即時系統) 需自訂排序時能做正確選擇。