Array.Sort是如何在.NET中实现的？

Question

我在编程中使用结构,并根据结构中的值使用排序结构IComparer.

Microsoft是如何实现该Array.Sort()方法的？有没有这方面的文件(参考)？对于Sort()Visual Basic中的所有类型,它是否相同？

这是我想要的一个简单的例子.

Dim MyArray(6) As Integer
    MyArray(0) = 1
    MyArray(1) = 45
    MyArray(2) = 45
   ' Some Code.....
    '.........
    '..........
    MyArray(3) = 1
    MyArray(4) = 10
    ' Some Code.....
    '.........
    '..........
    MyArray(5) = 1
    MyArray(6) = 57

    Array.Sort(MyArray)

Array.Sort() 将此数组排序为: (1 1 1 10 45 45 57)

1号怎么排序？它是将第一个结束还是保留在同一个索引中？

在我的原始示例(排序之前)MyArray(0) = 1和排序之后MyArray(0) = 1.

这是相同的原始1或另一个1(添加到阵列的最新的一个)移动到那个位置？

如果MyArray(0) = 1后排序应该MyArray(5) = 1在排序之前.

Answer 1

它使用Quicksort算法,当有效实施(就地)时,该算法不稳定.这意味着它不能保证相等的值在排序后保持其先前的相对位置.

例如,如果你有一堆点:

Point[] points = new Point[]
{
   new Point(0, 1),
   new Point(0, 2),
   new Point(0, 3),
   new Point(1, 1),
   new Point(1, 2),
   new Point(1, 3)
};

并且您只使用此比较器按x坐标对这些点进行排序:

private int CompareByX(Point a, Point b)
{
    return a.X - b.X;
}

它只能保证点按x坐标排序,这意味着你可以很容易地得到一个混合顺序(当看y坐标时):

Point(0, 3)
Point(0, 2)
Point(0, 1)
Point(1, 3)
Point(1, 2)
Point(1, 1)

[编辑]

这并不意味着排序算法是非确定性的(随机的).对于相同的输入数据,您将在每次运行时获得相同的输出数据.如果精确检查算法,也可以预测重组的实际方式,但这是不必要的.只需知道在使用sort例程时就会发生这种情况就足够了.

下面是您的问题的一个工作示例,尝试更改测试数据大小(第一行Main)并观察每次运行时如何重组数组:

class Program
{
    static void Main()
    {
        Point[] points = CreateTestData(1, 4).ToArray();
        DisplayItems("Before", points);
        Array.Sort(points, CompareByX);
        DisplayItems("After", points);
        Console.ReadLine();
    }

    private class Point
    {
        public int X { get; private set; }
        public int Y { get; private set; }
        public override string ToString()
        { return string.Format("({0},{1})", X, Y); }
        public Point(int x, int y)
        { X = x; Y = y; }
    }

    private static int CompareByX(Point a, Point b)
    { return a.X - b.X; }

    private static IEnumerable<Point> CreateTestData(int maxX, int maxY)
    {
        for (int x = 0; x <= 1; x++)
            for (int y = 0; y <= 4; y++)
                yield return new Point(x, y);
    }

    private static void DisplayItems(string msg, Point[] points)
    {
        Console.WriteLine(msg);
        foreach (Point p in points)
            Console.WriteLine(p.ToString());
        Console.WriteLine();
    }
}

当然,如果扩展比较器委托以包含Y坐标,则不会出现此问题:

    private static int CompareByX(Point a, Point b)
    {
         if (a.X == b.X) 
            return a.Y - b.Y;
         else
            return a.X - b.X;
    }

Answer 2

Array.Sort是一种不稳定的排序,因此相同元素的顺序是未定义的而不是守恒的.MSDN中有关Array.Sort的文章指出:

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

另一方面,LINQ的OrderBy方法是稳定的.MSDN中关于OrderBy的文章指出:

该方法执行稳定的排序; 也就是说,如果两个元素的键相等,则保留元素的顺序.相反,不稳定的排序不会保留具有相同键的元素的顺序.

Answer 3

使用.Net Reflector并亲自查看...从方法名称看起来它们使用的是QuickSort算法:System.Array + SorterObjectArray.QuickSort

Answer 4

与大多数内置分类器一样,Array.Sort()在幕后的助手类中使用QuickSort实现.排序相对有效,可以使用IComparable和IComparer接口进行定制,但它不稳定; 您的示例中的三个1可能会以与排序之前不同的相对顺序结束.如果使用更复杂的结构,可以看到这个:

struct TestStruct
{
   int a;
   int b;
}

...

//As declared, this array is already sorted by both "a" and "b" properties
var myStructAray = new [] {new TestStruct{a=1,b=1}, new TestStruct{a=1,b=2}, new TestStruct{a=1,b=3});

//QuickSorts myStructArray based on the comparison of the lambda for each element
var newArray = Array.Sort(myStructArray, x=>x.a); 

//newArray may have a different order as myStructArray at this time
for(var i=0;i<myStructArray.Count();i++)
{
   //NUnit assertion; will almost surely fail given a sufficient array length
   Assert.AreEqual(myStructArray[i].b, newArray[i].b);
}