.NET的`Array.Sort()`方法使用的排序算法是一种稳定的算法吗？

Question

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

Answer 1

来自MSDN:

此实现执行不稳定的排序; 也就是说,如果两个元素相等,则可能不会保留它们的顺序.相反,稳定的排序保留了相等元素的顺序.

排序使用内省排序.(Quicksort在4.0及更早版本的.NET框架中).

如果需要稳定排序,可以使用Enumerable.OrderBy.

Answer 2

加入Rasmus Faber的答案 ......

LINQ中的排序,通过Enumerable.OrderBy和Enumerable.ThenBy,是一个稳定的排序实现,可以用作Array.Sort的替代.来自MSDN上的Enumerable.OrderBy文档:

该方法执行稳定的排序; 也就是说,如果两个元素的键相等,则保留元素的顺序.相反,不稳定的排序不会保留具有相同键的元素的顺序.

此外,任何不稳定的排序实现,如同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 }

Answer 3

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