为什么 Collections.sort 用相同的参数调用 Comparator 两次？

Question

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

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 : Sony
比较 :: Panasonic AND : Samsung
Panasonic
Samsung
Sony

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

Answer 1

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

超过 32 次的运行时间暂时保留。通过在当前运行中对后续元素进行二进制插入排序，直到它至少有 32 个元素长，运行短于 32 的运行会被加长。见binarySort源代码。

（合并排序方法仅在收集了 >= 32 的运行后完成。由于您的输入只有 3 个元素，因此整个排序使用二元插入排序完成，不进行合并。）

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

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

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

重复比较的发生是因为countRunAndMakeAscending和binarySort是单独的排序阶段，而且恰好第一阶段的最后一次比较与第二阶段的第一次比较相同。