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");
    }
}

这是MSDN关于实现CompareTo()方法的例子。我理解这个例子，也知道IComparable接口的工作原理，如果我理解正确，当我使用ArrayList.Sort()方法时，就会调用这个方法。

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

我已经尝试将CompareTo()过程打印到屏幕上，以便逆向工程输出结果，但我自己更加困惑了。

编辑： 也许如果我一步一步地解释，我可以更好地解释自己。假设我有三个温度对象：34、45、21，在一个ArrayList中。当我调用ArrayList.Sort()时，CompareTo()方法是否像34.CompareTo(45)一样被调用？然后是45.CompareTo(21)？第一次比较返回1，第二次比较返回-1？如果我只定义了CompareTo()方法在参数为null时返回1，那么这些整数是如何返回的呢？我没有定义任何返回-1或0的东西。就好像我正在实现一个已经实现了的方法，定义一个CompareTo()方法，当它已经定义为返回-1、0和1时。

- JaviML

---

另一个实例来自你正在排序的数组。 - SLaks

Answer 1

让我们从基本概念开始。

CompareTo的目的是什么？

42和1337相比如何？42是... 大于、小于还是等于1337？

这个问题及其答案被IComparable<T>和IComparable接口中的CompareTo方法所模拟。对于A.CompareTo(B)，该方法可以返回：

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

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

"Armadillo"和"Zodiac"相比如何？"Armadillo"是... 大于、小于还是等于"Zodiac"？

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

CompareTo如何帮助排序？

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

查看数组中的两个相邻元素A和B。
当A <= B时：向前移动到下一对。
当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 返回任何你想要的值。但如果你搞砸了，那么你的方法就不再回答问题“这是关于 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 总是小于任何非 null 对象。

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

- Daniel A.A. Pelsmaeker

Answer 2

当你想要比较a和b时，你会说：

int result=a.CompareTo(b);

即，第一个比较操作数是this，第二个是传递给函数的参数。

然后，当您对数组进行排序时，无论使用什么算法，都必须将元素作为this和obj发送到object.CompareTo（或此函数的可行重载）进行比较。

- Blindy

---

感谢大家的快速回答。但我仍然不明白：好的，“无论使用哪种算法”...但是，当我编写CompareTo()方法的实现时，我不是在定义算法吗？那么，为什么在我正在实现的CompareTo()方法中调用CompareTo()方法会起作用呢？ - JaviML

Answer 3

排序方法与CompareTo方法无关。我不确定使用的是哪种排序算法，但我猜测它类似于快速排序（显然不是冒泡排序）。如果您对这些算法感兴趣，可以在维基百科上详细了解。

CompareTo方法只是一种比较相同类型对象的方法。它已经为许多常见的.NET类型定义好了，并且可以被重写以进行自定义对象（您创建的对象）之间的比较。基本上，您从类型A的对象中调用它，传递第二个类型A的对象，返回值指示两者是否相等或一个是否大于另一个。

最好将CompareTo视为实用程序函数。它存在的目的是使用常见的.NET数据结构提供的排序方法进行自定义比较。如果没有类似的东西，您将不得不自己编写排序算法，以便比较您创建的类型。它的目的只是使排序方法可重用/可扩展。

- evanmcdonnal

Answer 4

简而言之，Sort方法会取出你的ArrayList中的两个元素，并对第一个元素调用CompareTo方法，将第二个元素作为参数传递进去，就像这样：

element1.CompareTo(element2)

如果element1小于element2，则CompareTo返回负值，如果它们相等，则返回0，否则返回正值。Sort使用此返回值来进行一些排序。然后，它会为下两个元素重复此过程，进行更多的排序，直到ArrayList被排序。搜索“排序算法”以获取有关此过程的更多信息。

- Dmitry Osinovskiy

Answer 5

有不同的排序算法。然而，无论如何，算法必须在某些点上决定哪个元素更大，这时就会调用CompareTo。

a.CompareTo(b) < 0;

如果a和b是整数（或伪代码中），您也可以使用：Integers。

a < b

我认为你会在很多伪代码或整数排序算法示例中发现a < b符号。而IComparable<T>的CompareTo方法则是面向对象的实现方式，或者说是一种符号表示。

- Matthias Meid