Производительность функции вставки в PHP

Question

Я изучаю сортировку, и я сделал функцию сортировки вставкой ( видео ):

<?php
set_time_limit(null);

function insertSort(array &$array)
{
    $array_size = count($array);
    $tmp = null;
    for ($i = 0; $i < $array_size; $i++)
    {
        $j = $i + 1;
        if ($j == $array_size)
        {
            break;
        }
        while ($array[$j] < $array[$i])
        {
            $tmp = $array[$i];
            $array[$i] = $array[$j];
            $array[$j] = $tmp;

            if ($i > 0)
            {
                $i--;
            }
            $j--;
        }
    }
}

$array = range(0, 100);
shuffle($array);//array(3, 0, 1, 8, 7, 2, 5, 4, 9, 6);

$time_start = microtime(true);
insertSort($array);
$time_end = microtime(true);
echo ($time_end - $time_start);
?>

Я получил следующие результаты с microtime:

10000 integers - 69.174551010132
5000 integers - 16.151810884476
1000 integers - 0.7065761089325
500 integers - 0.18473505973816
100 integers - 0.0077528953552246

Как улучшить производительность функции сортировки вставки?Спасибо.

Answer 1

Сортировка вставкой не очень эффективный алгоритм для большого количества элементов.

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

Напишите ваш тип сортировки, используя alogrithm mergesort или quicksort, и время вашей сортировки будет значительно сокращено.

Answer 2

function insertionSort($array){
    $length = count($array);

    for($j=1;$j<$length;$j++){
        $key = $array[$j];
        $i=$j-1;
        while($i>=0 && $array[$i]>$key){
            $array[$i+1]=$array[$i];
            $array[$i]=$key;
            $i--;
        }
    }
    return $array;
}

используйте эту функцию на моей машине: для 10000 времени, которое занимает это: 7.4051690101624 и выше упомянутая функция: 21.813783884048