Какие основные алгоритмы сортировки существуют и как они реализуются на PHP?

Математика Университет Алгоритмы сортировки алгоритмы сортировки сортировка на PHP основные алгоритмы реализация сортировки PHP сортировка Новый

Существует множество алгоритмов сортировки, каждый из которых имеет свои особенности, преимущества и недостатки. Рассмотрим основные из них и их реализацию на PHP.

1. Сортировка пузырьком (Bubble Sort)

Этот алгоритм работает по принципу многократного прохода по массиву, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке.

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;
}

2. Сортировка вставками (Insertion Sort)

Этот алгоритм строит отсортированный массив по одному элементу за раз, вставляя каждый новый элемент в нужную позицию.

function insertionSort($array) {
    $n = count($array);
    for ($i = 1; $i < $n; $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;
}

3. Сортировка выбором (Selection Sort)

Алгоритм находит минимальный элемент в неотсортированной части массива и меняет его местами с первым неотсортированным элементом.

function selectionSort($array) {
    $n = count($array);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($array[$j] < $array[$minIndex]) {
                $minIndex = $j;
            }
        }
        // Меняем местами
        $temp = $array[$minIndex];
        $array[$minIndex] = $array[$i];
        $array[$i] = $temp;
    }
    return $array;
}

4. Быстрая сортировка (Quick Sort)

Это один из самых эффективных алгоритмов сортировки. Он выбирает опорный элемент и делит массив на две части: элементы меньше опорного и элементы больше опорного.

function quickSort($array) {
    if (count($array) < 2) {
        return $array;
    }
    $pivot = $array[0];
    $less = [];
    $greater = [];
    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] <= $pivot) {
            $less[] = $array[$i];
        } else {
            $greater[] = $array[$i];
        }
    }
    return array_merge(quickSort($less), [$pivot], quickSort($greater));
}

5. Сортировка слиянием (Merge Sort)

Этот алгоритм делит массив на две половины, сортирует каждую половину и затем объединяет их в отсортированный массив.

function mergeSort($array) {
    if (count($array) < 2) {
        return $array;
    }
    $mid = 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);
}

Каждый из этих алгоритмов имеет свои характеристики по времени выполнения и использованию памяти. Выбор конкретного алгоритма зависит от размера данных и требований к производительности.