Selection Sort (選擇排序法) In PHP

# 前言

出來混總是要還的! 身為一個非本科的工程師, 就是自己找時間把自己缺的的都補上！
實作沒什麼好交代的, 直接看範例看註解吧！

# 概念解說

先來說說 selection sort 的概念, 聽我說完沒學過的很可能會一臉矇逼, 沒矇逼就代表我概念說的還行, 矇逼也是正常的, 要配合服用 example code, 才會藥到病除
概念是這樣:
selection sort 是一種比較式的演算法, 看起來跟 bubble sort 有點像, 而最大的不同之處在於它的交換動作比 bubble sort 要來得少
我們一開始找到最大/最小的值, 並將他們放在第一個位置, 最大/最小取決於正序/倒序排列。
在第二輪呢, 我們取最大/最小值, 並將它至於第二個位置, 反覆直到每個數字都被排到正確的位置
下面是示意圖：

示意圖解析：
第一輪一開始第一個數字是 20, 然後我們找到最小值, 即10, 至此, 我們都還沒有進行交換動作, 只是將第一個以及最小值的位置記下, 在第一輪最後, 我們在進行交換動作
第二輪我們從 45 開始, 並開始往後尋找下一個最小值, 找到了 20, 如同上一輪的動作, 我們將 45 與 20 的位置進行了交換
重複此動作, 直到完成 sorting

# 實作範例

直接看範例

• Answer:

  <?php
  function selectionSort(array $arr): array {
      $len = count($arr);
      // 外層迴圈主要定位了 "當次迴圈中要變更的 index 位置"
      for ($i = 0; $i < $len; $i++) {
        // 由於每一輪的開始, 都會假設 $i 是目前最小的值
        $min = $i;
        for ($j = $i+1; $j < $len; $j++) {
            // 目的要找出最小值的 index 位置
            if ($arr[$j] < $arr[$min]) {
              // $min 代表最小值的 index 位置, 會動態更換
              $min = $j;
            }
        }
        // 如果找到的最小值 index 跟當前的 $i index 不相符, 則對調他們
        if ($min != $i) {
            $tmp = $arr[$i];
            $arr[$i] = $arr[$min];
            $arr[$min] = $tmp;
        }
      }
      return $arr;
  }

# 複雜度

最佳複雜度	$$\Omega(n^2)$$
最差複雜度	$$O(n^2)$$
平均複雜度	$$\Theta(n^2)$$
空間複雜度	$$O(1)$$

# 參考資料

PHP 7 Data Structures and Algorithms: Implement linked lists, stacks, and queues using PHP