比较器在内部是如何工作的？

Question

这对你来说可能很琐碎，但我很难想象比较器/comparator和数组排序。我们如何只使用2个参数对整个数组进行排序？它是如何在内部工作的？

例如，输入- [5,3,2,6,8,10,1]，输出- [1，2，3，5，6，8，10]。

它在内部使用哪个算法？最初比较的两个对象是哪两个？（5与3相比？）然后下面是什么两个对象？（5与2相比？）还是（3与2相比？）

public static void main(String[] args) {
         Integer[] tring = new Integer[]{5,3,2,6,8,10,1};
       lol(tring);
       for(int i=0;i<tring.length;i++){
       System.out.println(tring[i]);
       }
    }
    
    public static void lol(Integer[] args) {
      Arrays.sort(args,(h1,h2)->h1-h2);
    }

- Dave Bhavin

---

据我所知，它使用双轴快速排序。 - Ecto

我可能会退一步，看一些简单的排序算法（堆、冒泡、快速等）。你每次只能比较两个值。 - Dave Newton

你下载了Java源代码来看看了吗？ - John Manko

@Zabuzard 我认为对于原始类型，它仍然使用快速排序，因为原始类型不需要稳定的排序。对于对象，它使用Tim排序。 - markspace

@markspace，你说得没错。请参考这个答案。Java使用双轴快速排序算法对包含原始数据的数组进行排序。而如果数组大小较小（小于17），则使用插入排序，如果数组大小大于17，则使用TimSort（也称为"合并排序的变种"）对包含对象的数组进行排序。 - Zabuzard

Answer 1

你可以这样想象这个过程。

Integer[] tring = new Integer[]  {5, 3, 2, 6, 8, 10, 1};
Comparator<Integer> comparator = (a, b) -> {
    System.out.println(Arrays.toString(tring) + " comparing " + a + " and " + b);
    return a.compareTo(b);
};
Arrays.sort(tring, comparator);
System.out.println(Arrays.toString(tring));

result:

[5, 3, 2, 6, 8, 10, 1] comparing 3 and 5
[5, 3, 2, 6, 8, 10, 1] comparing 2 and 3
[5, 3, 2, 6, 8, 10, 1] comparing 6 and 2
[2, 3, 5, 6, 8, 10, 1] comparing 6 and 3
[2, 3, 5, 6, 8, 10, 1] comparing 6 and 5
[2, 3, 5, 6, 8, 10, 1] comparing 8 and 5
[2, 3, 5, 6, 8, 10, 1] comparing 8 and 6
[2, 3, 5, 6, 8, 10, 1] comparing 10 and 5
[2, 3, 5, 6, 8, 10, 1] comparing 10 and 8
[2, 3, 5, 6, 8, 10, 1] comparing 1 and 6
[2, 3, 5, 6, 8, 10, 1] comparing 1 and 3
[2, 3, 5, 6, 8, 10, 1] comparing 1 and 2
[1, 2, 3, 5, 6, 8, 10]

- user4910279

Answer 2

比较器使用一种称为 TimSort 的排序方法。

个人认为我不太有资格解释 timsort算法，但是我相信你可以在谷歌上找到很多解释。

对于你问题的第二部分，比较器使用你提供的两个参数来确定任何两个给定值的顺序应该是什么。

例如，假设您想要对[6,4]进行排序，比较器将使用您的函数a-b，然后插入数字6和4并得到2，并且因为2是正数，所以排序知道6需要在4之后。这将导致[4,6]。

- Christopher Oosthuizen