使用 PHP 實現「插入排序」

Algorithm
, , ,

做法

把未排序的元素，在已排序的陣列裡頭，從後向前比對，找到相應的位置後插入。

實作

原始陣列。

1
$items = [75, 18, 53, 94, 31];

首先把陣列的第 2 個値 18 設為準備插入値。

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

先做一次比較迴圈，如果準備插入値小於比較値（準備插入値的前一個値），就把比較値複製到後面一個位置，並且停止迴圈。

1
2
3
for ($j = $i - 1; $j >= 0 && $temp < $items[$j]; $j--) {
    $items[$j + 1] = $items[$j];
}

輸出：

1
Array ( [0] => 75 [1] => 75 [2] => 53 [3] => 94 [4] => 31 )

再把比較値的位置改為準備插入値 18。

1
$items[$j + 1] = $temp;

輸出：

1
Array ( [0] => 18 [1] => 75 [2] => 53 [3] => 94 [4] => 31 )

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Array ( [0] => 75 [1] => 18 [2] => 53 [3] => 94 [4] => 31 )
// 準備插入値 18 比比較値 75 小，比較値 75 往後複製
// Array ( [0] => 75 [1] => 75 [2] => 53 [3] => 94 [4] => 31 )
// 比較値位置改為準備插入値 18
Array ( [0] => 18 [1] => 75 [2] => 53 [3] => 94 [4] => 31 )
// 準備插入値 53 比比較値 75 小，比較値 75 往後複製
// Array ( [0] => 18 [1] => 75 [2] => 75 [3] => 94 [4] => 31 )
// 比較値位置改為準備插入値 53
Array ( [0] => 18 [1] => 53 [2] => 75 [3] => 94 [4] => 31 )
// 準備插入値 94 沒有比比較値 75 小
Array ( [0] => 18 [1] => 53 [2] => 75 [3] => 94 [4] => 31 )
// 準備插入値 31 比比較値 94 小，比較値 94 往後複製
// Array ( [0] => 18 [1] => 53 [2] => 75 [3] => 94 [4] => 94 )
// 準備插入値 31 比比較値 75 小，比較値 75 往後複製
// Array ( [0] => 18 [1] => 53 [2] => 75 [3] => 75 [4] => 94 )
// 準備插入値 31 比比較値 53 小，比較値 53 往後複製
// Array ( [0] => 18 [1] => 53 [2] => 53 [3] => 75 [4] => 94 )
// 準備插入値 31 沒有比比較値 18 小 ，迴圈中斷。
// 比較値位置改為準備插入値 53
Array ( [0] => 18 [1] => 31 [2] => 53 [3] => 75 [4] => 94 )

因此最終可寫為：

1
2
3
4
5
6
7
8
9
10
11
12
13
function insertionSort($items) {
    for ($i = 1; $i < count($items); $i++) {
        $temp = $items[$i];

        for ($j = $i - 1; $j >= 0 && $temp < $items[$j]; $j--) {
            $items[$j + 1] = $items[$j];
        }

        $items[$j + 1] = $temp;
    }

    return $items;
}

程式碼