Мог бы ты назвать основные классические алгоритмы и их особенности?

Основные классические алгоритмы и их особенности:

• Сортировка:

  • Пузырьковая (Bubble Sort) — простая, но неэффективная (O(n²)), подходит для обучения.
  • Сортировка вставками (Insertion Sort) — эффективна для почти отсортированных данных.
  • Быстрая сортировка (Quick Sort) — быстрая в среднем (O(n log n)), но в худшем случае O(n²).
  • Сортировка слиянием (Merge Sort) — стабильная, гарантированное O(n log n), требует дополнительной памяти.

• Поиск:

  • Линейный поиск — простой, но медленный (O(n)).
  • Бинарный поиск — быстрый (O(log n)) для отсортированных массивов.

• Алгоритмы на графах:

  • Поиск в глубину (DFS) и поиск в ширину (BFS) — обход графа.
  • Алгоритм Дейкстры — поиск кратчайшего пути в графе с неотрицательными весами.

• Рекурсия и динамическое программирование:

  • Используются для решения задач с перекрывающимися подзадачами, например, вычисление чисел Фибоначчи, задачи о рюкзаке.

• Жадные алгоритмы:

  • Принимают локально оптимальные решения, например, алгоритм Крускала для минимального остовного дерева.

Пример: Быстрая сортировка на C#

void QuickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[(left + right) / 2];
    int i = left, j = right;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
            i++; j--;
        }
    }
    QuickSort(arr, left, j);
    QuickSort(arr, i, right);
}