Мы знаем, что быстрый сортировка - лучший алгоритм сортировки.
В коллекции .sort вместо алгоритма сортировки используется алгоритм сортировки слияния. Но Arrays.sort использует быструю сортировку.
В чем причина, почему Collections.sort использует сортировку слияния вместо быстрой сортировки?
Скорее всего, Джош Блох & sect;:
Я написал эти методы, поэтому, полагаю, я имею право отвечать. это true, что нет ни одного наилучшего алгоритма сортировки. QuickSort имеет два основных недостатка по сравнению с mergesort:
Он нестабилен (как заметил парсифал).
Это не гарантирует производительность n log n; он может деградировать до квадратичной производительности на патологических входах.
Стабильность - это не проблема для примитивных типов, так как нет понятия идентичность в отличие от (значения) равенства. И возможность квадратичное поведение считалось нецелесообразным на практике для Реализация Bentely и McIlroy (или впоследствии для Dual Pivot Quicksort), поэтому эти варианты QuickSort были использованы для примитивные сорта.
Стабильность - это большое дело при сортировке произвольных объектов. Например, предположим, что у вас есть объекты, представляющие сообщения электронной почты, и вы сортируете их сначала по дате, затем отправителем. Вы ожидаете, что они будут отсортированы по дата в каждом отправителе, но это будет верно только в том случае, если сортировка стабильный. Поэтому мы решили обеспечить стабильный вид (Merge Sort) для сортировки ссылок на объекты. (Говоря по-русски, несколько последовательных стабильные сортировки приводят к лексикографическому упорядочению на ключах в обратный порядок сортировки: окончательная сортировка определяет наиболее значительный подраздел.)
Хорошее преимущество в том, что Merge Sort гарантирует n log n (время) производительность независимо от того, что вход. Конечно, есть нижняя сторона: быстрая сортировка - это сортировка "на месте": она требует только log n внешнего пространства (для поддержания стека вызовов). Слияние, сортировка, с другой стороны, требуется O (n) внешнее пространство. Вариант TimSort (представленный на Java SE 6) требует существенно меньшего пространства (O (k)), если входной массив равен почти отсортировано.
Кроме того, важно :
Алгоритм, используемый java.util.Arrays.sort и (косвенно) посредством java.util.Collections.sort для сортировки ссылок на объекты является "измененным mergesort (в котором слияние опущено, если самый высокий элемент в low sublist меньше, чем самый низкий элемент в высоком подсписке). является достаточно быстрым стабильным типом, который гарантирует O (n log n) и требует O (n) дополнительного пространства. В свое время (было написано в 1997 году Джошуа Блох), это был прекрасный выбор, но сегодня, но мы можем сделать намного лучше.
С 2003 года сортировка списка Python использовала алгоритм, известный как timsort (после Тима Петерса, который написал это). Это стабильная, адаптивная, итеративная mergesort, который требует гораздо меньше n log (n) сравнений, когда работающих на частично отсортированных массивах, обеспечивая производительность сравнимый с традиционным слиянием при запуске на случайных массивах. подобно все правильные timesort mergesorts стабильны и работают в O (n log n) времени (худший случай). В худшем случае timsort требует временного хранения пространство для n/2 ссылок на объекты; в лучшем случае для этого требуется только небольшое постоянное пространство. Сравните это с текущим реализация, которая всегда требует дополнительного пространства для n объекта ссылки и биты n log n только в почти отсортированных списках.
Здесь подробно описывается Timsort: http://svn.python.org/projects/python/trunk/Objects/listsort.txt.
Тим Петерс оригинальная реализация написана на C. Joshua Bloch портировал его с C на Java и заканчивал тестирование, тестировал и настраивал в результате получилось широкое распространение. Получившийся код является выпадающим замена для java.util.Arrays.sort. В отношении высокоупорядоченных данных это код может работать до 25 раз быстрее, чем текущая реализация (on сервер VM HotSpot). На случайных данных скорость старого и нового реализации сопоставимы. Для очень коротких списков новый реализация значительно быстрее, чем старое даже на случайном данных (поскольку он позволяет избежать ненужного копирования данных).
Также см. Является ли Java 7 с помощью Tim Sort для массива методов. Сорт?.
Нет ни одного "лучшего" выбора. Как и во многих других вещах, это касается компромиссов.