选择在PHP中排序-DEV365 开发者社区

关于选择排序

选择排序是一种基于原位比较的分类算法。它可以通过反复从数组的未排序部分找到最小元素，并用未分类部分的第一个元素将其交换。该过程一直持续到整个数组分类为止。它具有O（n^2）的时间复杂性，使其对于大数据集的效率低下。

选择排序算法

该算法涉及循环和比较两个值，我们保持最小值索引的跟踪。

循环中的步骤：

我们需要跟踪最小值的索引，因此我们在循环开始时将临时变量$min_i分配给$i。
在循环中，我们比较$min_i和$j的值。
如果index $j处的值小于$i的值，我们将使用位置较小值的新索引更改$min_i。

循环＃1

我们将第一个值（5）与所有值进行比较，我们发现索引1的值小于5。一旦循环结束，我们将交换5和1。

。


循环＃1

循环＃2

现在，第一个索引已被排序，因此我们继续循环并将5与其余数组进行比较。我们发现3小于5，最后交换它们。


循环＃2

循环＃3

值1和3是分类的，但是在最后一个循环中，$ min_i不会更改（没有小于4的值），因此我们不交换。这也是为什么我们有跳过交换if $i != $min_i的条件。


循环＃3


final

功能

function selectionSort(array $a): array
{
  for ($i = 0; $i < count($a) - 1; $i++) {
    $min_i = $i;
    for ($j = $i + 1; $j < count($a); $j++) {
      if ($a[$j] < $a[$min_i]) {
        $min_i = $j;
      }
    }
    if ($i != $min_i) {
      $temp = $a[$i];
      $a[$i] = $a[$min_i];
      $a[$min_i] = $temp;
    }
  }
  return $a;
}

// $a = [5, 1, 4, 3];
// selectionSort($a);
// [1, 3, 4, 5]

您也可以在这里找到脚本：

https://gist.github.com/matusstafura/09c0af86c749f5e5066f920d44f31ba1

时间复杂性

选择排序的时间复杂性为o（n^2），其中n是数组中的元素数。