Рубрики
Uncategorized

PHP Реализует Сортировку Вставок

Автор оригинала: David Wong.

Представил

На этом алгоритм сортировки заканчивается. Сортировка пузырьков, быстрая сортировка, сортировка по выбору и сортировка по вставкам в этой статье относительно просты и понятны. Более сложный алгоритм, никакого уродства, чтобы не перепутать чужих детей.

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

Сортировка вставки (Английский: Сортировка по вставкам) – это простой и интуитивно понятный алгоритм сортировки. Его принцип работы заключается в построении упорядоченной последовательности, сканировании назад и вперед в упорядоченной последовательности, нахождении соответствующей позиции и вставке ее в неупорядоченные данные. Сортировка вставки В реализации обычно используется сортировка на месте (т. Е. Используется только O (1) дополнительное пространство), поэтому в процессе сканирования спереди назад отсортированные элементы необходимо многократно перемещать шаг за шагом назад, чтобы обеспечить место для вставки последних элементов.

Вообще говоря, Сортировка вставки Все они реализованы на месте в массивах. Конкретный алгоритм описывается следующим образом:

  1. Начиная с первого элемента, элемент можно считать отсортированным
  2. Удалите следующий элемент и отсканируйте его назад и вперед в отсортированной последовательности элементов
  3. Если элемент (отсортирован) больше, чем новый элемент, переместите элемент в следующее местоположение
  4. Повторяйте шаг 3, пока не найдете местоположение отсортированного элемента, которое меньше или равно новому элементу
  5. После вставки нового элемента в это место
  6. Повторите шаги 2-5

Введение из Википедии. Акцент делается на шагах 2-5.

Демонстрация динамического графика

Пример

php

$arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function insertSort($arr)
{
    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    for ($i = 1; $i < $count; $i++) {
        // current value
        $temp = $arr[$i];
        for ($k = $i - 1; $k >= 0; $k--) {
            // If the condition holds, move one bit after the comparison value and replace the current value with the comparison value.
            // Reverse order $temp > $arr [$k]
            if ($temp < $arr[$k]) {
                $arr[$k + 1] = $arr[$k];
                $arr[$k] = $temp;
            }
        }
    }
    return $arr;
}

print_r(insertSort($arr));
// Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 )

Ссылка: Сортировка вставок, Серия алгоритмов сортировки PHP: Сортировка вставок.

Оригинал: “https://developpaper.com/php-implements-insert-sorting/”