PHP插入排序函数的性能 - PHP Insert Sort function performance

PHP Insert Sort function performance

本文关键字：性能函数插入排序 PHP | 更新日期: 2023-09-26

我正在学习排序，我做了一个插入排序函数(视频):

<?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

如何提高插入排序函数的性能?谢谢你。

对于大量的数据项，插入排序并不是一个非常有效的算法。

这里的要点是，如果算法本身很慢，你无法进行再多的优化来产生显著的差异。

使用归并排序或快速排序算法编写排序，您的排序时间将大大减少。

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

使用这个函数在我的机器里:一万块所用时间为:7.4051690101624上述函数为:21.813783884048