给定如下所示的数字列表,请按升序对它们进行排序。
$numbers = [21,25,100,98,89,77];
要求
选择算法
。选择排序的工作方式是:维护已排序的子列表,从主列表中找到最小的项,然后将其交换到子列表的最后一个元素,直到对所有项进行排序为止。
每次交换后,已排序的子列表的长度增加一,而主列表的长度减小一。
描述选择排序的伪代码如下:
FOR each element of the master list indexed by i
Set current element of master list as the sub-list[i] element
Find the smallest item from the master list (staring from i)
Swap it with the last element of sub-list
END FOR
我们需要一个外部FOR
循环来遍历主列表,并需要一个内部FOR
循环从主列表中找到最小的项。
<?php
$masterList = [21, 25, 100, 98, 89, 77];
$subList = [];
for ($i = 0; $i < count($masterList); $i++) {
$subList[$i] = $masterList[$i];
// Find the smallest item
$smallestIndex = $i;
for ($j = $i; $j < count($masterList); $j++) {
if ($masterList[$j] < $masterList[$smallestIndex]) {
$smallestIndex = $j;
}
}
// 交换
$tmp = $subList[count($subList) - 1];
$subList[count($subList) - 1] = $masterList[$smallestIndex];
$masterList[$smallestIndex] = $tmp;
}
print_r($subList);
// Output:
/*
Array
(
[0] => 21
[1] => 25
[2] => 77
[3] => 89
[4] => 98
[5] => 100
)
*/
需要注意的,内部的for
循环从i
开始。