1

如果实现了一个类型IComparable<T>，并且您有一个包含 100 个元素的此类型的集合。当您在此集合上调用 Sort 方法时，该CompareTo方法将被调用多少次以及如何调用？会以这种方式使用吗？

CompareTo(item0, item1);
CompareTo(item1, item2);
CompareTo(item2, item3);
CompareTo(item3, item4);
...
CompareTo(item97, item98);
CompareTo(item98, item99);

编辑：基本上我要做的是将这种排序方式转变为基于值的排序，在其中我为每个项目分配一些值，然后对它们进行排序。很难解释，但我无法使用基于 -1,0,1 的排序函数来解决这个问题。但我只有一个 CompareTo 函数，我需要用它来对项目进行排序。所以我需要为每个项目生成一些值，然后程序会从最小值到最大值进行排序。

4

2 回答 2

11

好吧，您不能 100% 确定（使用大多数排序算法），因为它取决于数据。例如，某些排序算法只会对已经排序的数据执行 N（N 是集合的大小）比较，但如果不是，则需要更多。

常用的排序算法，如MergeSort、QuickSort、HeapSort都是O(n*log(n))，也就是说比较的次数会是item数乘以log base的顺序。项目数。（这些算法的对数基数将为 2。）虽然这并不准确，但它会随着这种关系而扩展。

如果您对特定排序操作调用它的次数感兴趣，您可以使用以下内容：

public class LoggingComparer<T> : IComparer<T>
{
    private IComparer<T> otherComparer;
    public LoggingComparer(IComparer<T> otherComparer)
    {
        this.otherComparer = otherComparer;
    }

    public int Count { get; private set; }

    public int Compare(T x, T y)
    {
        Count++;
        return otherComparer.Compare(x, y);
    }
}

它将包装另一个比较器，但也会计算比较调用的数量。这是一个示例用法：

var list = new List<int>() { 5, 4, 1, 2, 3, 8, 7, 9, 0 };

LoggingComparer<int> comparer = new LoggingComparer<int>(Comparer<int>.Default);
list.Sort(comparer);
Console.WriteLine(comparer.Count);
于 2012-12-06T21:56:08.013 回答
1

小猪支持Servy的回答。无论排序算法的比较操作的渐近复杂度是多少，这就是可能对 CompareTo() 进行多少次调用。请注意，这通常是一种增长模式，而不是确切的操作数量。

于 2012-12-06T21:57:25.240 回答