Как бы вы определили, какой элемент будет использоваться как быстрая в быстрой сортировке?

Question

Выбор случайного элемента или среднего элемента сводит к минимуму вероятность наихудшего случая. Но, учитывая случайный входной массив, все еще существует вероятность того, что элемент, который мы выберем случайным или средним, может привести к худшему случаю. Есть ли способ, которым мы можем решить, какой элемент сводки будет использоваться на основе предоставленного ввода? вместо того, чтобы учитывать минимальные шансы наихудшего случая

Answer 1

Элемент разворота выбирается в основном тремя способами:

1. Средний элемент
2. Случайный элемент
3. Последний элемент

The Выше три гарантирует, что случайный элемент будет выбран за O(1) время. Необходимо убедиться, что алгоритм выбора элемента сводки равен O(1), иначе общая сложность времени быстрой сортировки составит O(n^2).