选择排序的思想是在未排序数组中查找最小或最大元素，并将其放置在已排序数组中的正确位置。这将导致每次迭代后将已排序数组的长度增加 1，并将未排序数组的长度减少 1。
示例:
为了理解选择排序，让我们考虑一下未排序的数组 [1, 10, 23, -2] 并讨论按升序对数组进行排序所采取的每个步骤。在每次遍历中，都会在未排序的数组中找到最小的元素，并与未排序的数组的第一个元素交换。
第一遍:整个数组未排序数组，(-2) 是数组中最小的数字。找到(-2)作为最小数字后，将其与数组的第一个元素交换。
第二遍: 在此示例中，左侧数组是排序数组，并且该数组的长度在每次迭代后增加一。第一次传递后，排序数组的长度为 1。数组的其余部分是未排序的数组。 (1) 是未排序数组中的最小数字，与未排序数组的第一个元素交换。交换后，排序数组和未排序数组的长度将为 2。
第三遍: (10)是未排序数组中的最小数字，并与未排序数组的第一个元素交换。
第四遍: (23) 是未排序数组中唯一位于正确位置的数字。
选择排序的实现
<?php
//选择排序函数
function selectionsort(&$Array, $n) {
for($i=0; $i<$n; $i++) {
$min_idx = $i;
for($j=$i+1; $j<$n; $j++) {
if($Array[$j] < $Array[$min_idx])
{$min_idx = $j;}
}
$temp = $Array[$min_idx];
$Array[$min_idx] = $Array[$i];
$Array[$i] = $temp;
}
}
//打印数组的函数
function PrintArray($Array, $n) {
for ($i = 0; $i < $n; $i++)
echo $Array[$i]." ";
echo "\n";
}
//测试代码
$MyArray = array(1, 10, 23, 50, 4, 9, -4);
$n = sizeof($MyArray);
echo "原始数组\n";
PrintArray($MyArray, $n);
selectionsort($MyArray, $n);
echo "\n排序数组\n";
PrintArray($MyArray, $n);
?> 上面的代码将给出以下输出:
原始数组
1 10 23 50 4 9 -4
排序数组
-4 1 4 9 10 23 50 时间复杂度:
即使整个数组已排序，选择排序的时间复杂度在所有情况下都是θ(N²)，因为整个数组需要对每个元素进行迭代，并且它包含两个嵌套。