Сколько раз можно / можно выбрать элемент для быстрой сортировки?

Question

Я пытался понять это в течение некоторого времени, но не могу понять, может ли какое-то тело объяснить это.

Answer 1

Взять описание из Википедии:

1. Выбрать элемент, называемый сводной, из массива.
2. Разделение: переупорядочить массив так, чтобы все элементы со значениями меньше, чемpivot предшествует pivot, тогда как все элементы со значениями, превышающими pivot, идут после него (равные значения могут идти в любом случае).После этого разделения шарнир находится в своем окончательном положении.Это называется операцией разбиения.
3. Рекурсивно применять вышеуказанные шаги к подмассиву элементов с меньшими значениями и отдельно к подмассиву элементов с большими значениями.

Поскольку ни один из подмассивов не включает в себя сводку, тот же элемент не может быть выбран в качестве сводки для рекурсивных вызовов.Так что это может быть только один поворот.

Если у вас есть несколько равных элементов в исходном массиве, все они могут быть использованы в качестве сводного.