Как работает Collections.sort (...)?

Question

Чтобы быть ясным, я пытаюсь выяснить, как метод Collections.sort (list, new MyComp()) вызывает метод сравнения, в котором последовательность.

У меня есть LinkedList с сотрудниками и их персональный номер (к): Числа: {1,2,3,4,5,6} метод сравнения (o1 объекта, о2 объекта) в MyComparator возвращает некоторое количество (что не относится к этой проблеме). Как сортирует метод sort()? Вызывает ли это его с параметрами 1,2, затем 2,3, затем 3,4, затем 4,5, затем 5,6? Я отлаживаю его, но есть странная последовательность, где он отскакивает назад, а также сравнивает 1,3.

Что именно он сравнивает? Любой шаблон?

Answer 1

Конкретные сопоставления зависят от того, какой алгоритм используется внутри, метод Collections.sort используется для сортировки элементов. Согласно Javadoc для Collections.sort:

Документация для полиморфных алгоритмов, содержащихся в этом классе, как правило, содержит краткое описание реализации. Такие описания следует рассматривать как примечания к реализации, а не части спецификации. Разработчики должны смело заменить другие алгоритмы, при условии соблюдения самой спецификации. (Например, алгоритм, используемого родами не должен быть слиянием, но она должна быть стабильными.)

Других слов, реализация Java свободно использовать любой алгоритм сортировки они хотели бы, при условии, что он сохраняет равные элементы в одном и том же относительном порядке. Это означает, что без знания конкретной реализации Java не существует способа узнать, какие сравнения будут сделаны. (Если я правильно помню, версия Java для Java фактически переключила реализацию Collections.sort с Java 7 на Java 8, хотя я могу ошибаться.)

Это не плохо. Идея написания компаратора заключается в том, чтобы рассказать метод сортировки «делать все, что вам нужно, чтобы сортировать вещи, и если вам когда-нибудь понадобится провести сравнение, вот как это сделать». Это хорошая абстракция - вы говорите, как оценивать вещи, а Magic Black Box of Sorting затем идет и использует ее, чтобы привести в порядок.

Answer 2

Алгоритм сортировки Collections.sort в Java 7 - это сортировка вставки.