C# .NET 的`Array.Sort()` 方法使用的排序算法是一种稳定的算法吗？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/148074/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is the sorting algorithm used by .NET's `Array.Sort()` method a stable algorithm?
提问by Pop Catalin
采纳答案by Rasmus Faber
From MSDN:
从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.
此实现执行不稳定的排序；也就是说，如果两个元素相等，它们的顺序可能不会被保留。相反，稳定排序保留相等元素的顺序。
The sort uses introspective sort. (Quicksort in version 4.0 and earlier of the .NET framework).
排序使用内省排序。（.NET 框架 4.0 及更早版本中的快速排序）。
If you need a stable sort, you can use Enumerable.OrderBy.
如果您需要稳定的排序，您可以使用Enumerable.OrderBy。
回答by Konrad Rudolph
回答by Jon Skeet
As other answers have stated, Array.Sort isn't stable. However, the LINQ OrderBy methods (and OrderByDescending etc) arestable, which can be very useful.
正如其他答案所述， Array.Sort 不稳定。但是，LINQ OrderBy 方法（和 OrderByDescending 等）是稳定的，这非常有用。
回答by Atif Aziz
Adding to Rasmus Faber's answer…
添加到Rasmus Faber 的答案......
Sorting in LINQ, via Enumerable.OrderByand Enumerable.ThenBy, is a stable sort implementation, which can be used as an alternative to Array.Sort. From Enumerable.OrderBy documentation over at MSDN:
在 LINQ 中通过Enumerable.OrderBy和Enumerable.ThenBy进行排序是一种稳定的排序实现，可用作Array.Sort的替代方法。来自MSDN 上的 Enumerable.OrderBy 文档：
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.
此方法执行稳定排序；也就是说，如果两个元素的键相等，则保留元素的顺序。相反，不稳定排序不会保留具有相同键的元素的顺序。
Also, any unstable sort implementation, like that of Array.Sort, can be stabilized by using the position of the elements in the source sequence or array as an additional key to serve as a tie-breaker. Below is one such implementation, as a generic extension method on any single-dimensional array and which turns Array.Sortinto a stable sort:
此外，任何不稳定的排序实现，如 的实现，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);
}
}
}
Below is a sample program using StableSortfrom above:
下面是一个使用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);
}
}
Below is the output from the sample program above (running on a machine with Windows Vista SP1 and .NET Framework 3.5 SP1 installed):
下面是上面示例程序的输出（在安装了 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 }
回答by halority
UPDATE:This code not stabilizing Array.Sort (ensure that the elements are always sorted in the same order):
更新：此代码不能稳定 Array.Sort（确保元素始终按相同顺序排序）：
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;
};
}
}
Use:
用：
Comparison<Person> comparison = (x, y) => x.BirthYear.CompareTo(y.BirthYear);
Array.Sort(unstable, comparison.WithGetHashCode());
