选择排序最佳交换情况不是O（N）是O（1）!!？

Question

我在选择排序中看到，如果内部等于最小值，它将交换它们。但为什么你这样做？我刚刚添加了if语句用于交换if $ inner = $ min所以为什么交换它们因为它们是相同的索引！那你为什么这么做？!!

条件是：if $ inner = $ minimum（不要交换）。否则他们不平等（交换）。

这是代码。

<?php
$a = array(10,9,8,7,6,5,4,3,2,1);
$num = sizeof($a);

$comp = 0;
$swap = 0;

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

for ($in=0; $in < $num; $in++) { 
      $min  = $in;
     for ($i=$in+1; $i < $num; $i++) { 
         if ($a[$i] < $a[$min]) {
           $min = $i;
         }
         $comp++;
     }
     if ($in != $min) {
       $past = $a[$min];
       $a[$min] = $a[$in];
       $a[$in] = $past;
       $swap++;
     }
}


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


?>

Answer 1

不会。时间复杂度不依赖于您执行的交换次数，而是取决于检查的迭代次数。

让我们举个例子。，1 4 9 3 0 8 5

你说你将迭代整个数组并找到最低（最小）数，如果两者不相等，你将把它与当前索引交换。

那意味着，

你的排序数组：0 4 9 3 1 8 5

但它没有排序。这意味着它仅排序到第0个[第一个数字]索引。

你必须从第二个索引重复它。

现在，让我们找出实际的时间复杂度。

当你为每个索引迭代时（让我们把它作为'i'），对于外循环它是O（N）并且你将从i + 1迭代内循环（让我们把它作为'j'）并且它是O（N）内循环。

所以O（N）* O（N）= O（N ^ 2）

如果你仍然有任何疑问，让我们采取j的迭代，即

对于i = 0，j从1 - > N迭代

对于i = 1，j从2 - > N迭代

对于i = 2，j从3 - > N迭代，依此类推......

so =（N-1）+（N-2）+（N-3）+（N-4）...... + 1

=>（N（N-1））/ 2

=是（不是^ 2）