Блог

Это обсуждалось во многих местах, по-моему, много раз, но я искал уже 3 дня и не понимал, как это происходит. Мой вопрос:

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

Что я буквально имею в виду:

Случай 1

Центральный элемент массива в качестве стержня

Это все понятно, поскольку 5 находится в центре, мы идем дальше и находим элементы, соответствующие условиям:

1.) элемент < pivot для левой стороны, если найден, мы останавливаем указатель

2.) элемент> поворот для правой стороны, если найден, мы останавливаем указатель

3.) поменяйте местами элементы, на которых мы остановили указатели во время шагов 1 и 2

Случай 2: (неясный)

первый или последний элемент в качестве стержня

Здесь неясно, куда я должен поместить оба указателя, чтобы начать поиск элементов, и в каком направлении относительно поворота я должен двигаться? Должно ли это быть также двумя указателями и как их следует перемещать? Все еще должно быть всего два указателя?

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

Обратите внимание, что алгоритм Хоара обычно включает pivot в один из разделов. Это создает проблему при использовании первого или последнего элемента в качестве сводного, поскольку шаблоны данных, такие как уже отсортированные данные, приведут к переполнению стека, поскольку разделение всегда будет состоять из 0 элементов и n элементов. Чтобы решить эту проблему, алгоритму необходимо исключить pivot в рекурсивных вызовах.