То есть, Quicksort выполняет ЛУЧШЕ, когда задан уже отсортированный список? Я не понимаю, почему это так, но, возможно, я не понимаю точно алгоритм.Является ли Quicksort «адаптивным» и «онлайн»?
Кроме того, может быстросортировать «продолжать движение», пока мы добавляем новые данные в список WHILE SORTING? Кажется, алгоритм нуждается в полном наборе всех данных в начале, чтобы «работать».
ли Quicksort работают лучше, когда дали уже отсортированный список
Я думаю, что производительность Quicks рода главно зависит от выбора элемента поворота на каждом шагу. Это было бы хуже всего, если поворотный элемент, который выбран, вероятно, будет либо маленький, либо наибольший элемент в списке
быстрой сортировки «будет держать» в то время как мы добавляем новые данные в список WHILE СОРТИРОВКИ?
Да quicksort не адаптивна. Это свойство быстрого сортировки.
ли Quicksort выполняет ЛУЧШЕ, когда задан уже отсортированный список?
Нет, на самом деле так, как его обычно учат (используйте первый элемент в качестве стержня), отсортированный (или почти отсортированный) список является наихудшим. Использование среднего или случайный элемент в качестве шарнира может смягчить это, однако.
может быстросортировать «продолжайте движение», в то время как мы добавляем новые данные в список WHILE SORTING?
Нет, ваша интуиция верна, вам нужен весь набор данных с самого начала.
«Использование середины» - я думаю, вы имеете в виду медиану, если вы всегда используете элемент в середине массива, мы можем построить примеры с наихудшим случаем без проблем. –
Нет, я имел в виду средний элемент. Да, мы можем построить для него наихудшие случаи, но они значительно менее вероятны, чем отсортированный массив, и исчезающе малая вероятность в больших массивах. – Kevin
@ G.Bach, если вы используете медиану, тогда вы гарантируете 'итерации ', но quicksort не дает такой гарантии. Quicksort - это «O (n^2)». Найти медиана каждый раз дороже, чем вероятное небольшое количество дополнительных итераций. – Adam
Быстросортировать, когда его выбор поворота является случайным, имеет время выполнения O (n lg n), где n - размер массива. Если его выбор опорных точек находится в упорядоченном порядке, его время выполнения ухудшается до O (n^2). Независимо от того, выбираете ли вы стержень с левой стороны, с правой стороны, в середине или в случайном порядке, это не имеет значения, поскольку возможно, если не вероятно, выбрать опорные точки в отсортированном порядке.
Единственный способ избежать этого - гарантировать, что опорные точки не в порядке, используя технику, такую как «Медиана трех».
Согласно Роберту Седжуику, Алгоритмы, издательство Addison-Wesley Publishing Company, 1988, стр. 124, если вы используете метод Median of Three, чтобы выбрать опорный стержень и остановить рекурсию для небольших разделов (от 5 до 25 дюймов; это оставляет массив несортированным, но вы можете быстро завершить его с помощью сортировки вставки), тогда quicksort всегда будет O (n lg n) и, кроме того, будет работать на 20% быстрее, чем обычная quicksort.
Ваш источник: – templatetypedef