在对集合进行排序时调用CompareTo方法的次数是多少？

Question

如果类型实现,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函数,我需要使用它来对项目进行排序.所以我需要为每个项生成一些值,然后程序将它们从最小值到最大值进行排序.

Answer 1

那么,你不能100%肯定(使用大多数排序算法),因为它将取决于数据.例如,某些排序算法只会执行N(N是集合的大小)数据的比较已经排序,但如果不是,则需要更多.

常用的排序算法,例如MergeSort,QuickSort和HeapSort都是O(n*log(n)),也就是说,比较的数量将是项目数量乘以日志基数的顺序.东西的个数.(对于那些算法,日志库将是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);