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

Bubble Sort (氣泡排序法) In PHP Laravel - 完全杜絕 N+1 issue 的可能

留言

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×