Вы правы насчет (1) и (2).Быстрая сортировка ведет себя хорошо, когда сводная диаграмма делит данные примерно пополам (так что в идеале сводная величина является срединной), и менее хорошо, когда деление неравномерно.
Значение того, отсортированы ли входные данные или нет, зависит откак выбирается сводка.
Самый простой возможный выбор сводки - взять первый элемент раздела, который вы разбиваете.Если вы сделаете это, и если данные отсортированы или отсортированы в обратном порядке, вы получите самое неравномерное деление, потому что выбранная вами опорная точка - это наименьшее или наибольшее значение в диапазоне.
Следующеесамое простое, я полагаю, это взять элемент поворота на полпути вдоль входа.Затем, если данные уже отсортированы, вы получите наилучшее возможное деление.Ура!Но все же возможно, что этот средний элемент является наименьшим (или наибольшим) значением в диапазоне, и в этом случае вы получаете плохое деление.Boo!
Лучший выбор сводки можно сделать с помощью различных методов: «медиана-три», «псевдо-медиана-девять» или случайный выбор (в этом случае злоумышленник не можетсоздайте наихудший случай, чтобы отправить вас, и вероятность плохого случая настолько мала для входов значительного размера, что на практике вы не можете заботиться об этом).
Вы могли бы даже использовать медиану медианБыстрый выбор, чтобы найти медиану в линейном времени и использовать ее в качестве разворота, таким образом, избегая O (n ^ 2) наихудшего случая в целом.На самом деле, однако, есть лучший способ избежать O (n ^ 2) наихудшего случая: Introsort.
Когда люди говорят о «быстрой сортировке», они не обязательно подразумевают какой-либо конкретный выбор сводки, поэтомуВы не можете сказать, что бы сделала быстрая сортировка без указания выбора.Я думаю, что в самом первом описании Quicksort Хоара первый элемент использовался как сводный, поэтому он медленен для почти отсортированных или почти обратно отсортированных данных.