使用 PHP 實現「合併排序」

Algorithm
, , ,

做法

將陣列分割後排序，再將兩個已排序的陣列合併成一個陣列。

實作

原始陣列。

1
$items = [74, 52, 91, 13, 6, 69, 31, 24];

先試著把陣列分割成左陣列和右陣列。

1
2
3
$half = (int) floor(count($items) / 2); // 找出陣列的中間位置
$left = array_slice($items, 0, $half); // 用中間位置分割成左陣列
$right = array_slice($items, $half); // 用中間位置分割成右陣列

輸出：

1
2
Array ( [0] => 74 [1] => 52 [2] => 91 [3] => 13 )
Array ( [0] => 6 [1] => 69 [2] => 31 [3] => 24 )

使用遞迴函數。

1
2
3
4
5
6
7
8
9
10
11
12
function mergeSort($items) {
    // 當元素只剩下 1 個時，返回自己不再分割
    if (count($items) <= 1) {
        return $items;
    }

    $half = (int) floor(count($items) / 2);
    $left = array_slice($items, 0, $half);
    $right = array_slice($items, $half);
    $left = mergeSort($left);
    $right = mergeSort($right);
}

輸出：

1
2
3
4
5
6
7
8
9
10
11
12
13
Array ( [0] => 74 [1] => 52 [2] => 91 [3] => 13 )
Array ( [0] => 6 [1] => 69 [2] => 31 [3] => 24 )
Array ( [0] => 74 [1] => 52 )
Array ( [0] => 91 [1] => 13 )
Array ( [0] => 74 )
Array ( [0] => 52 )
Array ( [0] => 91 )
Array ( [0] => 13 )
Array ( [0] => 6 [1] => 69 )
Array ( [0] => 31 [1] => 24 )
Array ( [0] => 6 )
Array ( [0] => 69 )
Array ( [0] => 31 )

設定另一個 merge() 函數，以進行比較合併。

1
2
3
4
5
6
7
8
9
10
11
12
function merge($left, $right) {
    // 比較左陣列和右陣列的第 1 個元素，小的優先放進新陣列，直到一方陣列的元素用完
    while (count($left) && count($right)) {
        if ($left[0] < $right[0]) {
            $reg[] = array_shift($left);
        } else {
            $reg[] = array_shift($right);
        }
    }

    return array_merge($reg, $left, $right); // 回傳已排序的陣列
}

因此寫為：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function mergeSort($items) {
    if (count($items) <= 1) {
        return $items;
    }

    $half = (int) floor(count($items) / 2);
    $left = mergeSort(array_slice($items, 0, $half));
    $right = mergeSort(array_slice($items, $half));

    return merge($left, $right);
}

function merge($left, $right) {
    while (count($left) && count($right)) {
        if ($left[0] < $right[0]) {
            $reg[] = array_shift($left);
        } else {
            $reg[] = array_shift($right);
        }
    }

    return array_merge($reg, $left, $right);
}

輸出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Array ( [0] => 52 ) // [74] 和 [52] 比較，52 放進新陣列
Array ( [0] => 74 ) // 左陣列
Array ( ) // 右陣列
Array ( [0] => 13 ) // [91] 和 [13] 比較，13 放進新陣列
Array ( [0] => 91 ) // 左陣列，留下 91，直接放進新陣列的尾巴
Array ( )  // 右陣列
Array ( [0] => 13 ) // [52, 74] 和 [13, 91] 比較，13 放進新陣列
Array ( [0] => 13 [1] => 52 ) // [52, 74] 和 [91] 比較，52 放進新陣列
Array ( [0] => 13 [1] => 52 [2] => 74 ) // [74] 和 [91] 比較，74 放進新陣列
Array ( ) // 左陣列
Array ( [0] => 91 ) // 右陣列
Array ( [0] => 6 ) // [6] 和 [69] 比較，6 放進新陣列
Array ( ) // 左陣列
Array ( [0] => 69 ) // 右陣列
Array ( [0] => 24 ) // [31] 和 [24] 比較，24 放進新陣列
Array ( [0] => 31 ) // 左陣列
Array ( ) // 右陣列
Array ( [0] => 6 ) // [6, 69] 和 [24, 31] 比較，6 放進新陣列
Array ( [0] => 6 [1] => 24 ) // [69] 和 [24, 31] 比較，24 放進新陣列
Array ( [0] => 6 [1] => 24 [2] => 31 ) // [69] 和 [31] 比較，31 放進新陣列
Array ( [0] => 69 ) // 左陣列，留下 69，直接放進新陣列的尾巴
Array ( ) // 右陣列
Array ( [0] => 6 ) // [13, 52, 74, 91] 和 [6, 24, 31, 69] 比較，6 放進新陣列
Array ( [0] => 6 [1] => 13 ) // ...... 13 放進新陣列
Array ( [0] => 6 [1] => 13 [2] => 24 ) // ...... 24 放進新陣列
Array ( [0] => 6 [1] => 13 [2] => 24 [3] => 31 ) // ...... 31 放進新陣列
Array ( [0] => 6 [1] => 13 [2] => 24 [3] => 31 [4] => 52 ) // ...... 52 放進新陣列
Array ( [0] => 6 [1] => 13 [2] => 24 [3] => 31 [4] => 52 [5] => 69 ) // ...... 69 放進新陣列
Array ( [0] => 74 [1] => 91 ) // 左陣列，留下 [74, 91]，直接放進新陣列的尾巴
Array ( ) // 右陣列

最終可合併為：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function mergeSort($items) {
    if (count($items) <= 1) {
        return $items;
    }

    $half = (int) floor(count($items) / 2);
    $left = mergeSort(array_slice($items, 0, $half));
    $right = mergeSort(array_slice($items, $half));

    while (count($left) && count($right)) {
        if ($left[0] < $right[0]) {
            $reg[] = array_shift($left);
        } else {
            $reg[] = array_shift($right);
        }
    }

    return array_merge($reg, $left, $right);
}

程式碼