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

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

94 голоса | спросил zjffdu 14 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 14 Sep 2010 12:23:47 +0400 2010, 12:23:47

4 ответа


0

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

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

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

ответил Michael Borgwardt 14 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 14 Sep 2010 12:33:18 +0400 2010, 12:33:18
0

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

ответил Will Byrne 8 Mayam15 2015, 08:48:26
0

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

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

ответил msw 14 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 14 Sep 2010 12:33:36 +0400 2010, 12:33:36
0
Метод

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

ответил David McManamon 23 42017vEurope/Moscow11bEurope/MoscowThu, 23 Nov 2017 19:14:00 +0300 2017, 19:14:00

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132