插入排序

Question

這兩個實現之間的區別我覺得這兩個實現都在做同樣的事情，但如果你可以讓我知道它們是否（性能明智）做同樣的事情（例如在數字方面的指令執行）。謝謝。

<?php 

$arr = array(10, 2, 3, 14, 16); 

function sortOne($arr) { 

    $instructionCount = 0; 

    for ($i = 1; $i < count($arr); $i++) { 
     $instructionCount++; 
     for ($j = $i - 1; $j >= 0 && ($arr[$j] > $arr[$i]); $j--) { 
      $instructionCount++; 

      $tmp = $arr[$i]; 
      $arr[$i] = $arr[$j]; 
      $arr[$j] = $tmp; 

     } 
    } 

    echo "\nTotal Instructions for Sort One: $instructionCount\n"; 

    return $arr; 
} 

function sortTwo($array) { 

    $instructionCount = 0; 

    for($j=1; $j < count($array); $j++){ 
     $instructionCount++; 
     $temp = $array[$j]; 
     $i = $j; 
     while(($i >= 1) && ($array[$i-1] > $temp)){ 
      $instructionCount++; 
      $array[$i] = $array[$i-1]; 
      $i--; 
     } 
     $array[$i] = $temp; 
    } 

    echo "\nTotal Instructions for Sort Two: $instructionCount\n"; 

    return $array; 
} 


var_dump(sortOne($arr)); 

Answer 1

不，他們是不一樣的。功能sortOne是錯誤執行的insertion sort。

正確執行的功能sortOne是：

for ($i = 1; $i < count($arr); $i++) { 
    $instructionCount++; 
    $temp = $arr[$i]; 
    for ($j = $i - 1; $j >= 0 && ($arr[$j] > $temp); $j--) { 
     $instructionCount++; 
     $arr[$j + 1] = $arr[$j];     
    } 
    $arr[$j + 1] = temp; 
} 

現在考慮的表現，他們基本上有相同的性能。只要將循環更改爲while循環，您不會得到任何性能變化。