Какие классические алгоритмы вы знаете?

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

1. Алгоритмы сортировки

• Bubble Sort (Сортировка пузырьком): O(n²). Простой для понимания, но неэффективен для больших данных. Используется в образовательных целях.
• Quick Sort (Быстрая сортировка): O(n log n) в среднем случае, O(n²) в худшем. Эффективный алгоритм «разделяй и властвуй» с выбором опорного элемента (pivot). На практике часто используется в стандартных библиотеках (например, Array.Sort() в .NET использует гибридный подход).
• Merge Sort (Сортировка слиянием): O(n log n). Стабильная сортировка, гарантированная сложность. Требует дополнительной памяти O(n). Хорош для связных списков и внешней сортировки.

2. Алгоритмы поиска

• Binary Search (Двоичный поиск): O(log n). Крайне эффективен, но работает только на отсортированных коллекциях. Основа многих структур данных (например, в Dictionary<TKey, TValue> для поиска по ключу).

3. Алгоритмы обхода графов

• DFS (Depth-First Search, Поиск в глубину): Реализуется через рекурсию или стек. Применяется для поиска путей, проверки связности, топологической сортировки.
• BFS (Breadth-First Search, Поиск в ширину): Реализуется через очередь. Используется для поиска кратчайшего пути в невзвешенном графе, обхода по уровням.

Практический пример: Quick Sort на C# Это реализация с выбором последнего элемента в качестве опорного (Lomuto partition scheme).

public void QuickSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int pivotIndex = Partition(arr, left, right);
        QuickSort(arr, left, pivotIndex - 1); // Сортируем левую часть
        QuickSort(arr, pivotIndex + 1, right); // Сортируем правую часть
    }
}

private int Partition(int[] arr, int left, int right)
{
    int pivot = arr[right]; // Опорный элемент
    int i = left - 1; // Индекс меньшего элемента

    for (int j = left; j < right; j++)
    {
        // Если текущий элемент меньше или равен опорному
        if (arr[j] <= pivot)
        {
            i++;
            // Меняем местами arr[i] и arr[j]
            (arr[i], arr[j]) = (arr[j], arr[i]);
        }
    }
    // Помещаем опорный элемент на правильную позицию
    (arr[i + 1], arr[right]) = (arr[right], arr[i + 1]);
    return i + 1; // Возвращаем индекс опорного элемента
}

Ключевой вывод: Выбор алгоритма зависит от данных (размер, степень упорядоченности) и требований (стабильность, использование памяти).