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

121

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

zjffdu
источник
14
Наихудший случай быстрой сортировки - N ^ 2, а не NlogN.
codaddict
Подождите, что произойдет, если у вас есть массив Integers или что-то в этом роде?
Тихон Джелвис,
1
Разве это не объясняется в источнике, который вы читаете?
Хамфри Богарт,
5
Эта информация уже не актуальна. Начиная с Java SE 7, MergeSort был заменен на TimSort, а QuickSort был заменен на Dual-Pivot QuickSort . См. В моем ответе ниже ссылки на документы Java API.
Уилл Бирн
Смотрите также stackoverflow.com/questions/15154158/... и JDK 7+ см stackoverflow.com/questions/32334319/...
rogerdpack

Ответы:

200

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

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

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

Майкл Боргвардт
источник
1
Еще одна причина использовать быструю сортировку заключается в том, что в среднем она выполняется быстрее, чем сортировка слиянием. Хотя быстрая сортировка выполняет больше сравнений, чем сортировка слиянием, она делает гораздо меньше обращений к массивам. Трехсторонняя быстрая сортировка также может достичь линейного времени, если входные данные содержат много повторяющихся записей, что не является необычным для практических приложений (я предполагаю, что быстрая сортировка с двумя поворотами также имеет это свойство).
Jingguo Yao,
Для примитивных типов он не клонирует массив, он может сортировать их на месте, поэтому я думаю, что единственная причина - это контракт стабильности, в основном ...
rogerdpack
27

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

Уилл Бирн
источник
2
Это не ответ, почему было выбрано 2 разных алгоритма.
Александр
12

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

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

MSW
источник
2
Java quicksort - это модифицированная быстрая сортировка, которая не снижается до O (n ^ 2), из документов: «Этот алгоритм предлагает производительность n * log (n) для многих наборов данных, что приводит к
снижению
7

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

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

kukido
источник
4
Это не главная причина. Сразу после этого предложения возник вопрос, встроенный в видео: «Почему для ссылочных типов используется MergeSort?» (потому что стабильно). Я думаю, что Седжвик не упомянул об этом в видео, чтобы оставить это под вопросом.
likern
1

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

Например: это пример, когда важна стабильность сортировки.

введите описание изображения здесь

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

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

Динеш Кумар
источник
0

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

Дэвид Макманамон
источник