4

我注意到，在使用 custom 对 .NET 中的数组进行排序时IComparer<T>，会请求将项目与自身进行比较。

为什么会这样？看看是否要对相同的索引进行比较，并假设结果必须为零，这肯定是一个微不足道的优化？

示例代码：

class Comparer : IComparer<string>
{
  public int Compare(string x, string y)
  {
    Console.WriteLine("{0} vs {1}", x, y);

    return string.Compare(x, y);
  }
}

static void Main(string[] args)
{
  var values = new[] {"A", "D", "C", "B", "E"};

  Array.Sort(values, new Comparer());
}

输出（标记了奇怪的比较）：

A vs C
A vs E
C vs E
A vs C
D vs C
C vs E
C vs B
C vs C   ***
C vs C   ***
A vs B
A vs B
A vs A   ***
A vs B
A vs A   ***
D vs E
D vs E
D vs D   ***
D vs E
D vs D   ***
4

1 回答 1

3

人们报告不同的结果，因为 Array.Sort() 算法被更改了几次。至少在 .NET 4.0 和 .NET 4.5 中，可能在此之前。最新最好的版本从 QuickSort 切换到 Introsort。

由于针对 Quicksort 非常糟糕的最坏情况行为 O(n^2) 的对策，您看到了一个元素本身的比较。Introsort的Wikipedia 文章很好地解释了这一点：

在快速排序中，关键操作之一是选择枢轴：列表分区所围绕的元素。最简单的枢轴选择算法是将列表的第一个或最后一个元素作为枢轴，这在排序或接近排序输入的情况下会导致不良行为。Niklaus Wirth 的变体使用中间元素来防止这些发生，对于人为的序列退化到 O(n²)。median-of-3 枢轴选择算法采用列表的第一个、中间和最后一个元素的中值；然而，即使这在许多现实世界的输入中表现良好，仍然可以设计一个中间为 3 的杀手列表，这将导致基于这种枢轴选择技术的快速排序显着减慢。这样的输入可能会被攻击者利用，

您正在看到中位数 3 枢轴选择算法的副作用。

于 2012-11-12T13:30:53.913 回答