В чем разница между сортировкой разделов и быстрой сортировкой?

В чем разница между сортировкой разделов и быстрой сортировкой?

13.10.2009 14:41:25
Если это домашнее задание, добавьте тег [домашнее задание]. Кроме того, когда вы посмотрели в Википедии, что вы нашли? Какие вопросы у вас были на основе исследований, которые вы уже сделали?
S.Lott 13.10.2009 14:42:25
и почему вы считаете это вопросом [java]?
quosoo 13.10.2009 14:44:08
Может быть, он новичок, поэтому он думает о Java == Программирование?
Mark Brittingham 13.10.2009 14:59:05
2 ОТВЕТА

Quicksort - это алгоритм сортировки с разделением, вы можете сослаться на Mergesort, который также является алгоритмом сортировки с разделением. Самое большое различие, вероятно, заключается в скорости, Quicksort быстрее, даже если оба они O (n * log (n)).

Quicksort использует элемент Pivot для своей сортировки, а MergeSort разделяет и захватывает. Оба, однако, являются алгоритмами сортировки на месте, что означает, что они не используют дополнительную память при сортировке.

7
13.10.2009 14:48:02
+1 - отличный ответ Когда я увидел «сортировку по разделам», я сразу подумал: «он должен иметь в виду Mergesort, если он противопоставляет его быстрой сортировке» .
Mark Brittingham 13.10.2009 14:57:52
MergeSort не является алгоритмом сортировки на месте: сортировка слиянием требует копию массива для выполнения слияния. Из Википедии: Наиболее распространенная реализация сортировки слиянием не сортируется на месте . Существует оптимизация, при которой вы выделяете только массив размером N / 2, но он все еще не на месте. Кроме того, хотя Quicksort, как правило, быстрее на практике, Mergesort имеет теоретически более жесткую верхнюю границу времени выполнения. Быстрая сортировка - это O (n * 2) в худшем случае, а не O (n * log (n)).
dantiston 1.03.2017 00:31:43

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

-1
2.09.2019 07:49:46
+1 Хорошая информация. Имейте в виду, что с вопросами, помеченными как «домашнее задание», цель состоит в том, чтобы дать руководство, а не конкретный ответ.
Chains 17.08.2011 20:51:25