.NET的Array.Sort()方法使用的排序算法是否稳定？

解决方案

从MSDN：

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

排序使用自省排序。 (版本4.0和更早版本的.NET框架中的Quicksort)。

如果需要稳定的排序，则可以使用Enumerable.OrderBy。

不，不是：

This method uses the QuickSort algorithm. This implementation performs an unstable sort

正如其他答案所述，Array.Sort不稳定。但是，LINQ OrderBy方法(和OrderByDescending等)是稳定的，这可能非常有用。

添加到拉斯穆斯·法伯(Rasmus Faber)的答案

通过Enumerable.OrderBy和Enumerable.ThenBy在LINQ中进行排序是一个稳定的排序实现，可以用作Array.Sort的替代方法。从Enumerable.OrderBy在MSDN上的文档中：

This method performs a stable sort;
  that is, if the keys of two elements
  are equal, the order of the elements
  is preserved. In contrast, an unstable
  sort does not preserve the order of
  elements that have the same key.

同样，任何不稳定的排序实现，例如Array.Sort，都可以通过将元素在源序列或者数组中的位置用作辅助键来稳定。下面是一个这样的实现，它是对任何一维数组的通用扩展方法，它将Array.Sort变成稳定的排序：

using System;
using System.Collections.Generic;

public static class ArrayExtensions {

    public static void StableSort<T>(this T[] values, Comparison<T> comparison) {
        var keys = new KeyValuePair<int, T>[values.Length];
        for (var i = 0; i < values.Length; i++)
            keys[i] = new KeyValuePair<int, T>(i, values[i]);
        Array.Sort(keys, values, new StabilizingComparer<T>(comparison));
    }

    private sealed class StabilizingComparer<T> : IComparer<KeyValuePair<int, T>> 
    {
        private readonly Comparison<T> _comparison;

        public StabilizingComparer(Comparison<T> comparison) {
            _comparison = comparison;
        }

        public int Compare(KeyValuePair<int, T> x, 
                           KeyValuePair<int, T> y) {
            var result = _comparison(x.Value, y.Value);
            return result != 0 ? result : x.Key.CompareTo(y.Key);
        }
    }
}

以下是从上方使用StableSort的示例程序：

static class Program 
{
    static void Main() 
    {
        var unsorted = new[] {
            new Person { BirthYear = 1948, Name = "Cat Stevens" },
            new Person { BirthYear = 1955, Name = "Kevin Costner" },
            new Person { BirthYear = 1952, Name = "Vladimir Putin" },
            new Person { BirthYear = 1955, Name = "Bill Gates" },
            new Person { BirthYear = 1948, Name = "Kathy Bates" },
            new Person { BirthYear = 1956, Name = "David Copperfield" },
            new Person { BirthYear = 1948, Name = "Jean Reno" },
        };

        Array.ForEach(unsorted, Console.WriteLine);

        Console.WriteLine();
        var unstable = (Person[]) unsorted.Clone();
        Array.Sort(unstable, (x, y) => x.BirthYear.CompareTo(y.BirthYear));
        Array.ForEach(unstable, Console.WriteLine);

        Console.WriteLine();
        var stable = (Person[]) unsorted.Clone();
        stable.StableSort((x, y) => x.BirthYear.CompareTo(y.BirthYear));
        Array.ForEach(stable, Console.WriteLine);
    }
}

sealed class Person 
{
    public int BirthYear { get; set; }
    public string Name { get; set; }

    public override string ToString() {
        return string.Format(
            "{{ BirthYear = {0}, Name = {1} }}", 
            BirthYear, Name);
    }
}

下面是上面的示例程序的输出(在装有Windows Vista SP1和.NET Framework 3.5 SP1的计算机上运行)：

{ BirthYear = 1948, Name = Cat Stevens }
{ BirthYear = 1955, Name = Kevin Costner }
{ BirthYear = 1952, Name = Vladimir Putin }
{ BirthYear = 1955, Name = Bill Gates }
{ BirthYear = 1948, Name = Kathy Bates }
{ BirthYear = 1956, Name = David Copperfield }
{ BirthYear = 1948, Name = Jean Reno }

{ BirthYear = 1948, Name = Jean Reno }
{ BirthYear = 1948, Name = Kathy Bates }
{ BirthYear = 1948, Name = Cat Stevens }
{ BirthYear = 1952, Name = Vladimir Putin }
{ BirthYear = 1955, Name = Bill Gates }
{ BirthYear = 1955, Name = Kevin Costner }
{ BirthYear = 1956, Name = David Copperfield }

{ BirthYear = 1948, Name = Cat Stevens }
{ BirthYear = 1948, Name = Kathy Bates }
{ BirthYear = 1948, Name = Jean Reno }
{ BirthYear = 1952, Name = Vladimir Putin }
{ BirthYear = 1955, Name = Kevin Costner }
{ BirthYear = 1955, Name = Bill Gates }
{ BirthYear = 1956, Name = David Copperfield }