为什么List .Sort方法重新排序相同的IComparable 元素？

我对List Sort方法如何处理排序有疑问。 鉴于以下要素：

class Element : IComparable { public int Priority { get; set; } public string Description { get; set; } public int CompareTo(Element other) { return Priority.CompareTo(other.Priority); } } 

如果我尝试这样排序：

 List elements = new List() { new Element() { Priority = 1, Description = "First" }, new Element() { Priority = 1, Description = "Second" }, new Element() { Priority = 2, Description = "Third" } }; elements.Sort(); 

然后第一个元素是先前的第二个元素“Second”。 或者，换句话说，这个断言失败了：

 Assert.AreEqual("First", elements[0].Description); 

当元素基本相同时，为什么.NET重新排序我的列表？ 如果比较返回非零值，我希望它只对列表重新排序。

Answer 1

从MSDN的List.Sort（）方法的文档：

此方法使用Array.Sort，它使用QuickSort算法。 此实现执行不稳定的排序; 也就是说，如果两个元素相等，则可能不会保留它们的顺序。 相反，稳定的排序保留了相等元素的顺序。

这是链接： http ： //msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

从本质上讲，排序按设计和记录执行。

Answer 2

这是List where T : IComparable的扩展方法SortStable（）， List where T : IComparable ：

 public static void SortStable(this List list) where T : IComparable { var listStableOrdered = list.OrderBy(x => x, new ComparableComparer()).ToList(); list.Clear(); list.AddRange(listStableOrdered); } private class ComparableComparer : IComparer where T : IComparable { public int Compare(T x, T y) { return x.CompareTo(y); } } 

测试：

 [Test] public void SortStable() { var list = new List { new SortItem{ SortOrder = 1, Name = "Name1"}, new SortItem{ SortOrder = 2, Name = "Name2"}, new SortItem{ SortOrder = 2, Name = "Name3"}, }; list.SortStable(); Assert.That(list.ElementAt(0).SortOrder, Is.EqualTo(1)); Assert.That(list.ElementAt(0).Name, Is.EqualTo("Name1")); Assert.That(list.ElementAt(1).SortOrder, Is.EqualTo(2)); Assert.That(list.ElementAt(1).Name, Is.EqualTo("Name2")); Assert.That(list.ElementAt(2).SortOrder, Is.EqualTo(2)); Assert.That(list.ElementAt(2).Name, Is.EqualTo("Name3")); } private class SortItem : IComparable { public int SortOrder { get; set; } public string Name { get; set; } public int CompareTo(SortItem other) { return SortOrder.CompareTo(other.SortOrder); } } 

在测试方法中，如果调用Sort（）方法而不是SortStable（），则可以看到测试失败。

Answer 3

你告诉它如何比较事情，它做到了。 您不应该依赖于应用程序中Sort的内部实现。 这就是为什么它让你覆盖CompareTo。 如果要使用辅助排序参数（在本例中为“描述”），请将其编码到CompareTo中。 依赖于Sort恰好如何工作是编写很难找到的bug的好方法。

你可以找到一个稳定的.NET快速排序或使用合并排序 （已经稳定）。

Answer 4

请参阅其他回答，了解List.Sort（）不稳定的原因。 如果您需要稳定排序并使用.NET 3.5，请尝试Enumerable.OrderBy（） （LINQ）。

Answer 5

您可以通过向结构添加“索引值”来解决此问题，并在Priority.CompareTo返回0时在CompareTo方法中包含该值。然后，您需要在执行排序之前初始化“index”值。

CompareTo方法如下所示：

 public int CompareTo(Element other) { var ret = Priority.CompareTo(other.Priority); if (ret == 0) { ret = Comparer.Default.Compare(Index, other.Index); } return ret; } 

然后，而不是做elements.Sort() ，你会做：

 for(int i = 0; i < elements.Count; ++i) { elements[i].Index = i; } elements.Sort(); 

Answer 6

在一些应用中，当根据某个标准对项目列表进行排序时，保留比较相等的项目的原始顺序是不必要的。 在其他应用中，这是必要的。 保存具有匹配键的项目排列的排序方法（称为“稳定排序”通常要比没有排序的那些（“不稳定排序”）慢得多，否则它们需要大量临时存储（并且仍然稍慢）第一个广泛使用的“标准库”排序例程可能是标准C库中包含的qsort()函数。该库通常用于对相对于可用内存总量大的列表进行排序。如果库需要与要排序的数组中的项目数成比例的临时存储量，那么库就不那么有用了。

将在Java或.net等框架下使用的排序方法实际上可以使用比C qsort（）例程中可接受的临时存储更多的临时存储。 临时内存要求等于要排序的数组的大小在大多数情况下不会造成任何特定问题。 尽管如此，由于库提供Quicksort实现是传统的，这似乎是.net所遵循的模式。

Answer 7

如果你想基于两个字段而不是一个字段进行排序，你可以这样做：

 class Element : IComparable { public int Priority { get; set; } public string Description { get; set; } public int CompareTo(Element other) { if (Priority.CompareTo(other.Priority) == 0) { return Description.CompareTo(other.Description); } else { return Priority.CompareTo(other.Priority); } } } 

显然，这不符合稳定搜索算法的要求; 但是，它确实满足您的断言，并允许在相等的情况下控制元素顺序。