Array.Sort in with nontrivial comparison function

Question

在Nutshell中考虑C#5.0中的以下代码,p.289:

int[] numbers = { 1, 2, 3, 4, 5 };
Array.Sort (numbers, (x, y) => x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1); 

给出了结果{3, 5, 1, 2, 4}.

我在纸上尝试了这个并得到了 {1, 3, 5, 2, 4}.

为什么计算机排序3 > 5 > 1？

Answer 1

最有可能的主题是关于Sort不保证相等元素顺序的事实.与保持相等元素的原始顺序的稳定排序算法不同,"不稳定排序"可以交换它们.通常,当您手动排序时,您会执行"稳定排序"版本.

Array.Sort:

此实现执行不稳定的排序; 也就是说,如果两个元素相等,则可能不会保留它们的顺序.相反,稳定的排序保留了相等元素的顺序.

样本中使用的排序函数使得1 == 3, 1 == 5如此不稳定的排序允许以任何方式对这些数字进行排序,只要它们与其他数字的顺序正确:1,3,5(稳定 - 与源中的顺序相同)或任何序列3 ,1,5(不稳定排序).

即OrderBy实现"稳定排序",您可以使用相同的比较函数在以下示例中查看结果:

void Main()
{
    int[] numbers = { 1, 2, 3, 4, 5 };
    var result = numbers.OrderBy(x=> x, new MyComparer()));
      // 1, 3, 5, 2, 4
}

public class MyComparer : IComparer<int>  
{
    public int Compare( int x, int y)
    {
      return  x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1;
    }
}

Answer 2

尽管Array.Sort指定

如果分区大小小于 16 个元素，则使用插入排序算法。

它没有指定它如何进行插入排序或它使用哪种插入排序。正如已经提到的，它还指定

此实现执行不稳定的排序

因此，Array.Sort返回后元素顺序的唯一保证是它们是排序的。这对于 来说是正确的{3, 5, 1, 2, 4}。

考虑一下使用的算法Array.Sort甚至可以执行类似这样的操作（伪代码）：

if sequence = {1, 2, 3, 4, 5} then
    sequence := {3, 5, 1, 2, 4}
end if
Sort(sequence);

当然，这将是实现定义的行为，并且在 .NET 框架的另一个版本中可能会发生变化。

将您的代码修改为

Array.Sort(numbers, (x, y) =>
    {
        Console.WriteLine(x + ", " + y);
        return x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1;
    });

将为您提供由以下方法完成的比较Array.Sort：

1, 3
1, 5
3, 5
1, 3
3, 5
2, 3
3, 4
3, 3
5, 3
5, 3
5, 5
5, 3
2, 4
2, 1
4, 2
1, 4
4, 4
4, 2
1, 2
1, 2
1, 1
1, 2
1, 1

这很可能不是您在纸上进行插入排序的方式。

要点是：Array.Sort承诺对序列进行排序，但不承诺如何执行此操作。