使用 PHP 實現「冒泡排序」

Algorithm
, , ,

做法

重複地走訪要排序的數列，相鄰比較兩個元素，再根據條件進行交換。

實作

原始陣列。

1
$items = [5, 4, 3, 2, 1];

先試著做一次相鄰比較並交換値的迴圈。

1
2
3
4
5
6
7
for ($j = 0; $j < count($items) - 1 - $i; $j++) {
    if ($items[$j] > $items[$j + 1]) {
        $temp = $items[$j];
        $items[$j] = $items[$j + 1];
        $items[$j + 1] = $temp;
    }
}

輸出：

1
2
3
4
Array ( [0] => 4 [1] => 5 [2] => 3 [3] => 2 [4] => 1 )
Array ( [0] => 4 [1] => 3 [2] => 5 [3] => 2 [4] => 1 )
Array ( [0] => 4 [1] => 3 [2] => 2 [3] => 5 [4] => 1 )
Array ( [0] => 4 [1] => 3 [2] => 2 [3] => 1 [4] => 5 )

經過 4 次相鄰比較後，把 5 挪到最後面了。

這樣的迴圈重複做 4 遍可以得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Array ( [0] => 4 [1] => 5 [2] => 3 [3] => 2 [4] => 1 )
Array ( [0] => 4 [1] => 3 [2] => 5 [3] => 2 [4] => 1 )
Array ( [0] => 4 [1] => 3 [2] => 2 [3] => 5 [4] => 1 )
Array ( [0] => 4 [1] => 3 [2] => 2 [3] => 1 [4] => 5 )

Array ( [0] => 3 [1] => 4 [2] => 2 [3] => 1 [4] => 5 )
Array ( [0] => 3 [1] => 2 [2] => 4 [3] => 1 [4] => 5 )
Array ( [0] => 3 [1] => 2 [2] => 1 [3] => 4 [4] => 5 )
Array ( [0] => 3 [1] => 2 [2] => 1 [3] => 4 [4] => 5 )

Array ( [0] => 2 [1] => 3 [2] => 1 [3] => 4 [4] => 5 )
Array ( [0] => 2 [1] => 1 [2] => 3 [3] => 4 [4] => 5 )
Array ( [0] => 2 [1] => 1 [2] => 3 [3] => 4 [4] => 5 )
Array ( [0] => 2 [1] => 1 [2] => 3 [3] => 4 [4] => 5 )

Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 )
Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 )
Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 )
Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 )

但會發現，後面已經排序過的部分不需要再排序，因此可以改良為：

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort($items) {
    for ($i = 0; $i < count($items) - 1; $i++) {
        for ($j = 0; $j < count($items) - 1 - $i; $j++) {
            if ($items[$j] > $items[$j + 1]) {
                $temp = $items[$j];
                $items[$j] = $items[$j + 1];
                $items[$j + 1] = $temp;
            }
        }
    }

    return $items;
}

輸出得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
Array ( [0] => 4 [1] => 5 [2] => 3 [3] => 2 [4] => 1 )
Array ( [0] => 4 [1] => 3 [2] => 5 [3] => 2 [4] => 1 )
Array ( [0] => 4 [1] => 3 [2] => 2 [3] => 5 [4] => 1 )
Array ( [0] => 4 [1] => 3 [2] => 2 [3] => 1 [4] => 5 )

Array ( [0] => 3 [1] => 4 [2] => 2 [3] => 1 [4] => 5 )
Array ( [0] => 3 [1] => 2 [2] => 4 [3] => 1 [4] => 5 )
Array ( [0] => 3 [1] => 2 [2] => 1 [3] => 4 [4] => 5 )

Array ( [0] => 2 [1] => 3 [2] => 1 [3] => 4 [4] => 5 )
Array ( [0] => 2 [1] => 1 [2] => 3 [3] => 4 [4] => 5 )

Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 )

程式碼