插入和选择排序比较和交换时间是否相等？

Question

在我的代码中，我计算了插入排序和选择排序比较和交换时间。但我看到他们在比较和掉期方面是平等的。但我使用while循环进行插入。我可以使用for循环进行选择。看看代码。

    <?php
$a = array(4,1,7,9,3,2,6,8,10,20,14,29,54,27,563,4,563,334,2,7,5,42,24);
$num = sizeof($a);


for ($i=0; $i < $num; $i++) { 
  echo "$a[$i] | ";
}
echo "<br>";


echo "<br>Selection<br>";

//selection sort
$swap = 0;
$com = 0;
for ($inner=0; $inner < $num-1; $inner++) { 
  $min = $inner;

  for ($i=$inner+1; $i < $num; $i++) { 

    if ($a[$i] < $a[$min]) {
       $min = $i;

    }
     $com++;

  }
  $swap++;
  $past = $a[$inner];
  $a[$inner] = $a[$min];
  $a[$min] = $past;
}


for ($k=0; $k < $num; $k++) { 
  echo "$a[$k] | ";
}

echo "Com : <span style='color:red;'>$com</span> ";
echo "Swap  :<span style='color:red;'> $swap</span> ";



echo "<br>Insertion<br>";


$swap = 0;
$com = 0;

for ($out=1; $out < $num ; $out++) { 
   $temp = $a[$out];

   for ($i=$out; $i > 0; $i--) { 
         if ($a[$i-1] >= $temp) {
          $a[$i] = $a[$i-1];
         }
         $com++;
   }
   $a[$i] = $temp;
   $swap++;
}

for ($k=0; $k < $num; $k++) { 
  echo "$a[$k] | ";
}

echo "Com : <span style='color:red;'>$com</span> ";
echo "Swap  :<span style='color:red;'> $swap</span> ";




?>

现在。你怎么能告诉我插入排序比任何情况下的选择排序更快？因为他们在我的代码中所有时间都是平等的！谢谢

Answer 1

现在，我没有测试两种算法性能的框架......但我认为我们可以在纯粹的理论观点上进行性能分解。

选择排序

它包括重复选择未排序数组中的第一个元素，并将其与剩余的未排序元素进行比较。它类似于冒泡排序，但它不是交换较小的元素，而是保持最小的元素索引更新并在每次迭代结束时交换它。

插入排序

它创建一个已排序的子数组，并重复地将新元素插入其中。它遵循以下逻辑：

• 将第一个元素作为已排序的子数组。
• 将第二个元素插入到已排序的子数组中（根据需要进行移位）。
• 将第三个元素插入到已排序的子数组中（根据需要进行移位）。
• 冲洗并重复，直到没有剩余元素。

结论

在时间复杂度方面，选择排序总是(n * (n - 1)) / 2（转换为~O(n^2)）。在另一方面，插入排序可以提供更好的性能，因为只有最坏的情况时间复杂度是(n * (n - 1)) / 2（与选择排序相同）。如果我给出了选择，我会选择插入排序算法，因为可能发生的最糟糕的事情是获得相同的选择排序性能。您可以随时使用microtime并对两者进行快速基准测试，以便了解哪一个能为您带来最佳效果。