QuickSort против MergeSort для массивов примитивов в Java

Я знаю, что метод Java ---- +: = 0 =: + ---- использует MergeSort для сортировки массивов объектов (или коллекций объектов), поскольку он стабилен, а Java использует QuickSort для массивов примитивов, потому что мы этого не делаем.Не нужна стабильность, так как две равные целые числа неразличимы, т.е. их идентичность не имеет значения.В случае примитивов у меня вопрос, почему Java не использует гарантированное время MergeSort O (n log n), а вместо этого использует среднее время O (n log n) QuickSort?В последнем абзаце одного из связанных ответов здесь объясняется, что:Для ссылочных типов, где упомянутые объекты обычно занимают гораздо больше памяти, чем массив ссылок, это обычно не имеет значения.Но для примитивных типов клонирование массива напрямую удваивает использование памяти.Что это значит?Клонирование ссылки по крайней мере так же дорого, как клонирование примитива.Есть ли какие-либо другие причины для использования QuickSort (в среднем O (n log n)) вместо MergeSort (гарантированное время O (n log n)) для массивов примитивов?
7 голосов | спросил Q-RIUS 13 MaramMon, 13 Mar 2017 04:10:01 +03002017-03-13T04:10:01+03:0004 2017, 04:10:01

0 ответов


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

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

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