Как компаратор работает внутри?

Question

Для вас это может показаться тривиальным, но мне сложно визуализировать компаратор / array.sort. Как мы можем отсортировать полный массив, используя всего 2 аргумента? Как это работает внутри? Например,

- Вход - [5,3,2,6,8,10,1], Выход- [1,2,3,5,6,8,10] Какой al go он использует внутри? Какие 2 объекта сравниваются в первую очередь? (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);
    }

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));

результат:

[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]

Answer 2

Компаратор использует сортировку, называемую TimSort

Я лично не чувствую себя квалифицированным, чтобы объяснить алгоритм timsort , но я уверен, что вы можете найти много объяснений в Google.

Для второй части вашего вопроса способ, которым компаратор использует ваши два дополнения, - это определить, в каком порядке должны быть любые два заданных значения.

Так, например, , скажем, если вы хотите отсортировать [6,4], компаратор будет использовать вашу функцию ab, а затем подключит числа 8 и 4 и получит 2, и поскольку 2 положительно, сортировка знает, что 8 должно быть позади 4. Что приведет к [4,8].