归并排序

  • 时间复杂度 O(n)
  • 空间复杂度 O(log2n)

PHP:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
function merge(array $left, array $rigth) : array 
{
$result = array();

while (count($left) && count($rigth)) {
$result[] = $left[0] < $rigth[0] ? array_shift($left) : array_shift($rigth);
}

return array_merge($result, $left, $rigth);
}

function al_merge_sort(array $arr) : array
{
$len = count($arr);
if ($len <= 1) {
return $arr;
}

$mid = intval($len / 2);

$left = array_slice($arr, 0, $mid);
$rigth = array_slice($arr, $mid);

$left = al_merge_sort($left);
$rigth = al_merge_sort($rigth);

return merge($left, $rigth);
}

print_r(al_merge_sort([9, 3, 5, 6, 7, 1, 2, 55, 56]));

// Array
// (
// [0] => 1
// [1] => 2
// [2] => 3
// [3] => 5
// [4] => 6
// [5] => 7
// [6] => 9
// [7] => 55
// [8] => 56
// )

Go:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package main

import (
"fmt"
)

func merge(left, rigth []int) (result []int) {

l, r := 0, 0

for l < len(left) && r < len(rigth) {
if left[l] < rigth[r] {
result = append(result, left[l])
l ++
} else {
result = append(result, rigth[r])
r ++
}
}

result = append(result, left[l:]...)
result = append(result, rigth[r:]...)

return
}

func al_merg_sort(arr []int) []int {
length := len(arr)

if length <= 1 {
return arr
}

mid := length / 2

left := al_merg_sort(arr[:mid])
rigth := al_merg_sort(arr[mid:])

return merge(left, rigth)
}

func main() {
arr := []int{31, 4, 5, 27, 18, 1 ,3, 6, 8}
fmt.Println(al_merg_sort(arr))
}