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

• 2019 年 11 月 24 日
• 筆記

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循环来定位插入项目的位置。

<?php  $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）时不运行循环。