Почему метод Arrays.sort в Java использует два разных алгоритма сортировки для разных типов?

Question

Метод Java 6 Arrays.sort использует Quicksort для массивов примитивов и сортировку слиянием для массивов объектов.Я считаю, что в большинстве случаев быстрая сортировка выполняется быстрее, чем сортировка слиянием, и стоит меньше памяти.Мои эксперименты подтверждают это, хотя оба алгоритма являются O (n log (n)).Так почему разные алгоритмы используются для разных типов?

Answer 1

Наиболее вероятная причина: быстрая сортировка не стабильна , т. Е. Равные записи могут изменить свою относительную позицию во время сортировки;среди прочего, это означает, что если вы сортируете уже отсортированный массив, он не может остаться неизменным.

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

OTOH, причина не использовать (гарантированно n * log (n)) стабильную сортировку слиянием для примитивных типов может заключаться в том, что она требует создания клонамассив.Для ссылочных типов, где упомянутые объекты обычно занимают гораздо больше памяти, чем массив ссылок, это обычно не имеет значения.Но для примитивных типов прямое клонирование массива удваивает использование памяти.

Answer 2

В соответствии с документами API Java 7, приведенными в , этот ответ , Arrays#Sort() для массивов объектов теперь использует TimSort , который является гибридом MergeSort и InsertionSort.С другой стороны, Arrays#sort() для примитивных массивов теперь использует Dual-Pivot QuickSort .Эти изменения были реализованы начиная с Java SE 7.

Answer 3

Одной из причин, по которой я могу придумать, является то, что быстрая сортировка имеет наихудшую временную сложность O ( n ^ 2 ), тогда как сортировка слиянием сохраняет наихудшее время O ( n log n ) , Для массивов объектов вполне справедливо ожидать, что будет несколько повторяющихся ссылок на объекты, что является одним из случаев, когда быстрая сортировка работает хуже всего.

Приличное визуальное сравнение различных алгоритмов , обратите особое внимание на самый правый график для разных алгоритмов.

Answer 4

Я брал курс Coursera по Алгоритмам и в одной из лекций профессор Боб Седжвик упомянул оценку для сортировки системы Java:

"Если программист использует объекты, возможно, пространство не является критически важнымВажное соображение и дополнительное пространство, используемое сортировкой слиянием, возможно, не проблема. А если программист использует примитивные типы, возможно, производительность является наиболее важной вещью, поэтому они используют быструю сортировку. "

Answer 5

java.util.Arrays использует быструю сортировку для примитивных типов, таких как int и mergesort для объектов, которые реализуют Comparable или используют Компаратор .Идея использования двух разных методов состоит в том, что если программист использует объекты, возможно, пространство не является критически важным фактором, и поэтому дополнительное пространство, используемое mergesort , возможно, не является проблемой, и если программист использует примитивные типы, производительность может бытьсамая важная вещь, поэтому используйте быструю сортировку .

Например: это пример, когда сортировка имеет значение.

Вот почему стабильные сортировки имеют смысл для типов объектов, особенно изменяемых типов объектов и типов объектов с большим количеством данных, чем просто ключ сортировки, и сортировка слиянием является такой сортировкой.Но для примитивных типов стабильность не только не имеет значения.Это бессмысленно.

Источник: ИНФО

Answer 6

Метод Java Arrays.sort использует быструю сортировку, сортировку вставкой и сортировку слиянием.В коде OpenJDK реализована даже быстрая сортировка с одним и двумя поворотами.Самый быстрый алгоритм сортировки зависит от обстоятельств, и победителями являются: сортировка вставкой для небольших массивов (47 выбранных в настоящее время), сортировка слиянием для большинства отсортированных массивов и быстрая сортировка для оставшихся массивов, поэтому Java Array.sort () пытается выбрать лучший алгоритм дляприменять на основании этих критериев.