为什么 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());


        }
        }
    }

输出为

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

为什么要连续比较两个对象 Panasonic 和 Sony 两次？？我发现不需要这样做。

Answer 1

排序算法是一个复杂的话题。考虑这个非常简单（但效率低下）的算法。

比较第一项和第二项。跟踪较高的项目并将其与下一个项目进行比较。跟踪最高项，直到到达列表末尾以找到列表中的最高项。将最高的一个放在新列表中，并将其从原始列表中删除。

然后重复前面的步骤，直到原来的列表为空。

因为您要多次浏览列表，所以您最终可能会多次比较一个项目的邻居。甚至可能在不同的传球上连续。

Answer 2

这取决于排序算法，取决于它调用了多少次比较方法。一旦我们调用 Collections.sort() 方法，它就会执行 Collections.sort() 中使用的排序。

Collections.sort() 实现使用归并排序。根据 Javadoc，只有原始数组使用快速排序进行排序。对象数组也使用 Mergesort 进行排序。

Answer 3

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

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

(归并排序方法是在收集到运行s of >= 32之后才进行的。由于你的输入只有3个元素，所以整个排序是使用二进制插入排序完成的，没有归并完成。）

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

接下来，binarySort 将下一个元素 Panasonic 插入正确的位置，从而延长此运行。进行二进制搜索以找到该位置。 2的运行的中点是位置1，也就是索尼，所以比较松下和索尼。（这是重复比较。）松下不如索尼，所以接下来是松下和三星之间的比较，以确定合适的插入点。我们现在有一个运行长度为 3.

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

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

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

Why does Collections.sort call Comparator twice with the same arguments?

java

collections

comparable

comparator