Какой лучший способ выбрать пивот для быстрой сортировки?

Question

Некоторые люди говорили мне, что есть список оптимизированных сводок для быстрой сортировки, но я искал на net и не нашел его. Таким образом, этот список содержит много простых чисел, но также и много других (в настоящее время мы не можем объяснить, почему этот стержень лучший). Тогда, если вы знаете что-то об этом или имеете некоторую документацию, я заинтересован. Если вы знаете другой способ оптимизации быстрой сортировки, мне тоже интересно. Заранее спасибо

Answer 1

Нет лучшего способа выбрать точку поворота, чем выбрать средний элемент списка в качестве нашей точки.

Почему?

Идеальный способ найти точку поворота для списка чисел это найти точку поворота случайно. Однако дополнительный процесс рандомизации потребует дополнительной временной или пространственной сложности.

Что, если мы просто выберем первый элемент в качестве основного и скажем, что это как-то "случайно" для списка? Если список уже отсортирован и выбран первый элемент в качестве сводного, алгоритм сгенерирует, чтобы иметь временную сложность O (n ^ 2) вместо нашего среднего времени O (nlogn).

Поэтому, чтобы гарантировать, что дополнительная временная сложность не используется и не вырождается наш алгоритм. Самое быстрое, простое и распространенное решение - использовать средний элемент списка в качестве нашего центра. Если это так, мы можем гарантировать, что наш алгоритм O (nlogn). В этот момент нашему алгоритму будет крайне трудно вырождаться, если только он не упорядочен так, чтобы вырождаться.

Answer 2

Один тип сортировки, использующий список чисел, - это короткая оболочка, где числа используются для «пробелов»:

https://en.wikipedia.org/wiki/Shellsort#Gap_sequences

Для быстрой сортировки: Использование медианы 3 поможет, медиана 9 поможет немного больше, а медиана медиан гарантирует наихудший O (n log (n)) временной сложности, но включает большой постоянный фактор, который в большинстве случаев приводит к более медленной быстрой быстрой сортировке .

https://en.wikipedia.org/wiki/Median_of_medians

Интросорт с разумным выбором разворота (случайный, медиана 3, 9, ...), который переключается на динамическую сортировку, если уровень рекурсия становится слишком глубокой - это обычный выбор.

https://en.wikipedia.org/wiki/Introsort