PHP插入排序功能的性能

我正在學習有關排序和我做了一個插入排序函數（video）：PHP插入排序功能的性能

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

如何提高插入排序功能的性能？謝謝。

來源

2011-04-21 thom

for循環保證，其中陣列被重複的順序。 foreach *可能*以非連續順序返回元素。 – 2011-04-21 21:31:10

foreach的性能不佳：http：//www.phpbench.com/。謝謝。 – thom 2011-04-21 21:31:38

你真的有*實際*性能問題嗎？一個實用的？請注意，phpbench的交易時間爲微秒 - 百萬分之一秒。所顯示的大多數比較將不會對代碼產生實際影響。您製作的每個數據庫請求將花費數千倍的時間。 – 2011-04-21 21:32:42

對於大量項目，插入排序不是一種非常有效的算法。

這裏拿走的是，如果算法本身很慢，那麼您可以做的任何優化都沒有多大的影響。

使用mergesort或quicksort alogrithm編寫您的排序，您的排序時間將顯着減少。

來源

2011-04-21 22:01:34

@ thom如果你想學習排序，你想覆蓋所有的基地！ – afuzzyllama 2011-04-22 03:08:10

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

來源

2013-10-07 14:02:32 gyaan

PHP插入排序功能的性能

回答

相關問題