.NET 3.5和.NET 4.0之间的排序差异

Question

在对集合进行排序时,我遇到了一个非常奇怪的.NET框架行为.这种行为在.NET 3.5和4.0之间是不同的(但我想我知道为什么),但更重要的是(这是我真正关心的),在同一框架上的不同机器上的行为是不同的.

上下文

我正在开发一种依赖某些第三方软件的软件(在这种情况下是spring.net,但这并不重要),并且在某些时候,它正在整理一个集所有项目"相等"的集合(比较器总是返回0).这不在我的控制之下,如果排序该列表的行为始终一致,我会很好.不是.

如何重现

在.NET 3.5中创建一个简单的项目,然后运行下面的代码.当在3.5中编译时,行为似乎是一致的,并且集合将被"反转"(它出现为Three,Two,One).现在,请将项目目标更改为.NET 4(而不是4.5),然后再次运行:在我的计算机上,它不再反转集合(一,二,三),但在其他同事机器上,它确实(三二一)!!!我们有完全相同的设置......

你可以告诉我,在你的机器上,4.0以下,它是什么？反转还是不反转？

我正在尝试评估我的设置是否正确.

概念证明

class Program
{
    static void Main()
    {
        var collection = new ArrayList
        {
            "One",
            "Two",
            "Three",
        };

        // It should in any case write One, Two, Three
        Console.Out.WriteLine("Before sort: ");
        foreach (string item in collection)
        {
            Console.Out.WriteLine("\t"+item);
        }

        collection.Sort(new OrderComparator());

        // In .NET 3.5, it will write Three, Two, One
        // In .NET 4, it will sometimes write Three, Two, One, sometimes One, Two, Three: what is it for you?
        Console.Out.WriteLine("After sort: ");
        foreach (string item in collection)
        {
            Console.Out.WriteLine("\t" + item);
        }

        Console.Out.WriteLine("--end--");
        Console.Read();
    }
}

public class OrderComparator : IComparer
{
    public virtual int Compare(object o1, object o2)
    {
        return 0;
    }
}

另外,如果你知道为什么会这样,请告诉我!

Answer 1

由ArrayList.Sort()完成的排序不稳定,因此您无法预测"相同"项将排序的顺序.

此外,因为ArrayList.Sort()可以使用随机机制来为其QuickSort算法选择枢轴,所以相同的项目可以在不同的PC上或甚至在同一PC上被不同地分类.

[编辑:我找不到在当前实现中选择随机数据的任何证据,但数组排序仍然不稳定.我猜测随机性来自本机代码Quicksort实现,TrySZSort()其中可能被调用.

另外为了感兴趣,Reflector在ArrayList.Sort()中显示了这段代码(如果你稍微挖掘一下):

internal void Sort(int left, int length)
{
    if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
    {
        this.IntrospectiveSort(left, length);
    }
    else
    {
        this.DepthLimitedQuickSort(left, (length + left) - 0x1, 0x20);
    }
}

这似乎是为.Net 4.5选择完全不同的排序算法.