C# 穩定排序實現指南：保持相等元素原始順序

所謂穩定排序，是指排序後相等元素仍保持原有相對順序的排序算法。.NET 內建的 Array.Sort 與 List<T>.Sort 採用快速排序，屬於不穩定排序，雖然速度極快，但無法保證相等元素的原始順序。當業務邏輯要求「同齡人按錄入順序排列」等場景時，必須引入穩定排序方案。

問題演示

以 Person 類為例，實現 IComparable 並按 Age 排序：

class Person : IComparable
{
    public Person(string name, int age)
    {
        Name = name;
        Age = age;
    }
    public string Name;
    public int Age;
    public int CompareTo(object obj)
    {
        int result = 1;
        if (obj != null && obj is Person)
        {
            Person person = (Person)obj;
            result = this.Age.CompareTo(person.Age);
        }
        return result;
    }
    public override string ToString()
    {
        return String.Format("{0} - {1}", this.Name, this.Age);
    }
}

建立集合並排序：

Person p1 = new Person("Abby", 38);
Person p2 = new Person("Bob", 23);
Person p3 = new Person("CharlIE", 23);
Person p4 = new Person("DanIElle", 18);
List<Person> list = new List<Person>();
list.Add(p1);
list.Add(p2);
list.Add(p3);
list.Add(p4);
list.Sort();
Console.WriteLine("Unstable List Sort:");
foreach (Person p in list)
{
    Console.WriteLine(p);
}

執行結果中，Bob 與 CharlIE 同為 23 歲，但排序後順序可能被打亂，這就是不穩定排序的典型表現。

解決方案

若需穩定排序，可採用以下任一策略：

• 使用 LINQ 的 OrderBy / ThenBy（內部採用穩定排序）。
• 自行實現歸併排序等穩定算法。
• 為元素附加原始索引作為次要排序鍵。

選擇哪種方案取決於性能需求與代碼複雜度的權衡。