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

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

5 94
javascript algorithm quicksort mergesort

5 ответов:

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

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

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

157

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

18

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

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

12

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

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

4

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

0