为什么列表<T>。排序方法重新排序等于IComparable <T>元素？

Question

我对列表排序方法如何处理排序有问题。鉴于以下元素：

class Element : IComparable<Element> 
{ 
    public int Priority { get; set; } 
    public string Description { get; set; } 

    public int CompareTo(Element other) 
    { 
     return Priority.CompareTo(other.Priority); 
    } 
} 

如果我尝试这样排序是：

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

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

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

为什么.NET重新排序名单时的元素本质上是相同？如果比较返回一个非零值，我只想重新排列列表。

Answer 1

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

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

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

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

Answer 2

你告诉它如何比较事情，它做到了。您不应该依赖内部实现对应用程序进行排序。这就是为什么它让你重写CompareTo。如果你想有一个辅助排序参数（在这种情况下是“description”），将它编码到你的CompareTo中。依赖排序恰巧如何工作是一种很好的方式来编写一个很难找到的错误。

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

Answer 3

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

CompareTo方法是这样的：

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

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

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

Answer 4

说明为何List.Sort（）是不稳定的其他反应。如果您需要稳定的排序并使用.NET 3.5，请尝试Enumerable.OrderBy()（LINQ）。

Answer 5

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

class Element : IComparable<Element> 
{ 
    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); 
     } 
    } 
} 

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

Answer 6

这里是List<T> where T : IComparable<T>扩展方法SortStable（）：

public static void SortStable<T>(this List<T> list) where T : IComparable<T> 
{ 
    var listStableOrdered = list.OrderBy(x => x, new ComparableComparer<T>()).ToList(); 
    list.Clear(); 
    list.AddRange(listStableOrdered); 
} 

private class ComparableComparer<T> : IComparer<T> where T : IComparable<T> 
{ 
    public int Compare(T x, T y) 
    { 
     return x.CompareTo(y); 
    } 
} 

测试：

[Test] 
public void SortStable() 
{ 
    var list = new List<SortItem> 
        { 
         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<SortItem> 
{ 
    public int SortOrder { get; set; } 
    public string Name { get; set; } 

    public int CompareTo(SortItem other) 
    { 
     return SortOrder.CompareTo(other.SortOrder); 
    } 
} 

在测试方法，如果你调用sort（）方法，而不是SortStable（），你可以看到测试会失败。

Answer 7

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

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