Sort() 和 CompareTo() 方法的内部工作原理

我一直在试图弄清楚如何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");
    }
}

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

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

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

EDIT: 也许如果我一步一步来，我可以更好地解释自己。假设我有 3 个温度对象：34、45、21ArrayList。当我打电话时ArrayList.Sort()， 是个CompareTo()方法称为类似34.CompareTo(45)？进而45.CompareTo(21)？第一次比较时返回的整数为 1，第二次比较时返回的整数为 -1？如果我只定义了这些整数，那么这些整数是如何返回的CompareTo()仅当 obj（参数）为 null 时才返回 1 的方法？我没有定义任何返回 -1 或 0 的内容。就好像我正在实现一个已经实现的方法。定义一个CompareTo()方法已定义为返回 -1、0 和 1。

让我们从基本想法开始。

CompareTo 的目的是什么？

42 到 1337 是多少。是 42...比...更棒, 少于 or equal to 1337?

这个问题及其答案的模型是CompareTo方法中的IComparable<T> and IComparable接口。为了A.CompareTo(B)，该方法可以返回：

• A is 比...更棒B：大于0的整数值。
• A is 少于B：小于0的整数值。
• A is equal toB：等于 0 的整数值。

而且当然，IComparable不限于整数。你可以实施IComparable比较您认为应该具有可比性的任意两个对象。例如，字符串：

什么是“犰狳”到“十二宫”：“犰狳”是...比...更棒, 少于 or equal to“十二生肖”？

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

CompareTo 如何帮助排序？

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

查看数组中的两个相邻元素 A 和 B。
当 A 当A>B时：交换A和B，并返回到前一对。
当我们到达终点时，我们就完成了。

您会看到，要进行排序，必须有一种方法来确定两个元素中哪一个更大。那就是那里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返回任何你想要的东西。但如果你搞砸了，那么你的方法就不再能回答问题了what is this to obj?始终返回 1 意味着对于任何 A 和 B，A 始终大于 B。这就像说：20 大于 10and10 大于 20。这没有意义，结果是你所做的任何排序也没有任何意义。垃圾进垃圾出。

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

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

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