C# 經典排序算法實作：插入排序

算法原理

插入排序將陣列分為已排序與未排序兩部分，每次從未排序取出元素，插入已排序區間的正確位置。時間複雜度 O(n²)，最好情況 O(n) (已排序)，穩定排序，原地排序。

C# 實作

using System;

public class InsertionSorter
{
    public void Sort(int[] list)
    {
        for (int i = 1; i < list.Length; i++)
        {
            int temp = list[i];
            int j = i;
            while (j > 0 && list[j - 1] > temp)
            {
                list[j] = list[j - 1];
                j--;
            }
            list[j] = temp;
        }
    }
}

// 測試
public class Program
{
    public static void Main()
    {
        int[] arr = { 1, 13, 3, 6, 10, 55, 98, 2, 87, 12, 34, 75, 33, 47 };
        new InsertionSorter().Sort(arr);
        Console.WriteLine(string.Join(" ", arr));
    }
}

優化變體

1. 二分插入排序：用二分搜尋找插入位置，比較次數降為 O(n log n)，但移動次數仍 O(n²)。
2. 希爾排序：分組插入排序，大幅減少移動操作。
3. TimSort：Python/Java/.NET Core 內建混合排序，結合插入排序與合併排序。

適用場景

• 小規模或近乎有序資料 (最好 O(n))。
• 線上排序 (資料流逐筆到達)。
• 作為複雜排序算法的基礎組件 (如 TimSort、IntroSort 小區間處理)。