为什么Collections.sort使用相同的参数两次调用Comparator？ [英] Why does Collections.sort call Comparator twice with the same arguments?

问题描述

我正在运行一个示例，以了解Java中Comparator的行为。

I'm running an example to understand the behavior of Comparator in Java.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;


    class HDTV {
    private int size;
    private String brand;

    public HDTV(int size, String brand) {
        this.size = size;
        this.brand = brand;
    }

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }

    public String getBrand() {
        return brand;
    }

    public void setBrand(String brand) {
        this.brand = brand;
    }
}

class SizeComparator implements Comparator<HDTV> {
    @Override
    public int compare(HDTV tv1, HDTV tv2) {
        int tv1Size = tv1.getSize();
        int tv2Size = tv2.getSize();
 System.out.println("Comparing :: "+tv1.getBrand()+" AND : "+tv2.getBrand());
        if (tv1Size > tv2Size) {
            return 1;
        } else if (tv1Size < tv2Size) {
            return -1;
        } else {
            return 0;
        }
    }
}

public class HelloWorld {
    public static void main(String[] args) {
        HDTV tv1 = new HDTV(55, "Samsung");
        HDTV tv2 = new HDTV(60, "Sony");
        HDTV tv3 = new HDTV(42, "Panasonic");

        ArrayList<HDTV> al = new ArrayList<HDTV>();
        al.add(tv1);
        al.add(tv2);
        al.add(tv3);

        Collections.sort(al, new SizeComparator());
        for (HDTV a : al) {
            System.out.println(a.getBrand());


        }
        }
    }

输出为

比较:: Sony AND：Samsung

比较:: Panasonic AND：Sony

比较:: Panasonic AND：索尼

比较:: Panasonic AND：Samsung

Panasonic

Samsung

Sony

Comparing :: Sony AND :Samsung
Comparing :: Panasonic AND : Sony
Comparing :: Panasonic AND : Sony
Comparing :: Panasonic AND : Samsung
Panasonic
Samsung
Sony

为什么要比较两个对象 Panasonic 和索尼连续2次？
我认为没有必要这样做。

Why is it comparing two Objects Panasonic and Sony 2 times consecutively?? I don't find it is required to do that.

推荐答案

如果是Java 7或更高版本，则为使用TimSort。 TimSort首先运行输入并检测或收集32个或更多元素的上升运行（在此实现中）。参见 countRunAndMakeAscending 。

If this is Java 7 or later, it's using TimSort. TimSort starts off by running through the input and detecting or gathering ascending runs of 32 or more elements (in this implementation). See countRunAndMakeAscending in the source code.

现在运行的时间超过32 。小于32的游程可通过对当前游程进行后续元素的二进制插入来延长，直到其长度至少为32。参见 binarySort 。

Runs longer than 32 are left in place for now. Runs shorter than 32 are lengthened by doing a binary insertion sort of subsequent elements into the current run until it's at least 32 elements long. See binarySort in the source code.

（合并排序方法仅在运行后才能完成总共> = 32个。由于您的输入只有3个元素，整个排序是使用二进制插入排序完成的，并且没有合并。）

(The merge sorting approach is done only after runs of >= 32 are gathered. Since your input has only 3 elements, the entire sort is done using the binary insertion sort, and no merging is done.)

什么 countRunAndMakeAscending 要做的是通过比较相邻元素来检测运行。首先，它将索尼与三星进行比较，然后将松下与索尼进行比较。结果是长度为2的行程，[Samsung，Sony]。

What countRunAndMakeAscending has to do is to detect runs by comparing adjacent elements. First it compares Sony to Samsung and then Panasonic to Sony. The result is a run of length 2, [Samsung, Sony].

接下来， binarySort 将行程延长了取下一个元素Panasonic，并将其插入正确的位置。进行二进制搜索以找到该位置。游程2的中点是位置1，即索尼，因此将松下与索尼进行了比较。 （这是重复的比较。）松下小于索尼，因此下一个比较是在松下和三星之间，这确定了正确的插入点。现在我们有一个长度为3的游程。

Next, binarySort lengthens this run by taking the next element, Panasonic, and inserting it into the right place. A binary search is done to find that place. The midpoint of the run of 2 is location 1, which is Sony, so it compares Panasonic to Sony. (This is the repeated comparison.) Panasonic is less than Sony, so next comparison is between Panasonic and Samsung, which determines the proper insertion point. We now have a run of length 3.

由于整个输入的长度为3，因此在进行了四个比较之后，排序就完成了。

Since the entire input is of length 3, the sort is finished after four comparisons.

之所以会出现重复比较，是因为 countRunAndMakeAscending 和 binarySort 是单独的排序阶段，因此发生第一阶段的最后一次比较与第二阶段的第一次比较相同。

The duplicate comparisons occur because countRunAndMakeAscending and binarySort are separate sort phases, and it just so happens that the last comparison of the first phase is the same as the first comparison of the second phase.

这篇关于为什么Collections.sort使用相同的参数两次调用Comparator？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！