使用 PHP 實現「選擇排序」

Algorithm
, , ,

做法

首先在未排序的陣列中找到最小的元素，然後移動到已排序陣列的末端。

實作

原始陣列。

1
$items = [33, 75, 26, 5, 51];

一開始假定最小値是 33。

1
2
$i = 0;
$min = $i;

先做一次迴圈。

1
2
3
4
5
for ($j = $i + 1; $j < count($items); $j++) {
    if ($items[$min] > $items[$j]) {
        $min = $j;
    }
}

把記錄最小値位置的參數 $min 輸出分別是：

1
2
3
4
0 // 33 沒有大於 75，所以 $min 還是 0
2 // 33 大於 26，所以 $min 變成 2
3 // 33 大於 5 ，所以 $min 變成 3
3 // 33 沒有大於 51，所以 $min 還是 3

因此得知最小値是 5，就可以把 5 和 33 做交換。

1
2
3
$temp = $items[$min];
$items[$min] = $items[$i];
$items[$i] = $temp;

這樣的判斷做 4 次，也就是 (n-1) 次，就可以得到：

1
2
3
4
5
6
7
8
// 5 和 33 做交換
Array ( [0] => 5 [1] => 75 [2] => 26 [3] => 33 [4] => 51 )
// 75 和 26 做交換
Array ( [0] => 5 [1] => 26 [2] => 75 [3] => 33 [4] => 51 )
// 75 和 33 做交換
Array ( [0] => 5 [1] => 26 [2] => 33 [3] => 75 [4] => 51 )
// 75 和 51 做交換
Array ( [0] => 5 [1] => 26 [2] => 33 [3] => 51 [4] => 75 )

最終可寫為：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function selectionSort($items) {
    for ($i = 0; $i < count($items) - 1; $i++) {
        $min = $i;

        for ($j = $i + 1; $j < count($items); $j++) {
            if ($items[$min] > $items[$j]) {
                $min = $j;
            }
        }

        $temp = $items[$min];
        $items[$min] = $items[$i];
        $items[$i] = $temp;
    }

    return $items;
}

程式碼