在List<T>.Sort()方法中，是否会将一个项与自身进行比较？

Question

在List<T>.Sort()方法中，是否会将一个项与自身进行比较？

c#sortingquicksorticomparer

9

如果我将自定义的IComparer传递给List的实例的Sort()方法，那么比较器的Compare(x，y)方法是否会使用相同的项进行调用？

即：是否可能调用Compare(x,x)。

编辑：更关注列表项是不同的情况。

- ForeverLearnNeverMaster

当List<>包含相同的对象超过一次时，是可以这样做的。 - Hans Passant

@Hans：是的，在我删除的评论中有点混淆了。我正在使用包含类实例的列表进行工作。当然，在某些程序中，同一实例可能会多次出现在列表中。但是，如编辑所示，我想知道列表包含不同类实例的情况。 - ForeverLearnNeverMaster

2

我改正了。参考源代码中的注释说：原地预先对低、中（枢轴）和高值进行排序。这可以提高在已经排序的数据或由多个排序运行附加在一起组成的数据面前的性能。 - Hans Passant

2

无论是否可能，您必须支持它，因为它是比较函数合同的一部分。 - Raymond Chen

4个回答

7

根据文档所述：

此方法使用Array.Sort, 该方法使用快速排序算法。

~~快速排序不会将一个项目与自身进行比较。~~某些快速排序的实现会将项目与自身进行比较。如果该项在列表中出现多次，则可能会发生这种情况。

无论哪种情况，在您的比较函数成为适当的、良好行为的比较函数时，您需要处理元素与其自身进行比较的情况。

- Thomas

这怎么解释JohnD的答案？我有什么明显的遗漏吗？ - ForeverLearnNeverMaster

这个回答不断地得到投票，有人能确认这里所述的快速排序行为吗？它似乎与JohnD的示例程序相矛盾。 - ForeverLearnNeverMaster

嗯，这很有趣！我很高兴两个答案都出现在顶部，现在JohnD的答案已经被接受了。在这种情况下，我们必须得出结论，文档是错误的。 - Thomas

有许多快速排序的实现，其中一些会将元素与自身进行比较。文档没有任何问题。 - Raymond Chen

我承认我错了 - 我从未见过以那种方式编写快速排序。然而，我仍然坚持认为文档在将此实现细节称为规范的一部分时是错误的，因为它不是。任何最坏情况下二次方、平均情况下nlogn的算法都可以用作排序函数。 - Thomas

2

虽然没有严格的保证，但我相信List的Sort方法在比较对象时不会调用你的compare方法来比较一个对象和它自己，除非该对象恰好出现在列表中多次。我得出这个结论是基于List.Sort使用快速排序算法（根据MSDN），该算法通常不涉及将同一元素与其自身进行比较（我能想到的任何其他文档化的排序算法也是如此）。（编辑：看起来Microsoft的实现确实会将元素与其自身进行比较。请参见上面的已接受答案。）

然而，良好的编程实践应该要求你的IComparer实现能够处理在两个参数中传递相同对象的情况，否则你的实现就没有满足IComparer定义的契约。它可能适用于你的场景，但你将依赖于排序方法的实现细节（可能会在将来发生更改），并且你将无法在其他情况下使用你的IComparer实现（或者更糟糕的是，你或其他人使用它并可能创建难以找到的错误）。

- Nimrand

2

另一个答案，基于 ECMA-335 的 XML 部分，即 BCL（基础类库）的规范。虽然不能保证与实际实现相关，但这是最权威的。规范仅声明：

最坏情况下，此操作的时间复杂度为 O(n^2)，其中 n 是要排序的元素数。平均情况下，它是 O(n log n)。

尽管这暗示了 QuickSort，但这绝对不是保证。规范也不要求使用 Array.Sort 进行实现。

底线：就规范而言，实现将项目与自身进行比较是完全可以的。

- Thomas

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- JohnD · Accepted Answer

我写了一个测试程序来尝试它。看起来它实际上确实将同一元素与自身进行比较（至少对于相同的项两次调用了 Compare()）。在这个程序中，Compare() 被调用时带有参数 (2, 2)。

using System;
using System.Collections.Generic;

static class Program
{
    class MyComparer : Comparer<int>
    {
        public override int Compare(int x, int y)
        {
            Console.WriteLine("Compare(" + x + ", " + y + ")");
            if (x < y) return -1;
            if (x > y) return 1;
            return 0;
        }
    }

    static void Main()
    {
        MyComparer comparer = new MyComparer();
        List<int> list = new List<int> { 1, 2, 3 };
        list.Sort(comparer);
        return;

    }
}

输出结果如下：

Compare(1, 2)
Compare(1, 3)
Compare(2, 3)
Compare(1, 2)
Compare(2, 2)
Compare(2, 3)
Compare(2, 2)