數據結構和演算法——選擇排序

• 2019 年 11 月 28 日
• 筆記

1、要解決的問題

給定如下所示的數字列表，請按升序對它們進行排序。

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

要求

• 對數字進行排序時，需要使用插入選擇演算法。
• 用PHP實現該演算法

2、偽程式碼說明

選擇排序的工作方式是：維護已排序的子列表，從主列表中找到最小的項，然後將其交換到子列表的最後一個元素，直到對所有項進行排序為止。

每次交換後，已排序的子列表的長度增加一，而主列表的長度減小一。

描述選擇排序的偽程式碼如下：

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

3、PHP實現快速排序

我們需要一個外部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開始。