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

Question

我在我的编程中使用结构，我使用 IComparer 根据结构中的值对结构进行排序.

微软是如何实现 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)

[编辑]

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

这是您的问题的一个工作示例，尝试更改测试数据大小(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();
    }
}

当然，如果你扩展比较器委托(delegate)以包含 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;
    }