Я придумал несколько стратегий, но я не совсем уверен, как они влияют на поведение в целом. Я знаю, что средний случай - O (NlogN), поэтому я предполагаю, что это будет где-то в ответе. Я хочу просто поставить NlogN + 1, если я просто выберу 1-й элемент в массиве в качестве стержня для быстрой сортировки, но я не Не знаю, правильно ли это или приемлемо? Было бы здорово, если бы кто-нибудь просветил меня по этому поводу. Спасибо!
Возможные стратегии:
a) Массив случайный: выберите первый элемент, поскольку это наиболее рентабельный выбор.
б) Массив в основном отсортирован: выберите средний элемент, чтобы мы могли дополнить двоичная рекурсия разделения пополам каждый раз.
c) Массив относительно велик: выберите первый, средний и последний индексы в массиве и сравните их, выбирая наименьший, чтобы избежать худшего случая.
d) Выполнить 'c 'со случайно сгенерированными индексами, чтобы сделать выбор менее детерминированным.