figurecode/go-alg

Реализация базовых алгоритмов на Go

go-alg

Реализация базовых алгоритмов на Go

Алгоритм быстрой сортировки

Алгоритм состоит из трёх шагов:

1. Выбрать элемент из массива, дальше по тексту он называется опорный.
2. Разбиение: перераспределение элементов в массиве таким образом, что элементы, меньшие опорного, помещаются перед ним, а большие - после.
3. Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.

Первая версия алгоритма

• Алгоритм быстрой сортировки

В этой версии, опорным элементом всегда выбирается средний.

В таком варианте есть значительный минус, так как используется дополнительная память, чего можно избежать.