9

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

IE。有没有Compare(x,x)可能被调用。

编辑：对列表中的项目不同的情况更感兴趣。

4

4 回答 4

12

我写了一个测试程序来尝试一下。看起来它实际上对自身执行了 Compare() 相同的元素（至少为同一个项目调用了两次 Compare()）。在这个程序中，使用参数 (2, 2) 调用 Compare()。

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)
于 2011-09-10T18:35:46.910 回答
7

从文档：

此方法使用 Array.Sort，它使用 QuickSort 算法。

QuickSort 永远不会将项目与自身进行比较。QuickSort 的一些实现将项目与自身进行比较。如果该项目在您的列表中出现多次，也会发生这种情况。

无论哪种方式，为了使您的比较函数成为一个适当的、表现良好的比较函数，您需要处理元素与其自身进行比较的情况。

于 2011-09-10T18:23:39.573 回答
2

尽管没有严格保证，但我很确定 List 的 Sort 方法永远不会调用您的 compare 方法来比较对象与自身，除非该对象碰巧多次出现在列表中。我得出这个结论的基础是 List.Sort 是使用 QuickSort 算法（根据 MSDN）实现的，它从不比较 通常不涉及将相同的元素与自身进行比较（而且我能想到的任何其他记录的排序算法也没有的）。（编辑：似乎微软的实现确实将元素与自身进行了比较。请参阅上面接受的答案。）

但是，良好的编码实践将要求您的 IComparer 实现应该能够处理在两个参数中传递相同的对象，否则您的实现不会完全履行 IComparer 定义的合同。它可能适用于您的场景，但您将依赖 sort 方法的实现细节（将来可能会更改），并且您将无法在没有此类的其他场景中使用 IComparer 实现保证（或者更糟糕的是，您或其他人确实使用了它，并且可能会造成难以发现的错误）。

于 2011-09-10T18:27:04.830 回答
2

另一个答案，这个答案基于ECMA-335 的 XML 部分，即 BCL（基类库）的规范。尽管不能保证与实际实现的功能相关，但它具有权威性。规范只说明：

在最坏的情况下，此操作为 O(n^2)，其中 n 是要排序的元素数。平均而言，它是 O(n log n)。

尽管这暗示了 QuickSort，但绝对不能保证。该规范也不需要在Array.Sort.

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

于 2011-09-11T13:55:04.443 回答