Insertion Sort (插入排序法) In PHP

# 前言

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

# 概念解說

Insertion sort 某程度上會比 bubble sort 以及 selection sort 更有效率。
當 n 比較小時, insertion sort 效率較佳, 反之效率較差。
如同它的名字, insertion sort 的原則就是將數字插入到左側的正確位置。 它從 array 的第二個 index 開始, 檢查位於當前 index 左側的數字是否小於當前 index, 如果是, 就調換數字位置, 將較小的數字放到正確的位置。
然後再從下一個 index 開始, 重複直到所有 array 都完成排序。

引述大話資料結構

就像玩撲克牌一樣, 我們每抽到一張牌都會照大小順序排列, 例如我們已經有 A, 3, 4 三張牌, 這時抽到 2, 就會把它排在 A 跟 3 中間, 以此類推, 會將抽到的牌放到對的位置

示意圖如下：

示意圖解析:

• 從第二個 index 開始, 即 45, 檢查第二個 index 左側是否有比 45 大的數字, 只有 20 這一個數字, 所以此輪沒必要插入
• 接著從第三個 index 開始, 即 93, 比較 45 是否比 93 大, 結果不是, 到此結束第二輪, 因為在第一輪我們已經比較過 45 跟 20。 到目前, 我們已有 (20, 45, 93) 三個排好的數字
• 接著從第四個 index 開始, 即 67, 比較 93 是否比 67 大, 結果是的, 所以我們將 93 放到 67 目前的位置, 然後繼續往左檢查, 比較 45 是否比 67 大, 結果不是。 至此停下。 然後將 67 插入到 93 原本的位置
• 重複以上動作, 直到所有數字都完成排序

# 實作範例

直接看範例

<?php
// 使用 PHP Reference, 因此會直接更動外面的 $arr 內容
function insertionSort(array &$arr) { 
    $len = count($arr); 
    // 外層迴圈決定了 "待比較" index, 1-9 都會依次被比較
    for ($i = 1; $i < $len; $i++) { 
      // $key 即是每輪的主要 "待比較" 數
      $key = $arr[$i]; 
      $j = $i - 1; 

      // 內層 while 迴圈決定了 "待比較數" 的確切位置
      // 會將 $key 與往前的 index 依序比較, 若 $key 較小, 則會將該 index 往後挪
      // 依序往前比較, 直到 $key 不小於該 index, 這時 $key 會取代該 index 的後一個 index
      // 因為後一個 index 在上一輪已經被往後挪了
      while($j >= 0 && $arr[$j] > $key) { 
          $arr[$j+1] = $arr[$j]; 
          $j--; 
      }      
      $arr[$j+1] = $key; 
    }     
}

$arr = [20, 45, 93, 67, 10, 97, 52, 88, 33, 92];

insertionSort($arr);
echo implode(",", $arr);

# 複雜度

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

# 參考資料

大話資料結構
PHP 7 Data Structures and Algorithms: Implement linked lists, stacks, and queues using PHP