c# - Sort() 和 CompareTo() 方法的内部工作

Question

我一直试图弄清楚 CompareTo() 方法在内部是如何工作的，但我失败了。我搜索了这个站点并阅读了一些帖子，我想我已经在 MSDN 中看到了关于这个主题的所有内容，但我似乎不明白。 MSDN 示例:

public int CompareTo(object obj)
{
    if (obj == null)
    {
        return 1;
    }

    Temperature otherTemperature = obj as Temperature;
    if (otherTemperature != null)
    {
        return this.temperatureC.CompareTo(otherTemperature.temperatureC);
    }
    else
    {
        throw new ArgumentException("the object is not a temperature");
    }
}

这是 CompareTo() 方法实现的 MSDN 示例。我明白这一点，我明白 IComparable 接口(interface)是如何工作的，如果我理解正确的话，当我使用 ArrayList.Sort() 方法时会调用它。

我不明白的是:程序什么时候传递CompareTo(object obj) 方法的参数？或者换句话说，Sort() 方法是如何工作的？我的意思是，这段代码将一个温度实例与另一个温度实例进行比较，但是程序何时或如何获取第二个温度实例以进行比较？我希望我的问题是有道理的。

我已经尝试将 CompareTo() 过程打印到屏幕上，所以也许我可以对输出进行逆向工程，但我更加困惑了。

编辑:也许如果我一步一步来，我可以更好地解释自己。假设我有 3 个温度对象:ArrayList 中的 34、45、21。当我调用 ArrayList.Sort() 时，CompareTo() 方法的调用方式是否类似于 34.CompareTo(45)？然后 45.CompareTo(21)？返回的整数在第一次比较中为 1，在第二次比较中为 -1？如果我仅将 CompareTo() 方法定义为仅当 obj(参数)为 null 时才返回 1，那么这些整数是如何返回的？我没有定义任何返回 -1 或 0 的东西。就好像我正在实现一个已经实现的方法。在已定义返回 -1、0 和 1 的情况下定义 CompareTo() 方法。

Answer 1

让我们从基本概念开始。

CompareTo 的目的是什么？

What is 42 to 1337. Is 42... greater than, less than or equal to 1337?

此问题及其答案由 CompareTo 建模IComparable<T> 中的方法和 IComparable接口(interface)。对于 A.CompareTo(B) ，该方法可以返回:

• A 大于 B:大于 0 的整数值。
• A 小于 B:小于 0 的整数值。
• A 等于 B:一个等于 0 的整数值。

当然，IComparable不限于整数。您可以实现 IComparable比较您认为应该比较的任何两个对象。例如，字符串:

What is "Armadillo" to "Zodiac": Is "Armadillo"... greater than, less than or equal to "Zodiac"?

答案取决于您对大于、小于和等于的定义。对于字符串，通常的顺序是字典中较晚出现的词大于较早出现的词。

CompareTo 如何帮助排序？

好的，现在您知道如何比较任意两个对象了。这对许多算法都很有用，但主要是排序算法。以一个非常简单的排序算法为例:stupid sort。想法是:

Look at two adjacent elements in your array, A and B.
When A <= B: go forward to the next pair.
When A > B: swap A and B, and go back to the previous pair.
When we reach the end, we're done.

您知道，要进行排序，必须有一种方法来确定两个元素中哪个更大。那就是IComparable<T>开始发挥作用。

public static void StupidSort<T>(T[] array)
            where T : IComparable<T>
{
    int index = 0;
    while (index < array.Length)
    {
        if (index == 0 ||
            array[index - 1].CompareTo(array[index]) <= 0)
        {
            index++;
        }
        else
        {
            Swap(array, index - 1, index);
            index--;
        }
    }
}

当 CompareTo 总是返回 1 时会发生什么？

你当然可以编程CompareTo返回任何你想要的。但如果你搞砸了，那么你的方法将不再回答什么是 this 的问题。至 obj ? 总是返回 1 意味着对于任何 A 和 B，A 总是大于 B。这就像说:20 大于 10 并且 10 大于 20。它确实没有意义，结果是你做的任何排序也没有任何意义。垃圾进...垃圾出。

游戏规则是，对于给定的三个对象 A、B 和 C:

• A.CompareTo(A)必须返回 0(A 等于 A)。
• 如果A.CompareTo(B)返回 0，然后 B.CompareTo(A)返回 0(如果 A 等于 B，则 B 等于 A)。
• 如果A.CompareTo(B)返回 0，并且 B.CompareTo(C)返回 0，然后 A.CompareTo(C)返回 0(如果 A 等于 B，并且 B 等于 C，则 A 等于 C)。
• 如果A.CompareTo(B)返回大于 0 的值，然后 B.CompareTo(A)返回小于 0 的值(如果 A 大于 B，则 B 小于 A)。
• 如果A.CompareTo(B)返回小于 0 的值，然后 B.CompareTo(A)返回大于 0 的值(如果 A 小于 B，则 B 大于 A)。
• 如果A.CompareTo(B)返回大于 0 的值，并且 B.CompareTo(C)返回大于 0 的值，然后 A.CompareTo(C)返回大于 0 的值(如果 A 大于 B，并且 B 大于 C，则 A 大于 C)。
• 如果A.CompareTo(B)返回小于 0 的值，并且 B.CompareTo(C)返回小于 0 的值，然后 A.CompareTo(C)返回小于 0 的值(如果 A 小于 B，并且 B 小于 C，则 A 小于 C)。
• null总是小于任何非空对象。

如果您的实现不遵守这些(简单且合乎逻辑的)原则，那么排序算法实际上可以做任何事情，并且可能不会给出您期望的结果。