.NET的`Array.Sort（）`方法使用的sortingalgorithm是一个稳定的algorithm吗？
.NET的Array.Sort()方法使用的sortingalgorithm是一个稳定的algorithm吗？
来自MSDN ：
这个实现执行不稳定的sorting; 也就是说，如果两个要素相同，他们的顺序可能不会被保留。 相反，稳定的sorting保留了相同元素的顺序。
这种sorting使用内省sorting。 （.NET框架4.0及更早版本中的Quicksort）。
如果你需要一个稳定的sorting，你可以使用Enumerable.OrderBy 。
加上Rasmus Faber的回答 …
在LINQ中，通过Enumerable.OrderBy和Enumerable.ThenBy进行sorting是一个稳定的sorting实现，它可以用作Array.Sort的替代。 从MSDN上的Enumerable.OrderBy文档可以看出 ：
这种方法执行稳定的sorting; 也就是说，如果两个元素的键相等，则元素的顺序被保留。 相比之下，不稳定的sorting不会保留具有相同键的元素的顺序。
另外，像Array.Sort那样的任何不稳定的sorting实现都可以通过使用源序列或数组中的元素的位置作为额外的关键字来作为Array.Sort来稳定。 下面是一个这样的实现，作为任Array.Sort数组上的通用扩展方法，并将Array.Sort转换为稳定的sorting：
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 }
正如其他答案所述，Array.Sort不稳定。 但是，LINQ OrderBy方法（和OrderByDescending等） 是稳定的，这可能是非常有用的。
不，它不是 ：
此方法使用QuickSortalgorithm。 这个实现执行不稳定的sorting
更新：这个代码不稳定Array.Sort（确保元素总是以相同的顺序sorting）：
public static class ComparisonExtensions { public static Comparison<T> WithGetHashCode<T>(this Comparison<T> current) { return (x, y) => { var result = current(x, y); if (result == 0) return x.GetHashCode() - y.GetHashCode(); return result; }; } }
使用：
Comparison<Person> comparison = (x, y) => x.BirthYear.CompareTo(y.BirthYear); Array.Sort(unstable, comparison.WithGetHashCode());
