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界面是如何工作的,如果我理解正确,当我使用该ArrayList.Sort()方法时会调用它.

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

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

编辑:也许如果我一步一步走,我可以更好地解释自己.假设我有3个温度对象:34,45,21 ArrayList.当我打电话时ArrayList.Sort(),这个CompareTo()方法叫做34.CompareTo(45)？然后45.CompareTo(21)呢？返回的整数在第一次比较中为1,在第二次比较中为-1？如果我只CompareTo()在obj(参数)为null 时才定义返回1 的方法,那么这些整数是如何返回的呢？我没有定义任何返回-1或0的东西.就好像我正在实现一个已经实现的方法.定义一个CompareTo()已经定义为返回-1,0和1的方法.

Answer 1

让我们从基本思想开始吧.

CompareTo的目的是什么？

什么是42到1337.是42 ... 大于,小于或等于 1337？

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

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

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

什么是"犰狳"到"十二生肖":"犰狳"是...... 大于,小于或等于 "十二生肖"？

答案取决于你的定义大于,小于等于.对于字符串,通常的顺序是在字典中稍后出现的单词大于先前出现的单词.

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返回您想要的任何内容.但是,如果你搞砸了,那么你的方法不再回答的问题是什么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 始终小于任何非null对象.

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