數據結構和算法——插入排序

• 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）時不運行循環。