数据结构和算法——插入排序

点击上方“Lemon黄”关注我哦，不定期原创文，定期好技术文推广分享

1、要解决的问题

给定如下所示的数字列表，请按升序对它们进行排序。

$numbers = [21,25,100,98,89,77];

要求

对数字进行排序时，需要使用插入排序算法。

用PHP实现该算法

2、伪代码说明

插入排序的工作方式是：维护已排序的子列表，一一提取主列表中的项目，然后将其插入子列表中，直到所有项目都从主列表移到子列表中为止。

绿色部分就是已排序的子列表

描述插入排序的伪代码如下：

FOR each element of the master list //循环主列表

Extract the current item //提取当前索引元素

Locate the position to insert by comparing with items from sub-list //通过与子列表中的项目进行比较来找到要插入的位置

Insert the item to the position //将元素插入到子列表指定位置

END FOR//结束循环

3、PHP实现插入排序

我们需要一个FOR循环和一个WHILE循环。我们使用FOR循环来迭代主列表，并使用WHILE循环来定位插入项目的位置。

$masterList = [21, 25, 100, 98, 89, 77];

$subList = [];

for ($i = 0; $i < count($masterList); $i++) {

$extractItem = $masterList[$i];

$subList[] = $extractItem;

// 通过与子列表中的项目进行比较来找到要插入的位置

$positionFound = $i;

while ($positionFound > 0 && $extractItem < $subList[$positionFound - 1]) {

$subList[$positionFound] = $subList[$positionFound - 1];

$positionFound = $positionFound - 1;

}

// 将元素插入到子列表指定位置

$subList[$positionFound] = $extractItem;

}

print_r($subList);

// 输出：

/*

Array

(

[0] => 21

[1] => 25

[2] => 77

[3] => 89

[4] => 98

[5] => 100

)

*/

唯一需要说明的部分可能是WHILE循环。注意循环的条件，除了限制子列表的长度外，我们还需要确保提取第一个元素（$ positionFound = 0）时不运行循环。