Список комбинаторных алгоритмов

Общие комбинаторные алгоритмы[править | править код]

Алгоритм Флойда для нахождения циклов (англ.) — находит цикл в итерациях
Генераторы псевдослучайных чисел:
Алгоритм Робинсона-Шенстеда (англ.) — генерация перестановок из пар таблиц Юнга

Алгоритмы на графах[править | править код]

Алгоритм Беллмана-Форда — вычисляет кратчайший путь во взвешенном графе (где некоторые веса рёбер могут быть отрицательны)
Алгоритм Борувки (англ.) — находит минимальное остовное дерево в графе
Алгоритм Варшалла — вычисляет все кратчайшие пути во взвешенном графе
Алгоритм Дейкстры — вычисляет кратчайший путь в графе с неотрицательными весами рёбер
Алгоритм Краскала — находит остовный лес минимального веса в графе
Алгоритм основанный на источнике (англ.)— алгоритм для рисования графа
Алгоритм Прима — находит остовное дерево минимального веса в связном графе
Алгоритм Флойда-Варшалла (англ.)— решает проблему нахождения всех пар кратчайших путей во взвешенном направленном графе
Алгоритм Форда-Фалкерсона (англ.)— вычисляет максимальный поток в графе
Алгоритм Эдмонса-Карпа (англ.) — модификация алгоритма Форда-Фалкерсона
Метод ближайшего соседа
Неблокирующий минимальный охватывающий переключатель например, для телефонной связи

Алгоритмы поиска[править | править код]

Алгоритм перебора (англ.) — модификация алгоритма линейного поиска; находит k-тый по величине элемент в списке;
Дерево двоичного поиска (англ.) — использует бинарное дерево для хранения элементов;
Двоичный поиск — находит элемент в отсортированном списке
Интерполирующий поиск (Предсказывающий поиск, Поиск по словарю)
Линейный поиск — находит элемент в неотсортированном списке
Локальный поиск (оптимизация) (англ.)
Метод штрафов (англ.)
Поиск в глубину — проходит граф ветка за веткой
Поиск в ширину — проходит граф уровень за уровнем
Поиск по первому наилучшему совпадению (англ.) (англ. Best-first search)— проходит граф в порядке важности, используя очередь приоритетов
Алгоритм поиска по A*-дереву (англ.)— особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма
Троичный поиск (англ.)— находит элемент в отсортированном списке
Поиск в хеш-таблице

Алгоритмы на строках[править | править код]

Алгоритмы поиска строки[править | править код]

Алгоритм Кнута-Морриса-Пратта
Алгоритм Рабина-Карпа поиска строки
Алгоритм Бойера-Мура поиска строки (англ.)
Алгоритм Ахо-Корасика (англ.)
Алгоритм Битапа (англ.) (также известен как shift-or, shift-and или Baeza-Yates-Gonnet алгоритм)
Задача поиска наибольшей общей подпоследовательности
Задача поиска наибольшей увеличивающейся подпоследовательности (англ.)
Задача поиска наикратчайшей общей надпоследовательности (англ.)
Задача поиска наибольшей общей подстроки

Примерное соответствие[править | править код]

Деревья для строковых последовательностей[править | править код]

Алгоритмы сортировки[править | править код]

Bogosort (англ.)
Блинная сортировка (англ.)
Блочная сортировка (англ.) (также известен как корзинная сортировка)
Быстрая сортировка — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
Глупая сортировка (англ.)
Гномья сортировка (англ.)
Пирамидальная сортировка (Сортировка кучей) — превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
Плавная сортировка (англ.)
Поразрядная сортировка — сортирует строки буква за буквой
Сортировка Бентли-Седжвика (англ. BeSe sort) — модификация быстрой сортировки для составных ключей, заключающаяся в делении не пополам, а на три части — в третью попадают одинаковые (по текущему символу) ключи
Сортировка бинарным деревом
Сортировка методом вставок — определяем, где текущий элемент должен находится в отсортированном списке, и вставляем его туда
Сортировка методом выбора — наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка
Сортировка методом Шелла— попытка улучшить сортировку вставками
Сортировка перемешиванием (Сортировка коктейлем)
Сортировка подсчётом
Сортировка пузырьком
Сортировка расчёской (англ.)
Сортировка слиянием — сортируем первую и вторую половину списка отдельно, а затем — сливаем отсортированные списки
Топологическая сортировка (англ.)
Хитрая сортировка — извлекает из исходной последовательности отсортированные подпоследовательности, производя их слияние с уже извлечёнными данными
Цифровая сортировка (Сортировка по отделениям)