C# 穩定排序實作：插入排序法

什麼是穩定排序？

排序前後，相等元素的相對順序保持不變即為穩定排序。.NET 內建 Array.Sort、List<T>.Sort 採用快速排序，屬不穩定排序。

範例場景

class Person : IComparable {
    public string Name;
    public int Age;
    public Person(string name, int age) { Name = name; Age = age; }
    public int CompareTo(object obj) {
        if (obj is Person p) return Age.CompareTo(p.Age);
        return 1;
    }
    public override string ToString() => $"{Name} - {Age}";
}

// 測試資料：Bob(23) 在 Charlie(23) 之前
List<Person> list = new List<Person> { new Person("Abby",38), new Person("Bob",23), new Person("Charlie",23), new Person("Danielle",18) };
list.Sort(); // 不穩定排序
// 結果可能變成 Charlie - 23, Bob - 23 (順序顛倒)

穩定排序解決方案：插入排序

插入排序為簡單且穩定的演算法，適合小資料量或近乎排序資料。

public static void InsertionSort<T>(IList<T> list, Comparison<T> comparison) {
    if (list == null) throw new ArgumentNullException(nameof(list));
    if (comparison == null) throw new ArgumentNullException(nameof(comparison));

    int count = list.Count;
    for (int j = 1; j < count; j++) {
        T key = list[j];
        int i = j - 1;
        for (; i >= 0 && comparison(list[i], key) > 0; i--)
            list[i + 1] = list[i];
        list[i + 1] = key;
    }
}

使用方式

在 Person 類別加入靜態比較方法符合 Comparison<T> 委派：

public static int Compare(Person x, Person y) {
    if (x != null && y != null) return x.CompareTo(y);
    return 1;
}

// 呼叫
InsertionSort(list, Person.Compare);
// 結果保證：Bob - 23, Charlie - 23 (原始順序保留)

效能比較

建議

預設使用 .NET 內建排序；僅在業務邏輯強制要求相等元素順序不變時，改用插入排序或其他穩定演算法（如合併排序）。