Sort()和CompareTo()方法的内部工作 [英] Internal working of the Sort() and CompareTo() methods

问题描述

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

I've been trying to figure out how the CompareTo() method works internally and I failed. I've searched this site and read some posts, and I think I've seen all there is to see in MSDN about this subject and I just don't seem to get it. An MSDN example:

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()方法时调用此接口的方法.

This is the MSDN example of the implementation of the CompareTo() method. I understand this, I understand how the IComparable interface works, if I understood correctly this gets called when I use the ArrayList.Sort() method.

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

What I don't understand is: when does the program pass the argument for the CompareTo(object obj) method? Or in other words, how does the Sort() method work? I mean, this code is comparing the instance of a temperature with another instance of temperature, but when or how is the program getting the second temperature instance for the comparison to take place? I hope my question makes sense.

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

I've tried printing to the screen the CompareTo() process so maybe I could reverse-engineer the output but I confused myself even more.

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

EDIT: Maybe if I go step by step I can explain myself better. Suppose I have 3 temperatures objects: 34, 45, 21 in an ArrayList. When I call ArrayList.Sort(), is the CompareTo() method called like 34.CompareTo(45)? And then 45.CompareTo(21)? The returned integers would be 1 in the first comparison and -1 in the second? And how did those integers get returned if I only defined the CompareTo() method to return 1 only if the obj (the parameter) was null? I didn't define anything to return -1 or 0. It's as if I was implementing a method that's already been implemented. Defining a CompareTo() method when it's already defined to return -1, 0 and 1.

推荐答案

让我们从基本概念开始.

Let's start with the basic idea.

42到1337是什么.42... 大于，小于或等于 1337?

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

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

This question and its answer are modeled by the CompareTo method in the IComparable<T> and IComparable interfaces. For A.CompareTo(B), the method can return:

• A大于 B:<0>的整数值.
• A小于 B:小于0的整数值.
• A等于 B:一个等于0的整数.

• A is greater than B: an integer value greater than 0.
• A is less than B: an integer value less than 0.
• A is equal to B: an integer value equal to 0.

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

And of course, IComparable is not limited to integers. You can implement IComparable to compare any two objects that you think should be comparable. For example, strings:

"Armadillo"到黄道带"是什么:"Armadillo" ... 大于，小于或等于"生肖"?

答案取决于您对大于，小于和等于的定义.对于字符串，通常的顺序是字典中出现的稍后单词要比出现在前面的单词更大.

The answer depends on your definition of greater than, less than and equal to. For strings the usual order is that a word that would occur later in the dictionary is greater than a word that occurs earlier.

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

Okay, now you know how you can compare any two objects. This is useful for many algorithms, but mostly sorting and ordering algorithms. Take for example a very simple sorting algorithm: stupid sort. The idea is:

查看数组中两个相邻的元素A和B.
当A< = B时:转到下一对.
当A> B时:交换A和B，然后返回上一对.
当我们到达终点时，我们就完成了.

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>发挥作用的地方.

You see, to get sorted there must be a way to determine which of the two elements is the greater one. That's where IComparable<T> comes into play.

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 大于20.这没有意义，结果是您进行的任何排序也将毫无意义.垃圾进...垃圾出.

What happens when CompareTo would always return 1?

You can of course program CompareTo to return anything you want. But if you screw up, then your method no longer answers the question what is this to obj? Always returning a 1 would mean that for any A and B, A is always greater than B. That's like saying: 20 is greater than 10 and 10 is greater than 20. It does not make sense, and the result is that any sorting you do will also not make any sense. Garbage in... garbage out.

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

The rules of the game are, for three given objects A, B and 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对象.

• A.CompareTo(A) must return 0 (A is equal to A).
• If A.CompareTo(B) returns 0, then B.CompareTo(A) returns 0 (If A is equal to B, then B is equal to A).
• If A.CompareTo(B) returns 0, and B.CompareTo(C) returns 0, then A.CompareTo(C) returns 0 (If A is equal to B, and B is equal to C, then A is equal to C).
• If A.CompareTo(B) returns a value greater than 0, then B.CompareTo(A) returns a value less than 0 (If A is greater than B, then B is less than A).
• If A.CompareTo(B) returns a value less than 0, then B.CompareTo(A) returns a value greater than 0 (If A is less than B, then B is greater than A).
• If A.CompareTo(B) returns a value greater than 0, and B.CompareTo(C) returns a value greater than 0, then A.CompareTo(C) returns a value greater than 0 (If A is greater than B, and B is greater than C, then A is greater than C).
• If A.CompareTo(B) returns a value less than 0, and B.CompareTo(C) returns a value less than 0, then A.CompareTo(C) returns a value less than 0 (If A is less than B, and B is less than C, then A is less than C).
• null is always less than any non-null object.

如果您的实现不遵循这些(简单和逻辑)原则，那么排序算法实际上可以做任何事情，并且可能无法提供您期望的结果.

If your implementation doesn't adhere to these (simple and logical) principles, then sorting algorithms can literally do anything, and probably don't give the results you expect.

这篇关于Sort()和CompareTo()方法的内部工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！