STL std :: sort () использует Introsort, но как это работает?
Я действительно не понимаю алгоритм Introsort. Как вы можете видеть, я добавил псевдокод этого.
Что подразумевается под maxdepth?
Что это значит » ⌊log(length(A))⌋ × 2»
Я надеюсь, что кто-то может объяснить это мне.
procedure sort(A : array):
let maxdepth = ⌊log(length(A))⌋ × 2
introsort(A, maxdepth)
procedure introsort(A, maxdepth):
n ← length(A)
p ← partition(A) // assume this function does pivot selection, p is the final position of the pivot
if n ≤ 1:
return // base case
else if maxdepth = 0:
heapsort(A)
else:
introsort(A[0:p], maxdepth - 1)
introsort(A[p+1:n], maxdepth - 1)
Решение
Re ваш вопрос на ⌊log(length(A))⌋ × 2, ⌊...⌋ немного значит просто floor, наибольшее целое число меньше или равно значению.
В менее математическая язык, это было бы int(log(length(A))) * 2,
И на всякий случай кто-то поднимает разницу между floor (вокруг -∞) а также int (вокруг 0), это не имеет значения здесь, поскольку длина должна быть неотрицательным целым числом. Вы по-прежнему будете сталкиваться с математическими проблемами, если длина равна нулю, но это исключительный случай, так как он, вероятно, не нуждается в сортировке 🙂
Относительно Зачем maxdepth существует, это, очевидно, алгоритм, основанный на деревьях — использование log также поддерживает это, поскольку глубина сбалансированного дерева, как правило, пропорциональна логарифму числа узлов в нем.
Кажется, что происходит то, что, если интросорт выходит за пределы определенной глубины, он просто переключается на heapsort для оставшейся части.
И только одна небольшая заметка: std::sort() является не требуется использовать Introsort (как, по-видимому, подразумевает ваш заголовок), стандартное поведение мандатов, такое как at most Nlog2N comparisons, where N=last-first но в остальном не предъявляет никаких требований к выбору алгоритма.
Другие решения
Других решений пока нет …