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

本文关键字：内部 工作 CompareTo Sort 方法 | 更新日期: 2023-09-27 18:02:17

我一直在试图找出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接口是如何工作的，如果我理解正确的话，当我使用ArrayList.Sort()方法时，它会被调用。

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

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

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

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

让我们从基本思想开始。

comparareto的目的是什么?

42到1337是多少?是42…大于， 小于或等于 1337?

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

  • A 大于 B:为大于0的整数值
  • A 小于 B:小于0的整数值
  • A 等于 B:等于0的整数值

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

什么是"犰狳"到"生肖":是"犰狳"…大于， 小于或等于 "Zodiac"?

答案取决于你对大于、小于和等于的定义。对于字符串，通常的顺序是在后面出现的单词大于在前面出现的单词。

CompareTo如何帮助排序?

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

查看数组中相邻的两个元素，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返回你想要的任何东西。但是如果你搞砸了，那么你的方法就不能回答什么是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总是小于任何非空对象。

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

当你想比较a和b时，你说:

int result=a.CompareTo(b);

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

然后，当你排序数组，不管使用的算法，你必须比较元素在一起，发送它们作为this和obj到object.CompareTo(或可行的超载这个函数)。

排序方法独立于CompareTo方法。我不确定使用了什么排序算法，但我猜它类似于快速排序(显然不是冒泡排序)。如果你对这些算法感兴趣，维基百科详细记录了它们。

CompareTo方法只是比较相同类型的对象的一种方法。它是为许多常见的。net类型定义的，并且可以被重写以在自定义对象(您创建的东西)之间进行比较。基本上，你从A类型的对象中调用它，传递给它第二个A类型的对象，返回值表明两者是否相等，或者一个大于另一个。

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

简而言之，Sort取ArrayList的两个元素，对第一个元素调用CompareTo，并传递第二个元素作为参数，如下所示:

element1.CompareTo(element2)

如果element1小于element2, CompareTo返回负值，如果它们相等则返回0，否则返回正值。Sort使用这个返回值进行排序。然后它对接下来的两个元素重复这个过程，做更多的排序，以此类推，直到数组列表排序完毕。搜索"排序算法"以获得有关此过程的更多信息。

有不同的排序算法。然而，无论如何，算法必须确定哪个元素更大，这就是调用CompareTo的时候。

a.CompareTo(b) < 0;

如果a和b是Integers(或伪代码)，您还可以使用:

a < b

我想你会在很多伪代码或整数排序算法的例子中找到a < b符号。IComparable<T>的CompareTo方法是一种面向对象的实现或符号。

相关文章：