Какие знаете алгоритмы сортировки и какие O(n)?php-101

Сортировка — фундаментальная операция в программировании. Разберём основные алгоритмы и их временную сложность (O(n)).

1. Простые алгоритмы

Пузырьковая сортировка

function bubbleSort($array) {
    $n = count($array);
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($array[$j] > $array[$j+1]) {
                // Меняем элементы местами
                $temp = $array[$j];
                $array[$j] = $array[$j+1];
                $array[$j+1] = $temp;
            }
        }
    }
    return $array;
}
  • Сложность: O(n²) в худшем и среднем случае
  • Применение: Учебные цели, малые наборы данных

Сортировка вставками

function insertionSort($array) {
    for ($i = 1; $i < count($array); $i++) {
        $key = $array[$i];
        $j = $i - 1;
        while ($j >= 0 && $array[$j] > $key) {
            $array[$j + 1] = $array[$j];
            $j--;
        }
        $array[$j + 1] = $key;
    }
    return $array;
}
  • Сложность: O(n²) в худшем случае, O(n) для почти отсортированных данных
  • Плюсы: Стабильный, эффективен для малых массивов

2. Эффективные алгоритмы

Быстрая сортировка

function quickSort($array) {
    if (count($array) <= 1) {
        return $array;
    }
    $pivot = $array[0];
    $left = $right = [];
    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] < $pivot) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}
  • Сложность: O(n log n) в среднем, O(n²) в худшем случае
  • Особенности: "Разделяй и властвуй", нестабильный

Сортировка слиянием

function mergeSort($array) {
    if (count($array) <= 1) {
        return $array;
    }
    $mid = (int)(count($array) / 2);
    $left = array_slice($array, 0, $mid);
    $right = array_slice($array, $mid);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right) {
    $result = [];
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] < $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    return array_merge($result, $left, $right);
}
  • Сложность: Всегда O(n log n)
  • Плюсы: Стабильный, предсказуемое поведение

3. Специальные алгоритмы

Сортировка подсчётом

  • Сложность: O(n + k), где k — диапазон значений
  • Условия: Работает только с целыми числами в ограниченном диапазоне

Поразрядная сортировка

  • Сложность: O(nk), где k — количество цифр
  • Особенности: Эффективен для строк и чисел фиксированной длины

Сравнительная таблица сложности

Алгоритм Лучший случай Средний случай Худший случай Память
Пузырьковая O(n) O(n²) O(n²) O(1)
Вставками O(n) O(n²) O(n²) O(1)
Быстрая O(n log n) O(n log n) O(n²) O(log n)
Слиянием O(n log n) O(n log n) O(n log n) O(n)
Подсчётом O(n + k) O(n + k) O(n + k) O(n + k)

Резюмируем:

выбор алгоритма зависит от размера данных, их структуры и требований к стабильности. Для большинства практических задач в PHP используют встроенную функцию sort(), которая реализует гибридный алгоритм (обычно на основе QuickSort). Для специфических задач (например, сортировки больших данных) стоит выбирать алгоритм осознанно, учитывая его временную и пространственную сложность.

Вопросы

Собеседования