为什么List＆lt; T＆gt; .Sort方法重新排序等于IComparable＆lt; T＆gt;元素？

StackOverflow https://stackoverflow.com/questions/800007

  •  03-07-2019
  •  | 
  •  

题

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

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();

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

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

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

有帮助吗？

解决方案

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

  

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

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

基本上，排序按设计和记录执行。

其他提示

这是 List＆lt; T＆gt;的扩展方法SortStable（）。其中T：IComparable＆lt; T＆gt; ：

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（），则可以看到测试失败。

你告诉它如何比较事情，它确实如此。您不应该依赖于应用程序中Sort的内部实现。这就是为什么它让你覆盖CompareTo。如果您想要一个辅助排序参数（在这种情况下为“description”），请将其编码到CompareTo中。依赖于Sort恰好如何工作是一种很好的方法来编码很难找到的bug。

您可以找到适合.NET的稳定快速排序或使用合并排序（已经稳定了）。

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

您可以通过添加“索引值”来解决此问题。到您的结构，并在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();

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

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

如果您想基于两个字段而不是一个字段进行排序，则可以执行此操作：

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);
        }
    }
}

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top