Коллекции. Сортировка производительности по последующим сортам?

Question

Я использую Collections.sort с пользовательским классом компаратора.Я слышал, что это имеет O(N log N) сложность во время выполнения.Мне любопытно узнать, что происходит при последующих сортировках, когда коллекция не изменилась.

Например, допустим, у меня есть ArrayList Egg s, каждый из которых имеет приблизительное поле size (который сортирует мой компаратор).Если я вставлю десять яиц в список массивов и отсортирую их, я могу ожидать, что это займет O(N log N) времени.

Если я отсортирую это снова, без добавления, удаления или изменения каких-либо элементов, все равно будет ли этозаймет N log N время?

Answer 1

Javadoc говорит, что «объединение опущено, если самый высокий элемент в нижнем подсписке меньше самого низкого элемента в верхнем подсписке».Кажется, это означает, что ничего не происходит, поэтому должно быть быстрее.

Вы всегда можете проверить это.

Answer 2

Я не анализировал код в текущей библиотеке Sun Java. Тем не менее, Javadoc утверждает, что используется сортировка слиянием. Большинство сортировок слиянием дают производительность O (n) для уже отсортированной коллекции. Хотя это не указано в документации. Мой личный опыт показал мне действительно хорошую производительность в отсортированных или почти отсортированных списках.

Answer 3

Если развернуть ответ EJP, если в документации указывается, что этап слияния пропущен, то в этом наилучшем случае время выполнения будет составлять LG N, поскольку оно по-прежнему будет разбивать список на подзадачи LG N.Умножение на линейное сканирование - это повышение эффективности.

Answer 4

В JavaDoc Collections.sort используется алгоритм сортировки слиянием.

Здесь вы можете сами увидеть, как это работает -> http://www.sorting -algorithms.com /