28

我对 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 会重新排序我的列表？如果比较返回非零值，我希望它只对列表重新排序。

4

7 回答 7

44

从 MSDN 的 List.Sort() 方法的文档中：

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

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

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

于 2009-04-28T22:03:13.157 回答
7

这是一个扩展方法 SortStable() List<T> where T : IComparable<T>：

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()，你可以看到测试会失败。

于 2012-05-04T13:31:14.423 回答
3

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

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

于 2009-04-28T22:02:02.130 回答
3

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

于 2009-04-28T22:15:28.057 回答
1

您可以通过在结构中添加“索引值”来解决此问题，并在 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();
于 2009-04-28T22:13:51.757 回答
1

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

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

于 2012-05-04T15:55:51.603 回答
0

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

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

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

于 2009-04-28T22:24:40.857 回答