Блог

Я немного сбит с толку относительно среднего и наихудшего случая быстрой сортировки. Я знаю следующее:

1. При выборе средней точки поворота средняя сложность быстрой сортировки равна O (nlogn).
2. Сложность быстрой сортировки в наихудшем случае — это когда в качестве стержня выбирается минимальный или максимальный элемент.
3. Оба вышеуказанных случая обеспечат одинаковую сложность для почти отсортированного списка элементов и списка несортированных данных.

Верны ли вышеуказанные три пункта? Если нет, я хотел бы знать, как быстрая сортировка будет вести себя для почти отсортированного списка и несортированного списка?

Вы правы насчет (1) и (2). Быстрая сортировка работает хорошо, когда сводная таблица делит данные примерно пополам (поэтому в идеале сводная таблица является медианной), и менее хорошо, когда разделение неравномерно.

Значение того, отсортированы входные данные или нет, зависит от того, как выбрана точка поворота.

Самый простой возможный выбор pivot — это взять первый элемент раздела, который вы разбиваете. Если вы сделаете это, и если данные будут отсортированы или отсортированы в обратном порядке, то вы получите максимально неравномерное разделение, потому что выбранное вами значение pivot является наименьшим или наибольшим значением в диапазоне.

Я полагаю, что следующий простейший способ — использовать в качестве pivot элемент на полпути вдоль входных данных. Затем, если данные уже отсортированы, вы получаете наилучшее возможное разделение. Ура! Но все еще возможно, что этот средний элемент является наименьшим (или наибольшим) значением в диапазоне, и в этом случае вы получаете неправильное разделение. Бу!

Лучший выбор pivot может быть сделан с помощью различных методов: «медиана из трех», «псевдомедиана из девяти» или случайным образом (в этом случае злоумышленник не может создать наихудший вариант для отправки вам, а вероятность плохого варианта настолько мала для входных данных значительного размера, что на практике вам может быть все равно).

Вы могли бы даже использовать функцию быстрого выбора медианы по медианам, чтобы найти медиану за линейное время и использовать ее в качестве точки опоры, таким образом, полностью избегая O (n ^ 2) наихудшего случая. На самом деле, однако, есть лучший способ избежать O (n ^ 2) наихудшего случая: самосортировка.

Когда люди говорят о «быстрой сортировке», они не обязательно имеют в виду какой-либо конкретный выбор pivot, поэтому вы не можете сказать, что будет делать быстрая сортировка, не указав выбор. Я думаю, что в самом первом описании быстрой сортировки Хоара в качестве pivot использовался первый элемент, поэтому он медленный для почти отсортированных или почти наоборот отсортированных данных.